[자료구조] 그래프(Graph): 인접행렬과 인접리스트

✏️ 그래프(Graph)

👉🏻 그래프(Graph)란 노드(Node)와 간선(Edge)으로 연결관계를 표현하는 자료구조이다. 노드는 정점(Vertex)라고 불리기도 한다.

• 노드(node): 정점 (vertex)이라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge): 링크(link)라고도 하며 노드 간의 관계
• 인접 노드: (adjacent node): 하나의 노드에서 간선에 의해 직접 연결되어 있는 노드
• 차수(degree): 노드에 연결된 간선의 수
• 진입 차수(in-degree): 외부에서 오는 간선의 수
• 진출 차수(out-degree): 외부로 향하는 간선의 수
• 경로 (path): 간선을 따라갈 수 있는 길
• 경로의 길이 (length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로 (simple path): 경로 중에서 반복되는 간선이 없는 경로
• 사이클 (cycle): 시작 노드와 종료 노드가 같은 단순 경로

---

📌 그래프의 종류

👉🏻 그래프의 종류에는 무방향 그래프, 가중치가 있는 무방향 그래프, 가중치가 있는 유방향 그래프가 있다.

---

📌 그래프의 구현

👉🏻 그래프를 구현하는 방법에는 인접행렬(Adjacency Matrix)와 인접리스트(Adjacency List)가 있다.

• 인접행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

인접행렬(Adjacency Matrix)

노드의 개수가 n이라면 n*n 형태의 2차원 배열로 그래프의 연결 관계를 표현한다.
인접 행렬에서 행과 열은 노드를 의미하며, 각각의 원소들은 노드 간의 간선을 나타낸다.
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

가중치가 없는 무방향 그래프
: 연결되어 있는 경우 행렬에서 1의 값을 가지고, 연결되지 않은 경우 0의 값을 가진다. 두 개의 노드에서 간선이 동시에 연결되어 있기 때문에 인접 행렬이 대칭적 구조를 가진다.

가중치가 있는 유방향 그래프는 행렬
: 행렬에서 각 간선의 가중치 값이 저장된다. 이 경우 가중치가 0인 것과 간선이 없는 것이 구별돼야 한다.

장점: 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회할 때 O(1) 시간복잡도를 가진다.
단점: 간선의 수와 무관하게 항상 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
그래프의 모든 간선의 수를 알아내려면 인접행렬 전체를 확인해야 하므로 O(n²)의 시간이 소요된다.

인접리스트(Adjacency List)

그래프의 각 노드에 인접한 노드들을 연결리스트(Linked List)로 표현하는 방법이다.
즉, 노드의 개수만큼 인접리스트가 존재하며, 각각의 인접리스트에는 인접한 노드 정보가 저장된다. 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.

• 헤드포인터: 연결 리스트의 맨 처음 노드를 가리키는 포인터

가중치가 없는 무방향 그래프
: 그림과 같이 가중치 표현 없이 인접한 노드 정보가 저장된다.

가중치가 있는 유방향 그래프
: 종점 [노드 번호 | 간선의 가중치] 정보가 저장된다.

장점: 존재하는 간선만 관리하므로 보다 메모리 사용이 효율적이다.
단점: 두 노드를 연결하는 간선을 조회하거나 노드의 차수를 알기 위해서는 노드의 인접 리스트를 탐색해야 하므로 노드의 차수만큼의 시간이 필요하다.

💡 인접행렬과 인접리스트 비교