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

앞서 두 글에서 트리에 대해 알아보았다.

[자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등)

[자료구조] 트리 (Tree) - 이진 트리 순회 (Binary Tree Traversal) | 트라이 (Trie, Prefix Trees)

이 글에서는 그래프에 대해 정리해보자.

---

그래프란

트리는 그래프의 부분집합이다. 트리는 사이클이 없는 그래프이기 때문이다.

 

그래프는 노드와 엣지로 이루어져있다.

 

그래프에서 모든 vertex에 경로가 있는 경우 connected graphs라고 한다.

 

그리고 사이클이 없는 그래프를 acyclic graph라고 한다.

---

그래프 구현하기

그래프를 구현하는 방법은 크게 두 가지로 인접 리스트와 인접 행렬이 있다.

1) Adjacency List (인접 리스트)

Adjacency List는 아래와 같이 구현할 수 있다.

class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}

Graph 클래스를 구현하는 대신 배열이나 해쉬 테이블을 사용하여 그래프의 모든 노드를 저장해도 된다.

 

모든 노드를 저장하는 이유는 트리와는 다르게 한 노드에서 시작해서 그래프의 모든 노드에 도달할 수 있다는 보장이 없기 때문이다.

 

Node 클래스에는 인접 노드를 표시한다.

 

2) Adjacency Matrices (인접 행렬)

인접 행렬은 말 그대로 행렬로 표시한 것으로 nxn 크기의 행렬을 가진다. (n: 노드의 개수)

 

행렬의 (i,j)는 노드 i와 노드 j의 엣지가 존재하는지 true 혹은 1로 나타낸다.

 

undirected graph (양방향 그래프)의 경우 행렬은 대칭적이다.

 

Adjacency List처럼 BFS를 구현할 수는 있지만 리스트를 사용한 방식보다는 덜 효율적일 수 있다. 왜냐하면 각 노드의 인접 노드만 방문하면 되는 리스트와 달리 행렬에서는 모든 노드와의 엣지를 확인해야하기 때문이다.

---

그래프 탐색

그래프를 탐색하는 방법은 크게 두 가지가 있다. - DFS, BFS

 

1) Depth-first Search

깊이를 우선으로 탐색하는 방법으로 노드의 엣지를 타고 끝까지 도달했다가 돌아와서 같은 레벨의 노드를 탐색하는 방식이다.

 

보통 모든 노드를 탐색할 때 주로 사용된다.

 

DFS 코드는 아래와 같이 구현할 수 있다. (Python)

def search(root):
    if root is None:
    	return
    visit(root)
    root.visited = True
    for node in root.adjacent:
    	if not node.visited:
            search(node)

2) Breadth-First Search (BFS) 너비 우선 탐색

같은 레벨의 노드를 순서로 탐색하는 방법이다.

 

보통 최단거리를 찾을 때 사용된다.

 

BFS 코드 구현은 아래와 같다. (Python)

def search(root):
    queue = new Queue()
    root.marked = True
    queue.enqueue(root)
    
    while not queue.isEmpty():
    	node = queue.dequeue()
        visit(node)
        for n in node.adjacent:
            if not n.marked:
                n.marked = True
                queue.enqueue(n)

BFS 코드 구현에서는 큐를 사용한다는 점을 기억하자.

---

그래프 탐색방법에는 Bidirectional Search라고 하는 방법도 있다.

 

출발지점과 도착지점 노드 사이에 가장 짧은 path를 찾을 때 사용한다.

 

각 노드에서 두 개의 BFS를 동시에 실행하고 서치가 충돌하면 두 path를 합쳐서 최종 path를 찾는 방식이다.

 

만약 directed 그래프라면 출발 지점으로 부터는 정방향으로, 도착 지점으로부터는 역방향으로 탐색하면 된다.

 

이 방법은 BFS를 사용하는 방식보다 성능이 좋다.

 

BFS를 활용하면 k (노드의 개수) d (탐색하는 레벨) 를 가정했을 때 O(k^d) 노드를 탐색해야하는 반면

Bidirectional Search를 사용하면 2k^d/2로 O(k^d/2) 로 탐색할 수 있기 때문이다.

 

---

Reference

- Cracking the Coding Interview - Chapter 4. Trees and Graphs