[자료구조] 그래프(Graph)의 개념 및 탐색 간단하게 알아보기

그래프(Graph)의 용어

트리(Tree)와 그래프(Graph)의 차이

그래프(Graph)의 특징 : Directed, Undirected, Cyclic, Acyclic

그래프(Graph)를 표현하는 방법 : Adjacency Matrix, Adjacency List

그래프(Graph)의 탐색 : DFS(깊이 우선탐색), BFS(넓이 우선탐색)

---

그래프(Graph)의 용어

정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (0, 1, 2, 3)
간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 나타냅니다.
인접 정점(adjacent vertex) : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점1은 인접 정점)
단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3)
진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수를 뜻합니다.
진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수를 뜻합니다.

 

---

트리(Tree)와 그래프(Graph)의 차이

 

트리(Tree)는 루트와 자식노드가 있고, 노드를 연결하는 엣지(Edge)가 있다.

엣지의 방향은 위에서 아래이며, 들어오는 곳은 하나이고 나가는 곳은 여러 개가 될 수 있다.

 

트리(Tree)의 특징

 

반면, 그래프(Graph)는 엣지의 방향을 위 아래로 조정할 수 있고, 들어오는 것이 여러개가 되거나 옆 노드와 주고 받을 수도 있고, 엣지가 돌아 자기자신을 가리키며 루트의 개념도 없어진다.

간략히 보는 그래프(Graph)의 특징

 

트리(Tree)는 그래프(Graph)의 한 형태이다.

즉, 트리(Tree)는 루트가 있고 들어오는 곳이 한 개이며 사이클(Cycle)이 없고 위에서 아래로만 흐르는 그래프(Graph)이다.

 

---

그래프(Graph)의 특징 : Directed, Undirected, Cyclic, Acyclic

 

 

그래프(Graph)는 방향이 있을 수도(Directed) 있고, 없을 수도(Undirected) 있다.

여기서 트리는 Directed Graph (항상 위에서 아래로 그리기 때문에 화살표 생략) 이다.

또한, 그래프(Graph)는 노드들이 하나 이상의 서클(Circle) 을 만드는 경우(Cyclic)가 있고, 하나도 없는 경우(Acyclic)가 있다.

 

---

그래프(Graph)를 표현하는 방법 : Adjacency Matrix,  Adjacency List

 

 

- Adjacency Matrix : 그래프를 표에다가 표현하는 방법 (이차원 배열 표현)

 

 

- Adjacency List : 배열에 노드들을 나열하고 관계를 Linked List로 표현하는 방법

 

각 배열 방에 연결된 모든 노드를 (순서와 상관없이) 집어 넣고, 각 배열 방에 있는 해당 노드와 인접한 노드들을 Linke List로 나열해 저장하는 것이다.

여기서 엣지의 개수가 m개라면, 총 노드의 개수는 2m개가 된다. (두 개의 노드가 서로 연결되는 것이기 때문에)

 

---

그래프(Graph)의 탐색 : DFS(깊이 우선탐색), BFS(넓이 우선탐색)

 

 

 

 

Binary tree를 순회할 때 사용했던 방법인 inorder, preorder, postorder 가 DFS에 속한다.

DFS의 이동 경로는 자식노드의 자식노드를 깊이 탐색한 다음에 그 다음 줄기를 가서 또 자식 노드를 깊이 탐색 후 그 다음 줄기의 형제 노드를 따라간다.

BFS의 이동경로는 시작점에서 자식 노드들을 먼저 방문하고, 그 다음 자식의 자식을 방문하는 식의 레벨단위로 탐색하는 것이다.

(그래프에서의 자식노드라고 불리진 않지만, 쉽게 이해하기 위해 자식노드라 칭하였고, 정확히는 인접한 노드라고 한다.)

---

구현방법

1. DFS (Depth-First Search) : Stack

다음의 방법으로 탐색한다.
스택에서 노드를 꺼내고, 그 해당 노드의 자식노드를 전부 스택에 넣은 뒤 해당 노드는 출력한다.
여기서, 한번 스택에 넣은 자식노드는 다시 담지 않는다.
(스택은 FILO, First In, Last Out 즉, 선입 후출의 구조이다)

 

위의 예제는 0번 노드부터 시작해서 그래프를 순회해보자.

