[C++]인접 리스트

인접 리스트란, 각 정점에 인접한(간선으로 연결된) 노드들을 연결 리스트 형태로 표현하는 방법이다.

예를 들어, 0~4의 정점과 1-2, 1-3, 3-4의 간선을 가지는 adj라는 인접 리스트가 있다고 가정하자.

인접 리스트는 다음과 같다.

adj[0] 

adj[1] -> 2 -> 3

adj[2] -> 1

adj[3] -> 1 -> 4

adj[4] -> 3

C++에서는 list라는 자료구조가 존재해 이것을 사용해 인접 리스트의 구현이 가능하다. 간선을 추가하는데 드는 시간이 동일하기 때문에 굳이 list를 사용하지 않고 vector를 사용해도 무방하다. 오히려 특정 위치를 찾는 데는 vector가 속도가 빠르기 때문에 더 유리하다 할 수 있는 부분도 존재한다.

 

다음 코드는 인접 리스트를 vector로 구현한 코드이다.

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 10;
vector<int> adj[SIZE];
	int visited[SIZE];
	
int main(){
	fill(&visited[0], &visited[SIZE], 0);
	adj[1].push_back(2);
	adj[2].push_back(1);
	adj[1].push_back(3);
	adj[3].push_back(1);
	adj[3].push_back(4);
	adj[4].push_back(3);
	for(int x = 0; x < SIZE; x++){
		cout << "adj[" << x << "]";
		for(int y = 0; y < adj[x].size(); y++){
			cout << " -> " << adj[x][y];
		}
		cout << "\n";
	}
}