Lista de adjacência em C ++
- Lista de adjacência
- Matriz de adjacência
- Uma matriz de incidência
O tópico principal deste artigo será a lista de adjacência. Vamos primeiro tentar entender o que é realmente um gráfico antes de entrarmos nele para entender melhor essa ideia.
O que é um gráfico?
Um gráfico tem um número fixo de nós ou vértices. E cada nó é conectado por uma linha, que chamamos de vantagem. A borda é para comunicação entre dois vértices ou nós. Por exemplo, no gráfico acima, vemos seis vértices ou nós (0, 1, 2, 3, 4 e 5). Do vértice ou nó 0, podemos facilmente mudar para o vértice 1 e 3 porque há uma conexão direta entre eles. Mas não há conexão direta entre o vértice ou o nó 0 e 4.
Os gráficos são usados em muitos aplicativos da vida real para resolver problemas de rede. Por exemplo, no Facebook, o perfil do usuário é um nó ou vértice, e os amigos do usuário na lista são outros nós diferentes ou vértices que têm conexões diretas entre eles.
Tipos de gráficos
Existem principalmente dois tipos de gráficos, gráficos não direcionados e gráficos direcionados, ambos são descritos nas próximas seções:
Gráfico não direcionado
O gráfico não direcionado é muito famoso porque é um gráfico bidirecional. Por exemplo, abaixo está um exemplo de um gráfico não direcionado:
Gráfico não direcionado
No gráfico não direcionado, podemos mudar para qualquer vértice. Por exemplo, se houver uma conexão entre os nós A e B, também podemos passar de B para um.
Gráfico direcionado
Em um gráfico direcionado, as bordas têm bordas de direção. Portanto, essas bordas de seta nos dirão como podemos mover no gráfico de um vértice para outro vértice, mas apenas em algumas condições. Por exemplo, se houver uma borda direcionada entre os nós A e B, podemos passar rapidamente do vértice A a B, mas não de volta de B a A se não houver borda direcionada de B a A.
Gráfico direcionado
Lista de adjacência
A lista de adjacência é uma lista de matrizes em que o tamanho da matriz é igual ao número de nós presentes no gráfico. E cada nó também tem uma sub-matriz que representa sua conectividade com outros nós ou vértices. Vamos discutir as listas de adjacência dos dois tipos de gráficos (não direcionados e direcionados).
Lista de adjacência de gráficos não direcionados
No gráfico não direcionado acima, podemos ver seis vértices (0, 1, 2, 3, 4, 5). Então, temos uma variedade de seis vértices. E cada vértice individual possui sua própria lista vinculada ou lista de adjacência, como mostrado na lista de adjacência anterior. Podemos ver que o vértice 0 aponta para o vértice 4 e o vértice 3.
Mas, como explicamos antes, um gráfico não direcionado pode se mover em ambas as direções. Há uma vantagem entre os nós 0 e 4 e uma conexão direta entre 0 e 4. Mas devido ao gráfico não direcionado, também há uma conexão entre 4 e 0. É por isso que se você olhar para a lista de adjacência anterior, o Vertex 4 também aponta para o vértice 0. O mesmo também é verdadeiro no caso do vértice 3. A lista de adjacência do vértice 3 também aponta para o vértice 0.
Lista de adjacência de gráficos direcionados
A imagem acima é um gráfico direcionado e, do lado direito está sua lista de adjacência. Nesta lista de adjacência, podemos ver uma borda direta do nó 1 ao nó 2, mas não do nó 2 a 1. Então, só podemos nos mover em uma direção, isto é, de 1 a 2. O mesmo também está na lista de adjacência. Não podemos ver nenhum link do vértice 2 a 1 na lista de adjacência de 2.
Matriz de adjacência
A matriz é usada neste método para representar os detalhes dos vértices do gráfico. O tamanho da matriz depende do número de vértices no gráfico. Por exemplo, se algum gráfico tiver 5 vértices, o tamanho da matriz será 5 x 5. Nisso, a fila e a coluna são os próprios vértices. A representação da matriz da lista de adjacência usa 1 ou 0 para preencher a matriz. O valor de 1 representa um caminho do vértice da linha para a coluna vértice, mas o valor de 0 não representa o caminho entre o vértice da linha e a coluna vértice.
Lista de adjacência de matriz de gráficos não direcionada
Na lista de adjacência da matriz acima, podemos ver que A a E é o valor 0 porque não há caminho entre eles. Então, preenchemos esse valor com 0. Mas há um caminho de vértice b a a, e preenchemos esse valor com 1.
Lista de adjacência de matriz de gráficos direcionados
Na lista de adjacência da matriz acima direcionada, podemos ver que A a D é o valor 0 porque não há caminho de A a D, mas existe um caminho de D a A, por isso preenchemos esse valor com 1.
Matriz de incidência
A matriz é usada neste método para representar os detalhes dos vértices do gráfico. O tamanho da matriz depende do número de vértices e bordas totais no gráfico. Por exemplo, se algum gráfico tiver 5 vértices e 7 arestas, o tamanho da matriz será 5 x 7. As bordas representarão as colunas e os vértices estarão no lado da linha. A representação da matriz da lista de adjacência usa 0, 1 ou -1 para preencher os valores da matriz.
O valor de 1 representa um caminho de saída do vértice da linha para a coluna vértice, mas o valor de 0 representa nenhum caminho entre o vértice da linha e a coluna vértice. O valor de -1 representa um caminho de entrada para a borda do vértice da coluna.
Gráfico direcionado
Lista de adjacência do gráfico direcionado
Código C ++ para a lista de adjacência do gráfico direcionado
#incluir
usando namespace std;
// Sintaxe para criar um nó
Nó da estrutura
int valor;
Nó* a seguir;
;
// Isso armazenará os detalhes da borda do gráfico (fonte e destino)
Struct GraphEdge
Int fonte, destino;
;
classe graphadjacencylist
// Crie um novo nó para a lista de adjacência
Nó* getNeighbourVertex (Int Destination, Node* head_node)
Nó* new_node = novo nó;
new_node-> value = destino;
new_node-> next = head_node;
retornar new_node;
// ele armazenará o número total de nós em um gráfico
int number_of_nodes;
público:
Nó ** head_node;
GraphAdjacencyList (GraphEdge Graphedges [], int num, int number_of_nodes)
// alocação de memória dinâmica
head_node = new Node*[número_of_nodes] ();
this-> number_of_nodes = number_of_nodes;
// Inicialize o NODE DE CABEÇA para cada borda do gráfico
para (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
para (int k = 0; k < num; k++)
Int Source = Graphedges [K].fonte;
Int Destination = Graphedges [K].destino;
Nó* new_node = getNeighbourvertex (destino, head_node [origem]);
head_node [fonte] = new_node;
~ GraphadjacencyList ()
para (int k = 0; k < number_of_nodes; k++)
excluir [] head_node [k];
excluir [] head_node;
;
Void Display (Node* DisplayPtr)
while (displayptr != nullptr)
cout << " adjacency list -> " << displayptr->valor;
displayPtr = DisplayPtr-> Next;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// Estes são valores x e y que representam uma vantagem de x a y
0, 1, 1, 2, 2, 0, 2, 1, 3, 2, 4, 1, 3, 4
;
// Número total de nós de 0 a 5, então os nós totais são 6
int number_of_nodes = 6;
// Este método calculará o número de arestas no gráfico
int num_edges = sizeof (gráficos)/sizeof (gráficos [0]);
// Crie o gráfico
GraphAdjacencyList Graph (gráficos, num_edges, número_of_nodes);
// exibe a lista de adjacência do gráfico
para (int k = 0; k < number_of_nodes; k++)
cout << k;
Exibir (gráfico.head_node [k]);
retornar 0;
Saída:
0 Lista de adjacência -> 1
1 Lista de adjacência -> 2
2 Lista de adjacência -> 1 Lista de adjacência -> 0
3 Lista de adjacência -> 4 Lista de adjacência -> 2
4 Lista de adjacência -> 1
5
Gráfico direcionado com bordas de peso
Lista de adjacência do gráfico direcionado
Código C ++ para a lista de adjacência do gráfico direcionado com peso
#incluir
usando namespace std;
// Sintaxe para criar um nó
Nó da estrutura
Valor int, custo;
Nó* a seguir;
;
// Isso armazenará os detalhes da borda do gráfico (fonte e destino)
Struct GraphEdge
Int Fonte, Destination, Edgeweight;
;
classe graphadjacencylist
// Crie um novo nó para a lista de adjacência
Node* getNeighbourVertex (Int Destination, Int Edgeweight,
Nó* head_node)
Nó* new_node = novo nó;
new_node-> value = destino;
new_node-> Cost = Edgeweight;
new_node-> next = head_node;
retornar new_node;
// ele armazenará o número total de nós em um gráfico
int number_of_nodes;
público:
Nó ** head_node;
GraphAdjacencyList (GraphEdge Graphedges [], int num, int number_of_nodes)
// alocação de memória dinâmica
head_node = new Node*[número_of_nodes] ();
this-> number_of_nodes = number_of_nodes;
// Inicialize o NODE DE CABEÇA para cada borda do gráfico
para (int k = 0; k < number_of_nodes; k++)
head_node [k] = nullptr;
para (int k = 0; k < num; k++)
Int Source = Graphedges [K].fonte;
Int Destination = Graphedges [K].destino;
int edgeweight = grafedges [k].peso de ponta;
Nó* new_node = getNeighbourvertex (destino, peso de ponta,
head_node [fonte]);
head_node [fonte] = new_node;
Graphadjacencylist ()
para (int k = 0; k < number_of_nodes; k++)
excluir [] head_node [k];
excluir [] head_node;
;
Void Display (Node* DisplayPtr, int k)
while (displayptr != nullptr)
cout << "(" << k << ", " <<
displayptr-> valor << ", " << displayptr->custo << ") ";
displayPtr = DisplayPtr-> Next;
cout << endl;
int main ()
GraphEdge Graphedges [] =
// (x, y, z) => são valores x e y que representam uma vantagem
// de x a y com peso w
0, 1, 4, 1, 2, 6, 2, 0, 3, 2, 1, 5, 3, 4, 8,
4, 1, 1, 3, 2, 7
;
// Número total de nós de 0 a 5, então os nós totais são 6
int number_of_nodes = 6;
// Este método calculará o número de arestas no gráfico
int num_edges = sizeof (gráficos)/sizeof (gráficos [0]);
// Crie o gráfico
GraphAdjacencyList Graph (gráficos, num_edges, número_of_nodes);
// exibe a lista de adjacência do gráfico
para (int k = 0; k < number_of_nodes; k++)
cout << k;
Exibir (gráfico.head_node [k], k);
retornar 0;
Saída:
0 (0, 1, 4)
1 (1, 2, 6)
2 (2, 1, 5) (2, 0, 3)
3 (3, 2, 7) (3, 4, 8)
4 (4, 1, 1)
5
Conclusão
Neste artigo, vimos métodos diferentes para representar o gráfico. Também vimos a matriz de incidência, que também é um método para representar a matriz do gráfico. Em seguida, discutimos outros métodos de programação C ++ para representar a lista de adjacência (gráficos direcionados direcionados e ponderados). Também estudamos gráficos direcionados e não direcionados. Também sabemos que um gráfico não direcionado é fácil de manusear em comparação com um gráfico direcionado porque um gráfico não direcionado é um gráfico bidirecional. Afinal, não depende da direção da borda como o gráfico direcionado.