13. 그래프 순회 (Graph Traversal)

순회는 그래프의 모든 간선과 노드를 탐색하는 체계적인 절차이다. 대표적으로 깊이우선탐색과 넓이우선탐색이 있다.

깊이 우선 탐색^{Depth First Search: DFS}

그래프를 순회하기 위해 사용되는 일반적인 방법이다. DFS를 통해 아래와 같은 것들을 수행할 수 있다.

• 그래프의 모든 간선, 노드 방문하기
• 그래프 G가 연결 그래프인지 결정하기
• 그래프 G의 연결 요소들을 계산하기
• 그래프 G의 신장 숲 계산하기

$n$개의 정점과 $m$개의 간선을 갖는 그래프에 대한 DFS는 $O(n+m)$ 시간이 소요된다.

또한, DFS를 확장하면 아래의 것들도 수행이 가능하다.

• 두 개의 주어진 정점 사이의 경로를 찾아 보고하기
• 그래프 내 사이클 찾기

그래프의 DFS는 이진트리에 대한 선위순회와 유사하다.

DFS 코드

def DFS(G):
    for e in G.edges:
        I(e) = Fresh # 방문하지 않았음으로 초기화
    for u in G.vertices:
        I(u) = Fresh # 초기화
    for v in G.vertices:
        if I(v) == Fresh: # 방문한 적 없는 노드에 방문
            rDFS(G, v)
            
def rDFS(G, v):
    I(v) = Visited # 노드 방문함
    for e in v.incidentEdges: # 인접 간선들
        if I(e) == Fresh:
            w = opposite(v, e) # 간선이 연결된 노드
            if I(w) == Fresh: # 해당 노드에 방문한 적 없으면
                I(e) = Tree # 트리로 사용 중, 즉 rDFS(G, w)를 실행시키는 데 기여중인 간선이란 뜻
                rDFS(G, w)
            else:
                I(e) = Back # 이전에 사용 완료된, 후향 간선

DFS 특징

rDFS는 rDFS가 시작된 v로부터 연결된 모든 간선과 노드를 방문하며, rDFS가 탐색한 경로는 하나의 신장 트리를 이룬다. (DFS 트리라 한다.)

DFS를 확장하여 연결성 검사, 경로 찾기, 싸이클 찾기 등을 수행할 수 있다.

너비 우선 탐색^{Breadth First Search: BFS}

너비 우선 탐색은 그래프를 탐색하기 위한 일반적인 방법 중 하나로, DFS와 같이 아래의 일들을 수행할 수 있다.

• 그래프의 모든 간선, 노드 방문하기
• 그래프 G가 연결 그래프인지 결정하기
• 그래프 G의 연결 요소들을 계산하기
• 그래프 G의 신장 숲 계산하기

BFS 역시 $O(n+m)$의 시간 복잡도를 가지며, 확장하면 아래의 일들을 수행할 수 있다.

• 두 개의 노드 사이의 최소 간선을 사용하는 경로 찾기
• 그래프 내의 단순 싸이클 찾기

BFS는 이진 트리에 대한 레벨 순회와 유사하다.

BFS 코드

def BFS(G):
    for e in G.edges:
        I(e) = Fresh
    for u in G.vertices:
        I(e) = Fresh
    for v in G.vertices:
        if I(v) == Fresh:
            BFS1(G, v) # 여기까진 DFS랑 똑같음
    
def BFS1(G, v):
    L = list()
    L[0] = list() # Level0의 빈 리스트
    L[0].append(v)
    l(v) = Visited
    i = 0
    while !isEmpty(L[i]): 
        L[i+1] = list() # Level i+1 만들고
        for v in L[i]: # Level i 의 모든 노드 탐색
            for e in v.incidentEdges: # 인접 엣지
                if I(e) == Fresh:
                    w = opposite(v, e) # 엣지 반대편 노드
                    if I(w) == Fresh: # 해당 노드 방문한 적 없으면
                        I(e) = Tree
                        I(w) = Visited
                        L[i+1].append(w)
                    else:
                        I(e) = Cross # 교차 간선
        i += 1

BFS 특징

BFS 역시 모든 간선과 노드를 방문하며, 탐색한 경로가 신장 트리가 된다. BFS를 특화하여, 다음 문제들을 해결할 수 있다.

• 그래프 G의 연결요소들 계산하기
• G의 신장숲을 계산하기
• G 내의 단순 싸이클 찾기 혹은 G가 숲임을 알아내기
• G 내의 두 노드 사이에 최소 간선 경로를 찾거나, 경로가 없음을 밝히기

후향 간선과 교차 간선

DFS와 BFS 과정에서, 후향 간선이나 교차 간선이 생길 수 있다.

• 후향 간선: 간선 (v,w)에서, w가 트리에서 v의 조상
• 교차 간선: 간선 (v,w)에서, w가 v와 트리의 같은 레벨 혹은 다음 레벨에 존재

DFS와 BFS의 응용

응용	DFS	BFS
신장숲 연결 요소 경로 싸이클	가능	가능
이중 연결	가능
최단 경로		가능