BFS와 DFS

그래프 용어 정리

• Subgraph: 그래프 G의 서브그래프 S에 대해, S의 정점과 간선은 G의 정점과 간선의 subset이다.
  • Spanning subgraph: G의 모든 정점을 포함하는 Subgraph
• Connected graph: 임의의 두 정점 사이에 반드시 path가 존재하는 그래프
• Connected component: Maximal connected subgraph
• Tree: 사이클이 없는 connected graph
• Forest: 사이클이 없는 무향그래프, Forest의 connected components는 각각 트리이다.
• Spanning tree: 트리인 Spanning subgraph, 한 그래프에 대해 여러가지 모습으로 존재할 수 있다.
  • 그래프의 Spanning forest는 forest인 spanning subgraph이다.

 

 

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

BFS는 그래프 탐색 기법으로, 그래프 G에서의 BFS는 다음 네 가지 목적을 달성한다.

• 모든 정점과 간선 방문
• G의 connected 여부 확인 (모든 정점 사이에 path가 존재한다)
• Connected components(정점, 간선) 찾기
• G의 스패닝 트리 (혹은 forest) 찾기

시간복잡도는 O(n + m)이며, 최단거리 탐색이나 simple cycle 찾기 등에 사용할 수 있다.

 

 

BFS 알고리즘

1. 모든 정점과 간선의 Label을 UNEXPLORED로 설정한다.

2. 모든 정점 중 어떤 정점 s에 대해 Label이 UNEXPLORED라면 s에서 탐색을 시작한다.

3. s의 Label을 VISITED로 설정하고, sequence L0에 정점 s를 추가한다.

4. 반복문의 i번째 단계에서, L_i가 빌 때까지 L_i+1에 L_i의 정점들에 대한 UNEXPLORED 정점들을 추가한다.

 

BFS(Graph& G):
    Input: graph G
    Output: Labeling & Partition of vertices of G

for u : G.vertices():
    u.setLabel( UNEXPLORED )
for e : G.edges():
    e.setLabel( UNEXPLORED )
for v : G.vertices():
    if v.getLabel() == UNEXPLORED: BFS(G, v)

BFS(Graph& G, Vertex& s):

L₀ = new empty sequence
L₀.pushBack(s)
i = 0

while not L_i.empty():
    L_i+1 = new empty sequence
    for v : L_i.elements():
        for e : v.incidentEdges():
            if e.getLabel() == UNEXPLORED:
                w = e.opposite()
                if w.getLabel() == UNEXPLORED:
                    e.setLabel( DISCOVERY )
                    w.setLabel( VISITED )
                    L_i+1.pushBack(w)
                else:
                    e.setLabel( CROSS )
    i += 1

 

Properties

# Gs: connected component of s

 

1. BFS(G, s)는 Gs의 모든 정점과 간선을 방문한다.

2. BFS(G, s)를 통해 DISCOVERY EDGE로 label 된 간선들은 Gs의 스패닝 트리 Ts를 이룬다.

3. Li의 정점 v에 대해, Ts에서 s - v를 잇는 path는 i개의 간선으로 이루어져 있고, Gs에서 s - v를 잇는 모든 path는 최소한 i개의 간선으로 이루어져 있다.

 

 

Analysis

Vertex, Edge Labeling: O(1)

총 시간복잡도: O(n+m) # Adjacency list structure

모든 Vertex는 UNEXPLORED, VISITED로 두 번 label 된다

모든 Edge는 UNEXPLORED, DISCOVERY | CROSS로 두 번 label 된다

각 Vertex는 sequence Li에 한 번 삽입된다

각 Vertex의 incidenEdges() 함수는 한 번 호출된다

 

 

Depth-First Search (깊이우선탐색)

DFS는 그래프 탐색 기법으로, 그래프 G에서의 DFS는 다음 네 가지 목적을 달성한다.

• 모든 정점과 간선 방문
• G의 connected 여부 확인 (모든 정점 사이에 path가 존재한다)
• Connected components 찾기
• G의 스패닝 forest 찾기

시간복잡도는 O(n + m)이며, 두 정점간 path 찾기, cycle 찾기, 이진트리에서의 Euler tour를 할 수 있다.

 

 

DFS 알고리즘

1. 모든 정점과 간선의 Label을 UNEXPLORED로 설정한다.

2. 모든 정점 중 어떤 정점 v에 대해 Label이 UNEXPLORED라면 v에서 탐색을 시작한다.

3. v의 label을 VISITED로 설정하고, v의 incident Edges에 대해 opposite의 label이 UNEXPLORED인지 확인한다.

4. 그렇다면 e는 DISCOVERY edge 이고, opposite에서 재귀적 탐색을 시작한다.

5. 아니라면 e는 BACK edge 이다.

 

DFS(Graph& G):
    Input: graph G
    Output: Labeling of the edges of G

for u : G.vertices():
    u.setLabel( UNEXPLORED )
for e : G.edges():
    e.setLabel( UNEXPLORED )
for v : G.vertices():
    if v.getLabel() == UNEXPLORED: DFS(G, v)

DFS(Graph& G, Vertex& v):
    Input: graph G, start vertex v
    Output: v의 connected component에 속하는 edges에 대한 labeling (discovery, back)

for e : G.incidentEdges(v):
    if e.getLabel() == UNEXPLORED:
        w = e.opposite(v)
        if w.getLabel() == UNEXPLORED:
            e.setLabel( DISCOVERY )
            DFS(G, w)
        else:
            e.setLabel( BACK )

 

Properties

1. DFS(G, v)는 v의 connected component를 모두 방문한다.

2. DFS(G, v)를 통해 DISCOVERY EDGE로 label 된 간선들은 v의 connected component의 스패닝 트리 Ts를 이룬다.

 

 

Analysis

Vertex, Edge Labeling: O(1)

총 시간복잡도: O(n+m) # Adjacency list structure

모든 Vertex는 UNEXPLORED, VISITED로 두 번 label 된다

모든 Edge는 UNEXPLORED, BACK 으로 두 번 label 된다

각 Vertex의 incidenEdges() 함수는 한 번 호출된다