[C++] 인접행렬 / 인접 리스트 구현

인접 행렬 (Adjacency Matrix) 와 인접 리스트(Adjacency List)는 프로그래밍에서 그래프를 표현하는 대표적인 방식이다.

🔎 인접 행렬 Adjacency Matrix

: 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
-연결되어 있지 않은 노드의 관계는 INF(무한의 비용)이라고 작성한다.
보통 INF는 999999999 등으로 초기화한다.

ex) 다음과 같은 그래프를 인접 행렬로 표현한다면

#include <bits/stdc++.h>
#define INF 999999999 // 무한의 비용 선언

using namespace std;

// 2차원 리스트를 이용해 인접 행렬 표현
int graph[3][3] = {
    {0, 7, 5},
    {7, 0, INF},
    {5, INF, 0}
};

int main(void) {
	...
}

=>

	0	1	2
0	0	7	5
1	7	0	INF
2	5	INF	0

이와 같이 나타낼 수 있다.

🔎 인접 리스트 Adjacency List

주로 연결리스트 자료구조를 활용하여 모든 노드에 대하여 연결된 노드 정보를 차례로 연결하여 저장한다.

위와 같은 그래프를 이용하여 예를 들자면 다음과 같이 표현할 수 있다.

코드로는 :

// 행(Row)이 3개인 인접 리스트 표현
vector<pair<int, int> > graph[3];

int main(void) {
    // 노드 0에 연결된 노드 정보 저장 {노드, 거리}
    graph[0].push_back({1, 7});
    graph[0].push_back({2, 5});

    // 노드 1에 연결된 노드 정보 저장 {노드, 거리}
    graph[1].push_back({0, 7});

    // 노드 2에 연결된 노드 정보 저장 {노드, 거리}
    graph[2].push_back({0, 5});
...

❔인접 행렬과 인접 리스트의 차이점

인접 행렬	인접 리스트
모든 노드와의 관계 저장->메모리 비효율	연결된 노드와의 관계만 저장 ->메모리 효율
특정 노드가 연결되어 있는지 빠르게 확인 가능	특정 두 노드 연결 확인 느림
	(연결리스트라서) 앞에서부터 따라가며 찾아가야함