인접 리스트

• 인접 리스트(adjacency List)는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미합니다.

간단한 예를 들어 아래와 같은 그래프가 있을 때

이런 식으로 표현할 수 있다.

C++ 로 구현한 인접리스트

#include<bits/stdc++.h>
using namespace std;
const int V = 4;
vector<int> adj[V];
int main(){
	adj[0].push_back(1);
	adj[0].push_back(2);
	adj[0].push_back(3);
	adj[1].push_back(0);
	adj[1].push_back(2);
	adj[2].push_back(0);
	adj[2].push_back(1);
	adj[3].push_back(0);
	for(int i = 0; i < 4; i++){
		cout << i << " :: ";
		for(int there : adj[i]){
			cout << there << " ";
		}
		cout << '\\n';
	}
// 이렇게도 할 수 있다.
	for(int i = 0; i < 4; i++){
		cout << i << " :: ";
		for(int j = 0; j < adj[i].size(); j++){
			cout << adj[i][j] << " ";
		}
		cout << '\\n';
	}
}
/*
0 :: 1 2 3
1 :: 0 2
2 :: 0 1
3 :: 0
*/

• 인접리스트가 아닌 vactor로 구현한 이유

앞의 코드는 vector로 구현했는데 인접리스트인 list로 구현해도 되고, vector로 구현해도 된다.

이는 연결리스트와 vector의 연산 시간복잡도 차이를 보면 된다.

• 연결리스트의 시간 복잡도
• n번째 인덱스에 삽입, 삭제 : O(1)
• 마지막 요소에 삽입, 삭제 : O(1)