인접 행렬

---

정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬

시간복잡도

• 간선 1개 찾기: O(1)
• 모든 간선 찾기: O(v^2)

공간복잡도

• O(V^2)

코드

// 인접행렬
const int v = 10;
bool adj_matrix[v][v];

// 간선 1개 찾기
adj_matrix[1][2];

// 모든 간선 찾기
for(int i = 0; i < v; i++) {
	for(int j = 0; j < v; j++) {
    	adj_matrix[j][i];
    }
}

인접 리스트

---

정점과 간선의 관계를 나타내는 연결 리스트

시간복잡도

• 간선 1개 찾기: O(V)
• 모든 간선 찾기: O(V + E)

  인뜻 생각해보면 1번에서 2번 정점으로 간선 여부를 확인하려면 adj_list[1][2]로도 접근이 가능할 것 같다. 그러나 adj_list[1]의 백터의 2번쨰 원소는 정점의 수를 의미하지 않는다. 그저 삽입 순서를 의미할 뿐이다. 따라서 1번 정점에 연결된 정점을 순회를 통해 확인해야 함으로 O(V)인 것이다.

공간복잡도

• O(V + E)

코드

// 인접 리스트
const int v = 10;
vector<int> adj_list[v];

// 간선 1개 찾기
for(int i = 0; i < v; i++) {
	adj_list[1][i];
}

// 모든 간선 찾기
for(int i = 0; i < v; i++) {
	for(int e : adj_list[i]) {
    	e
    }
}

인접 행렬과 리스트 비교

---

그래프가 조밀(dense)할 때는 인접 행렬을 사용하는 것이 유리하고 희소(sparse)할 때는 인접 리스트를 사용하는 것이 유리하다.

	인접행렬	인접리스트
시간복잡도(간선 한개 찾기)	O(1)	O(V)
시간복잡도(간선 모두 찾기)	O(V^2)	O(V + E)
공간복잡도	O(V^2)	O(V + E)