[자료구조] 그래프(Graph)

그래프의 정의

그래프는 트리를 포함하는 개념이고, 트리는 사이클을 포함하지 않는 그래프라고 볼 수 있다.
그래서 모든 트리는 그래프이지만, 모든 그래프는 트리가 아니다.

 

그래프는 정점의 모음과 간선의 모임이 결합한 것이다.

 

정점 자체는 아무것도 아니지만 이들이 간선을 통해 서로 연결되면 관계가 형성되고 이로 인해 그래프가 만들어진다.

• 인접 (adjacent) : 간선으로 연결된 두 정점을 가리켜 서로 인접 또는 이웃 관계에 있다고 말한다.
  (A, B), (A, D), (A, E), (B, C), (B, E), (C, D)가 서로 이웃 관계
• 경로(Path) : 정점 A에서 정점 C까지는 A, B, C와 A, D, C가 각각 하나의 경로
• 경로의 길이 : 정점과 정점 사이에 있는 간선의 수
  경로 A, B, C 사이에는 간선이 (A, B)와 (B, C) 2개가 있으니 길이가 2

 

• 사이클(Cycle) : 정점 하나를 두 번 이상 거치도록 되어 있는 경로, 사이클은 트리에서 볼 수 없는 특징

 

방향성 그래프(Directed Graph)와 무방향성 그래프(Undirected Graph)

• 무방향성 그래프 내의 두 정점 사이에 경로가 존재하면 이 두 정점이 연결되어 있다고 표현
• 그래프 내의 각 정점이 다른 모든 정점과 연결되어 있으면 이 그래프는 연결되었다고 표현

 

그래프 표현 방법

그래프의 인접 관계를 표현 방법에는 아래와 같은 종류가 있다.

• 인접 행렬(Adjacency Matrix)
• 인접 리스트(Adjacency List)

 

인접 행렬

무방향성 그래프에서의 인접 행렬

• 그래프의 정점 수를 N이라고 했을 때 N×N 크기의 행렬을 만든다.
• 한 정점과 또 다른 정점이 인접해 있는 경우(즉, 정점 사이에 간선이 존재하는 경우) 행렬의 각 원소를 1로 표시하고 인접해 있지 않은 경우 0으로 표시
• 주 대각선을 기준으로 대칭(symmetric)을 이룸

 

방향성 그래프에서의 인접 행렬

• 방향성 그래프에서의 정점은 자신이 직접 간선을 통해 가리키고 있는 정점에 대해서만 인접해 있다고 표현
• 아래 그림에서 정점 1은 정점 2, 3, 4, 5에 인접해 있지만 3, 4는 인접한 정점이 하나도 없음

 

 

인접 리스트

그래프 내 각 정점의 인접 관계를 표현하는 리스트

 

무방향성 그래프에서의 인접 리스트

• 각 정점이 자신과 인접한 모든 정점의 목록을 리스트로 관리
• 모든 정점을 죽 늘어놓고 각 정점의 인접 정점을 옆에 나열
• 인접 정점들끼리 리스트로 연결한 후 이를 각 정점에 연결

 

방향성 그래프에서의 인접 리스트

• A -> B 와 같이 방향성이 있을 때는 A의 인접리스트에 B 원소만 추가한다.

 

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

인접 행렬
장점 - 정점 간의 인접 여부를 빠르게 알 수 있음
단점 - 인접 관계를 행렬 형태로 저장하기 위해 사용하는 메모리의 양이 ‘정점의 크기×N²’ 만큼 커짐

인접 리스트
장점 - 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적음
단점 - 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색이 필요

 

둘 다 어느 쪽도 장점이 압도적으로 많지 않다.

따라서 어느 자료구조를 선택할 것인가는 구현하고자 하는 프로그램의 목적에 따라 결정해야 한다.

 

그래프 순회 기법

reference : https://lemidia.github.io/

DFS(Depth First Search)

DFS에는 스택을 이용한 방법과 재귀를 이용한 방법이 있지만 이 글에서는 스택을 이용한 방법을 다룬다.

방문할 인접 정점들을 저장할 Stack과 정점들의 방문 표시를 할 visited[] 배열을 선언한다.
스택을 이용한 DFS 알고리즘은 다음과 같은 순서로 실행된다.

1. 탐색을 시작할 스타팅 노드를 스택에 넣는다.
2. 스택이 빈 공간이 아닐 때 까지 다음을 실행한다.
3. 스택에서 정점 하나를 꺼내 방문하지 않았으면 방문 표시를 하고 그 정점에 인접한 모든 정점을 스택에 넣는다.(방문 하지 않은 정점들만)
4. 2번으로 간다.

 

아래의 예는 현재 정점과 인접한 정점이 여러개면 번호가 작은 순서대로 방문한다.
물론 번호가 큰 순서대로 방문할 수도 있다.

탐색은 0번 정점부터 시작한다고 가정한다.

