연결 목록을 사용하여 그래프를 나타내는 C++ 프로그램

그래프의 발생 행렬은 메모리에 저장할 그래프의 또 다른 표현입니다. 이 행렬은 정방 행렬이 아닙니다. 입사 행렬의 순서는 V x E입니다. 여기서 V는 정점의 수이고 E는 그래프의 가장자리 수입니다.

이 행렬의 각 행에 정점을 배치하고 각 열에 모서리를 배치합니다. 에지 e {u, v}에 대한 이 표현에서는 e열의 u 및 v 위치에 대해 1로 표시됩니다.

인접 행렬 표현의 복잡성

• 입사 행렬 표현은 계산되는 동안 O(V x E) 공간을 차지합니다. 완전한 그래프의 경우 모서리 수는 V(V-1)/2입니다. 따라서 입사 행렬은 메모리에서 더 많은 공간을 차지합니다.

입력:

출력:

알고리즘

add_edge(adj_list, u, v)

입력 − 간선 {u,v}의 u와 v, 그리고 인접 목록

출력 − 그래프 G

Begin
   Append v into the list at index u
   Append u into the list at index v
End

예제 코드

#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void displayAdjList(list<int> adj_list[], int v) {
   for(int i = 0; i<v; i++) {
      cout << i << "--->";
      list<int> :: iterator it;
      for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
         cout << *it << " ";
      }
      cout << endl;
   }
}
void add_edge(list<int> adj_list[], int u, int v) {    //add v into the list u, and u into list v
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   //create an array of lists whose size is 6
   list<int> adj_list[v];
   add_edge(adj_list, 0, 4);
   add_edge(adj_list, 0, 3);
   add_edge(adj_list, 1, 2);
   add_edge(adj_list, 1, 4);
   add_edge(adj_list, 1, 5);
   add_edge(adj_list, 2, 3);
   add_edge(adj_list, 2, 5);
   add_edge(adj_list, 5, 3);
   add_edge(adj_list, 5, 4);
   displayAdjList(adj_list, v);
}

출력

0--->4 3
1--->2 4 5
2--->1 3 5
3--->0 2 5
4--->0 1 5
5--->1 2 3 4