Algorithm. 그래프 탐색

1. 그래프 탐색

• 그래프의 모든 정점을 빠짐없이 탐색

 

2. 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

깊이 우선 탐색(DFS)

루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

1. 시작 정점에서 한 방향을 선택해서 다음 정점으로 이동
2. 선택된 정점에서 (1)을 반복 수행하면서 계속 깊이 탐색
   • 이미 방문한 정점은 재방문 안한다.
3. 더 이상 갈곳이 없으면 부모노드로 되돌아가 다시 깊이 탐색

스택을 사용한다

DFS 재귀 호출

# G : 그래프
# v : 시작 정점
# visited : 정점의 방문 여부, False로 초기화
# G[v] : 그래프 G에서 v의 인접리스트

def dfs(G, v):
    visited[v] = True # v를 방문 표시
    visit(v) # v에 대해 작업 수행
    for w in G[v]: # v의 인접 정점에 대해서
    	if not visited[w]: # 방문하지 않았으면
        	dfs(G, w) # 재귀 호출

DFS 반복문

# S : 스택

def dfs(S, v):
    S = [v]
    while S: # 스택이 빈 상태가 아닌 동안 반복
    	v = S.pop() # 스택의 마지막 입력 원소 pop
        if v not in visted: # 방문하지 않았다면
            visited.append(v) # v를 방문 표시
            visit() # 해당 정점에 대해 필요작업 수행
            S.extend(G[v] - set(visited)) # v의 인접 정점 중 방문한 정점을 제외하고 스택에 추가
    return visited # visited 리스트에는 방문 순서대로 저장되어있다.

 

너비 우선 탐색(BFS)

• 시작 정점에서 인접한 정점을 먼저 모두 차례로 방문
• 방문했던 정점들을 다시 시작정점으로하여 앞의 과정을 반복 수행
• 재방문안함

큐를 사용한다.

# G : 그래프
# Q : 큐
# v : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화
# G[v] : 그래프 G에서 v의 인접 리스트

def bfs(Q, v):
    Q.append(v)
    visited[v] = True # v 방문표시
    visit(v) # 필요 작업 수행
    while Q: # Queue가 비어있지 않은 동안
    	v = Q.pop(0) # 제일 처음에 넣은 정점을 꺼낸다. 제일 처음 넣은 정점 = 인접 정점
        for w in G[v]: # v의 인접정점에 대해서
            if not visted[w]: # w가 방문하지 않았다면
            	Q.append(w) # 큐에 추가
                visited[w] = True # w를 방문 표시
                visit(w) # 필요 작업 수행

 

BFS 확장 알고리즘

• 너비 우선 탐색으로 시작 정점에서의 최단 경로 확인 가능

# D[] : 시작 정점에서 각 정점까지의 최단 거리 저장
# P[] : 최단 경로 트리 저장 리스트

def bfs(Q, v):
    D[v] = 0 # 출발점 거리값은 0으로 설정
    P[v] = v 
    Q.append(v)
    visited[v] = True
    visit(v)
    while Q:
    	v = Q.pop(0)
        for w in G[v]:
            if not visited[w]:
            	Q.append(w)
                visited[w] = True
                visit(w)
                D[w] = D[v] + 1 # D[v]에 +1
                P[w] = v # 각 정점에서 최단 경로 트리에서의 부모에 대한 정보 저장
                	     # v의 인접정점이 w를 최단 경로 트리에서 w의 부모노드로 설정