인접 목록을 구현하는 C++ 프로그램

그래프의 인접 목록 표현은 연결 목록 표현입니다. 이 표현에서 우리는 리스트의 배열을 가지고 있습니다. 배열 크기는 V입니다. 여기서 V는 정점의 수입니다. 즉, 서로 다른 V개의 목록을 저장할 배열이 있다고 말할 수 있습니다. 목록 헤더가 정점 u이면 u의 모든 인접 정점을 보유한다는 것을 의미합니다.

인접 목록 표현의 복잡성

• 이 표현은 무방향 그래프의 경우 O(V+2E), 방향 그래프의 경우 O(V+E)를 사용합니다. 모서리 수가 늘어나면 필요한 공간도 늘어납니다.

입력 :

출력 :

알고리즘

add_edge(adj_list, u, v)

입력 :edge {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