1. 0번 스택에 담는다.
2. 0번 노드를 꺼낸 뒤, 0번 노드의 자식(1번)노드를 스택에 담는다.
     0번 노드는 출력한다.
3. 1번 노드를 꺼낸 뒤, 1번 노드의 자식(2번, 3번)노드를 스택에 담는다.
     1번 노드는 출력한다.
4. 3번 노드를 꺼낸 뒤, 3번 노드의 자식(4번, 5번)노드를 스택에 담는다.
     3번 노드는 출력한다. (여기서 1번,2번은 이미 스택에 담았던 노드이기에 제외한다.)
5. 5번 노드를 꺼낸 뒤, 5번 노드의 자식(6번, 7번)노드를 스택에 담는다.
     5번 노드는 출력한다.
6. 7번 노드를 꺼낸 뒤, 7번 노드는 자식이 없으므로 바로 출력한다.
7. 6번 노드를 꺼낸 뒤, 6번 노드의 자식(8번)노드를 스택에 담는다.
     6번 노드는 출력한다.
8. 8번 노드를 꺼낸 뒤, 8번 노드는 자식이 없으므로 바로 출력한다.
9. 4번 노드를 꺼낸 뒤, 4번 노드는 스택에 안담겼던 자식이 없으므로 바로 출력한다.
10. 2번 노드를 꺼낸 뒤, 2번 노드는 스택에 안담겼던 자식이 없으므로 바로 출력한다.

 

 

 

2. BFS (Breadth-First Search) : Queue

 

다음의 방법으로 탐색한다.
큐에서 노드를 꺼내고, 그 해당 노드의 자식노드를 전부 스택에 넣은 뒤 해당 노드는 출력한다.
여기서, 한번 큐에 넣은 자식노드는 다시 담지 않는다.
(큐는 FIFO, First In, First Out 즉, 선입 선출의 구조이다)

위의 예제는 0번 노드부터 시작해서 그래프를 순회해보자.

1. 0번 큐에 담는다.
2. 0번 노드를 꺼낸 뒤, 0번 노드의 자식(1번)노드를 큐에 담는다.
     0번 노드는 출력한다.
3. 1번 노드를 꺼낸 뒤, 1번 노드의 자식(2번, 3번)노드를 큐에 담는다.
     1번 노드는 출력한다.
4. 2번 노드를 꺼낸 뒤, 2번 노드의 자식(4번)노드를 큐에 담는다.
     2번 노드는 출력한다. (여기서 1번, 3번은 이미 큐에 담았던 노드이기에 제외한다.)
5. 3번 노드를 꺼낸 뒤, 3번 노드의 자식(5번)노드를 큐에 담는다.
     3번 노드는 출력한다.
6. 4번 노드를 꺼낸 뒤, 4번 노드는 큐에 안담겼던 자식이 없으므로 바로 출력한다.
7. 5번 노드를 꺼낸 뒤, 5번 노드의 자식(6번, 7번)노드를 큐에 담는다.
     5번 노드는 출력한다.
8. 6번 노드를 꺼낸 뒤, 6번 노드는 자식(8번)노드를 큐에 담는다.     6번 노드는 출력한다.
9. 7번 노드를 꺼낸 뒤, 7번 노드는 자식이 없으므로 바로 출력한다.
10. 8번 노드를 꺼낸 뒤, 8번 노드는 자식이 없으므로 바로 출력한다.

 

 

 

이처럼 두 가지 방법으로 순회를 하면서 출력한 결과는

• DFS(0)   0  1  3  5  7  6  8  4  2
• BFS(0)   0  1  2  3  4  5  6  7  8

그래프는 트리가 아니기 때문에 0에서 시작할 필요는 없다.

3에서 시작해도 결과는 다르지만 규칙에 맞게 모든 노드들이 순회가 잘된다.

• DFS(3)   3  5  7  6  8  4  2  1  0
• BFS(3)   3  1  2  4  5  0  6  7  8

 

어떤 문제에 어떤 알고리즘 활용할지?

1) 그래프의 모든 정점을 방문해야하는 문제

DFS, BFS 

 

2) 경로의 특징을 저장하는 문제

예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다.

 

3) 최단거리를 구하는 문제

미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다.

 

4) 검색대상그래프가 많이 클때 DFS

 

5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS.