Alogrithm[5]:⭐⭐ - Graph Traversals(DFS and BFS)

Graph Traversal(그래프 순회)

그래프의 모든 vertices와 edges(또는 nodes와 branches)를 검사함으로써 그래프를 탐색하는 과정 또는 절차.

대표적인 알고리즘으로 DFS(깊이우선탐색)와 BFS(너비우선탐색)가 있다.

Graph Traversal의 활용

그래프의 Reachablity에 대한 문제에 활용.

• u에서 v로가는 path가 존재하는지 계산
• u에서 v로가는 shorted path 계산
• 그래프 G가 connected인지 계산
• Spinning tree 계산
• G가 cycle인지 계산
• G가 directed인 경우, verted s에서 reachable한 모든 vertices 계산
• G가 directed인 경우, G가 acyclic인지 계산

DFS

1. Vertex s 에서 시작. current 는 v
2. s에서 reachable한 다른 vertices를 검사
3. 만약 reachable한 vertex u가 visited 상태면 ignore.
4. unvisited라면 u를 visited 상태로 변경하고 current를 u로 변경.
5. 1을 반복.(Recursively)

Python Implemenation

Graph가 adjacency map으로 주어진 경우, queue와 stack을 이용하여 DFS를 구현할 수 있다.

def dfs(G, s):
    visited_queue, unvisited_stack = [], [s]
    while unvisited_stack:
        current = unvisited_stack.pop()
        if current not in visited_queue:
            visited_queue.append(current)
            unvisited_stack.extend(G[current])
    # All vertices reachable from vertex s
    return visited_queue

BFS

1. vertex s에서 시작. current는 s
2. current의 인접 vertices를 모두 visit.
3. current의 인접 vertex u로 이동. current는 u
4. 2를 반복.

Python Implemenation

Graph가 adjacency map으로 주어진 경우, 두 개의 Queue를 이용하여 BFS를 구현할 수 있다.

def bfs(G, s):
    visited_q, unvisited_q = [], [s]
    while unvisited_q:
        current = unvisited_q.pop(0)
        if current not in visited_q:
            visited_q.append(current)
            unvisited_q.extend(G[current])
    return visited_q