그래프의 인접 리스트(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의 인접 리스트
시작
인덱스 u에 해당하는 리스트에 v를 추가
인덱스 v에 해당하는 리스트에 u를 추가
끝
C++ 예제 코드
아래 코드는 C++의 STL list 컨테이너를 활용하여 무방향 그래프의 인접 리스트를 구현한 예제입니다. 정점은 총 6개이며, 각 간선을 추가한 뒤 전체 인접 리스트를 출력합니다.
#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) { // 리스트 u에 v를, 리스트 v에 u를 추가
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
int v = 6; // 그래프에는 6개의 정점이 있음
// 크기가 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
출력 결과에서 각 행은 특정 정점에서 시작해 도달할 수 있는 인접 정점들을 보여줍니다. 예를 들어 정점 0은 정점 4와 3에 연결되어 있음을 확인할 수 있습니다. 이처럼 인접 리스트는 그래프의 구조를 직관적으로 표현하면서도 메모리를 효율적으로 사용할 수 있는 대표적인 그래프 자료구조입니다.