---

탐색을 시작할 0번 정점을 스택에 넣는다.

스택에서 가장 위에있는 원소를 하나 꺼낸다. (여기서는 제일 왼쪽 칸이 top이다.)

0번 정점을 방문표시 하고 0번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.
(0번 정점과 1, 2, 3번 정점이 인접해 있다.) 

---

위의 방문 우선순위에 따라 인접한 정점이 여러개면 번호가 [작은 순서대로] 방문해야 하므로 3, 2, 1순으로 스택에 삽입한다. (후입 선출)

---

계속해서, 스택에서 가장 위에있는 1번 정점을 꺼낸다. 

1번 정점을 방문표시 하고 1번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

여기서는 2번 정점을 스택에 삽입한다.

---

그 다음, 스택에서 가장 위에있는 2번 정점을 꺼낸다.

2번 정점을 방문표시 하고 2번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

여기서는 4번 정점을 스택에 삽입한다.

---

그 다음, 스택에서 가장 위에있는 4번 정점을 꺼낸다.

4번 정점을 방문표시 하고 4번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

4번 정점과 인접한 정점 중에서는 방문하지 않은 정점들이 없으므로 다음 스탭으로 간다.

---

그 다음, 스택에서 가장 위에있는 3번 정점을 꺼낸다.

3번 정점을 방문표시 하고 3번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

3번 정점과 인접한 정점 중에서는 방문하지 않은 정점들이 없으므로 다음 스탭으로 간다.

스택이 모두 비었으니 알고리즘을 끝낸다.
스택을 이용한 DFS의 방문순서는 0 1 2 4 3 순이다.

 

BFS(Breadth First Search)

BFS는 큐를 이용하여 탐색한다.

위에서 보이는 트리에서 정점들의 번호는 너비우선탐색을 적용한 뒤 정점들의 방문 순서와 같다.
1번 정점을 루트로 하여 탐색을 시작하면, 1번 정점을 방문하고 그 인접한 정점 2, 3, 4를 순서대로 방문한다.
그 다음 레벨의 5, 6, 7, 8을 순서대로 방문하고 그 다음 레벨 9, 10, 11, 12순으로 방문하게 된다.

가정
현재 방문하고 있는 정점에서 인접한 왼쪽 간선을 오른쪽 간선보다 먼저 선택한다.
정점들의 방문은 중복되지 않는다.
1번 정점 부터 탐색을 시작한다.

 

먼저 1번 정점을 루트로 하여 BFS 탐색을 시작한다.

---

1번 정점을 큐에 넣는다.
Queue: [1]

---

큐에서 제일 앞에 있는 1번을 pop하고, 1번 정점을 방문한다.
1번 정점과 인접한 정점 중에서 방문하지 않은 2, 3, 4번을 순서대로 큐에 넣는다.
Queue: [2, 3, 4]

---

큐에서 제일 앞에 있는 2번을 pop하고, 2번 정점을 방문한다.
2번 정점과 인접한 정점 중에서 방문하지 않은 5, 6번을 순서대로 큐에 넣는다.
Queue: [3, 4, 5, 6]

---

큐에서 제일 앞에 있는 3번을 pop하고, 3번 정점을 방문한다.
3번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [4, 5, 6]

---

큐에서 제일 앞에 있는 4번을 pop하고, 4번 정점을 방문한다.
4번 정점과 인접한 정점 중에서 방문하지 않은 7, 8번을 순서대로 큐에 넣는다.
Queue: [5, 6, 7, 8]

---

큐에서 제일 앞에 있는 5번을 pop하고, 5번 정점을 방문한다.
5번 정점과 인접한 정점 중에서 방문하지 않은 9, 10번을 순서대로 큐에 넣는다.
Queue: [6, 7, 8, 9, 10]

---

큐에서 제일 앞에 있는 6번을 pop하고, 6번 정점을 방문한다.
6번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [7, 8, 9, 10]

---

큐에서 제일 앞에 있는 7번을 pop하고, 7번 정점을 방문한다.
7번 정점과 인접한 정점 중에서 방문하지 않은 11, 12번을 순서대로 큐에 넣는다.
Queue: [8, 9, 10, 11, 12]

---

큐에서 제일 앞에 있는 8번을 pop하고, 8번 정점을 방문한다.
8번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [9, 10, 11, 12]

---

큐에서 제일 앞에 있는 9번을 pop하고, 9번 정점을 방문한다.
9번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [10, 11, 12]

---

큐에서 제일 앞에 있는 10번을 pop하고, 10번 정점을 방문한다.
10번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [11, 12]

---

큐에서 제일 앞에 있는 11번을 pop하고, 11번 정점을 방문한다.
11번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [12]

---

큐에서 제일 앞에 있는 12번을 pop하고, 12번 정점을 방문한다.
12번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [ ]

큐가 비었으므로 너비우선탐색(BFS)가 완료되었다.