graph implementation c using adjacency list
Este tutorial explica a implementação de gráficos em C ++. Você também aprenderá sobre os diferentes tipos, representações e aplicações de gráficos:
Um gráfico é uma estrutura de dados não linear. Um gráfico pode ser definido como uma coleção de nós também chamados de “vértices” e “arestas” que conectam dois ou mais vértices.
Um gráfico também pode ser visto como uma árvore cíclica em que os vértices não têm uma relação pai-filho, mas mantêm uma relação complexa entre eles.
como testar a compatibilidade entre navegadores
=> Clique aqui para ver a série de treinamento Absolute C ++.
O que você aprenderá:
O que é um gráfico em C ++?
Conforme declarado acima, um gráfico em C ++ é uma estrutura de dados não linear definida como uma coleção de vértices e arestas.
A seguir está um exemplo de uma estrutura de dados de gráfico.
Dado acima está um exemplo de gráfico G. O gráfico G é um conjunto de vértices {A, B, C, D, E} e um conjunto de arestas {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Tipos de gráficos - gráfico direcionado e não direcionado
Um gráfico no qual as arestas não têm direções é chamado de gráfico não direcionado. O gráfico mostrado acima é um gráfico não direcionado.
Um gráfico no qual as arestas têm direções associadas a elas é chamado de gráfico direcionado.
A seguir está um exemplo de gráfico direcionado.
No gráfico direcionado mostrado acima, as bordas formam um par ordenado em que cada borda representa um caminho específico de um vértice para outro vértice. O vértice a partir do qual o caminho se inicia é chamado de “ Nó Inicial ”Enquanto o vértice em que o caminho termina é chamado de“ Nó Terminal ”.
Assim, no gráfico acima, o conjunto de vértices é {A, B, C, D, E} e o conjunto de arestas é {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Discutiremos a terminologia do gráfico ou os termos comuns usados em relação ao gráfico abaixo.
Terminologia de gráfico
- Vértice: Cada nó do gráfico é chamado de vértice. No gráfico acima, A, B, C e D são os vértices do gráfico.
- Beira: O link ou caminho entre dois vértices é chamado de aresta. Ele conecta dois ou mais vértices. As diferentes arestas no gráfico acima são AB, BC, AD e DC.
- Nó adjacente: Em um gráfico, se dois nós são conectados por uma aresta, eles são chamados de nós adjacentes ou vizinhos. No gráfico acima, os vértices A e B são conectados pela aresta AB. Assim, A e B são nós adjacentes.
- Grau do nó: O número de arestas conectadas a um nó específico é denominado grau do nó. No gráfico acima, o nó A tem grau 2.
- Caminho: A sequência de nós que precisamos seguir quando temos que viajar de um vértice para outro em um gráfico é chamada de caminho. Em nosso gráfico de exemplo, se precisarmos ir do nó A para C, o caminho seria A-> B-> C.
- Caminho fechado: Se o nó inicial for igual a um nó terminal, esse caminho será denominado caminho fechado.
- Caminho simples: Um caminho fechado no qual todos os outros nós são distintos é chamado de caminho simples.
- Ciclo: Um caminho no qual não há arestas ou vértices repetidos e o primeiro e o último vértices são iguais é chamado de ciclo. No gráfico acima, A-> B-> C-> D-> A é um ciclo.
- Gráfico conectado: Um grafo conectado é aquele em que existe um caminho entre cada um dos vértices. Isso significa que não existe um único vértice isolado ou sem borda de conexão. O gráfico mostrado acima é um gráfico conectado.
- Gráfico completo: Um gráfico no qual cada nó está conectado a outro é chamado de gráfico Completo. Se N é o número total de nós em um gráfico, o gráfico completo contém N (N-1) / 2 números de arestas.
- Gráfico ponderado: Um valor positivo atribuído a cada aresta indicando seu comprimento (distância entre os vértices conectados por uma aresta) é chamado de peso. O gráfico que contém arestas ponderadas é denominado gráfico ponderado. O peso de uma aresta e é denotado por w (e) e indica o custo de atravessar uma aresta.
- Diagrama: Um dígrafo é um gráfico no qual cada aresta está associada a uma direção específica e o percurso pode ser feito apenas na direção especificada.
Representação gráfica
A forma como a estrutura de dados do gráfico é armazenada na memória é chamada de “representação”. O gráfico pode ser armazenado como uma representação sequencial ou como uma representação vinculada.
Ambos os tipos são descritos a seguir.
Representação Sequencial
Na representação sequencial de grafos, usamos a matriz de adjacência. Uma matriz de adjacência é uma matriz de tamanho n x n onde n é o número de vértices no grafo.
As linhas e colunas da matriz de adjacência representam os vértices de um grafo. O elemento da matriz é definido como 1 quando há uma aresta presente entre os vértices. Se a borda não estiver presente, o elemento será definido como 0.
Abaixo está um gráfico de exemplo que mostra sua matriz de adjacência.
Vimos a matriz de adjacência para o gráfico acima. Observe que, como este é um gráfico não direcionado, podemos dizer que a aresta está presente em ambas as direções. Por exemplo, como a aresta AB está presente, podemos concluir que a aresta BA também está presente.
Na matriz de adjacência, podemos ver as interações dos vértices que são elementos da matriz que são colocados em 1 quando a aresta está presente e em 0 quando a aresta está ausente.
Agora vamos ver a matriz de adjacência de um grafo direcionado.
Conforme mostrado acima, o elemento de interseção na matriz de adjacência será 1 se e somente se houver uma aresta direcionada de um vértice para outro.
No gráfico acima, temos duas arestas do vértice A. Uma aresta termina no vértice B enquanto a segunda termina no vértice C. Assim, na matriz de adjacência, a interseção de A e B é definida como 1 como a interseção de A e C.
A seguir, veremos a representação sequencial do gráfico ponderado.
A seguir, está o grafo ponderado e sua matriz de adjacência correspondente.
qual é o melhor removedor de vírus
Podemos ver que a representação sequencial de um gráfico ponderado é diferente dos outros tipos de gráfico. Aqui, os valores diferentes de zero na matriz de adjacência são substituídos pelo peso real da aresta.
A aresta AB tem peso = 4, portanto, na matriz de adjacência, definimos a interseção de A e B em 4. Da mesma forma, todos os outros valores diferentes de zero são alterados para seus respectivos pesos.
A lista de adjacências é mais fácil de implementar e seguir. Traversal, ou seja, para verificar se há uma borda de um vértice para outro leva O (1) tempo e remover uma borda também leva O (1).
Quer o gráfico seja esparso (menos arestas) ou denso, ele sempre ocupa mais espaço.
Representação Vinculada
Usamos a lista de adjacências para a representação vinculada do grafo. A representação da lista de adjacências mantém cada nó do grafo e um link para os nós adjacentes a este nó. Quando atravessamos todos os nós adjacentes, definimos o próximo ponteiro como nulo no final da lista.
Vamos primeiro considerar um grafo não direcionado e sua lista de adjacências.
Conforme mostrado acima, temos uma lista vinculada (lista de adjacências) para cada nó. Do vértice A, temos arestas para os vértices B, C e D. Assim, esses nós estão ligados ao nó A na lista de adjacências correspondente.
A seguir, construímos uma lista de adjacências para o grafo direcionado.
No grafo direcionado acima, vemos que não há arestas originadas do vértice E. Portanto, a lista de adjacências para o vértice E está vazia.
Agora, vamos construir a lista de adjacências para o grafo ponderado.
Para um gráfico ponderado, adicionamos um campo extra no nó da lista de adjacência para denotar o peso da aresta conforme mostrado acima.
Adicionar vértice à lista de adjacências é mais fácil. Ele também economiza espaço devido à implementação da lista vinculada. Quando precisamos descobrir se existe uma aresta entre um vértice e outro, a operação não é eficiente.
Operações básicas para gráficos
A seguir estão as operações básicas que podemos realizar na estrutura de dados do gráfico:
- Adicione um vértice: Adiciona vértice ao gráfico.
- Adicione uma borda: Adiciona uma aresta entre os dois vértices de um gráfico.
- Exibir os vértices do gráfico: Exibe os vértices de um gráfico.
Implementação de gráfico C ++ usando lista de adjacência
Agora apresentamos uma implementação C ++ para demonstrar um grafo simples usando a lista de adjacências.
Aqui, exibiremos a lista de adjacências para um grafo direcionado ponderado. Usamos duas estruturas para conter a lista de adjacências e as arestas do grafo. A lista de adjacências é exibida como (start_vertex, end_vertex, weight).
O programa C ++ é o seguinte:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Resultado:
Resultado:
Lista de adjacência de gráfico
(start_vertex, end_vertex, weight):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Aplicações de gráficos
Vamos discutir algumas das aplicações de gráficos.
- Os gráficos são usados extensivamente na ciência da computação para representar gráficos de rede ou gráficos semânticos ou mesmo para descrever o fluxo de computação.
- Os gráficos são amplamente usados em compiladores para representar a alocação de recursos para processos ou para indicar análise de fluxo de dados, etc.
- Os gráficos também são usados para otimização de consulta em linguagens de banco de dados em alguns compiladores especializados.
- Em sites de redes sociais, os gráficos são as principais estruturas para representar a rede de pessoas.
- Os gráficos são amplamente utilizados para construir o sistema de transporte, especialmente a rede rodoviária. Um exemplo popular é o Google Maps, que usa amplamente gráficos para indicar direções em todo o mundo.
Conclusão
Um gráfico é uma estrutura de dados popular e amplamente usada que tem muitas aplicações no campo da ciência da computação em si, além de outros campos. Os gráficos consistem em vértices e arestas conectando dois ou mais vértices.
Um gráfico pode ser direcionado ou não direcionado. Podemos representar grafos usando uma matriz de adjacência, que é uma representação linear, e também usando uma lista vinculada de adjacência. Também discutimos a implementação do gráfico neste tutorial.
=> Veja aqui para explorar a lista completa de tutoriais C ++.
Leitura recomendada
- Python Advanced List Tutorial (List Sort, Reverse, Index, Copy, Join, Soma)
- Lista Python - criar, acessar, dividir, adicionar ou excluir elementos
- Lista de endereços IP do roteador padrão para marcas comuns de roteadores sem fio
- 12 melhores ferramentas de criação de gráfico de linha para criar gráficos de linha impressionantes (2021 RANKINGS)
- Senha de login do roteador padrão para modelos de roteador superior (lista 2021)
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Estrutura de dados de lista ligada circular em C ++ com ilustração
- Estrutura de dados de lista duplamente vinculada em C ++ com ilustração
