C++ 인접 리스트(Adjacency List)로 그래프 표현하기

그래프의 인접 리스트(Adjacency List) 표현법은 연결 리스트(linked list) 기반의 그래프 표현 방식입니다. 이 방식에서는 리스트들의 배열을 사용하며, 배열의 크기는 V입니다. 여기서 V는 그래프에 존재하는 정점(vertex)의 개수를 의미합니다. 다시 말해, 서로 다른 V개의 리스트를 저장할 수 있는 배열을 하나 만드는 것입니다.

만약 어떤 리스트의 헤더가 정점 u라면, 해당 리스트에는 u와 인접한 모든 정점들이 담기게 됩니다.

인접 리스트 표현의 복잡도

• 무방향 그래프의 경우 O(V+2E), 방향 그래프의 경우 O(V+E)의 공간이 필요합니다. 따라서 간선(edge)의 개수가 늘어나면, 그만큼 필요한 공간도 함께 증가하게 됩니다.

알고리즘

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