그래프 (2) DFS, BFS, Topological Sorting

DFS

def DFS(v):
    mark v as visited # by array or something
    for unvisited_vertex in unvisted_vertices_adjacent_to_v:
        DFS(v)

위 재귀 구조는 함수 호출 스택을 쌓게 된다. 따라서 이 코드를 그대로 스택으로 구현할 수도 있다.

 

 

2021/03/13 추가) 코딩테스트 문제 풀 때는 실질적으로 이런 구조로 짜는게 편하다

def DFS(level, node, record):
    # 1. record
    record <- node
    # 2. terminte at leaf (can be ommitted if iteration in 3. do nothing
    if node is leaf:
    	backtracking process(ex: delete last node from record)
    	return
    # 3. iteration of recursion
    for children of this node:
    	DFS(level + 1, child, record)
    # 4. backtracking process
    backtracking process(ex: delete last node from record)

 

BFS

def BFS(v):
    q = empty queue
    q.enqueue(v)
    while q is not empty:
        x = q.dequeue()
        mark all vertices adjacent to x as visited
        enqueue all vertices adjacent to x

 

✅ mark와 동시에 현재 방문하고 있는 노드와 마크한 노드를 잇는 간선을 그리면 그게 spanning tree가 된다. 각각 DFS spanning tree, BFS spanning tree가 된다.

 

Topological Sorting

 

topological sorting은 cycle이 없는 connected digraph의 모든 노드들을 순서대로 진행될 수 있는 순서로 일렬로 정렬하는 방법이다. 예를 들어, digraph가 어떤 선행되어야 하는 일들과 후행되는 일들의 관계를 나타낼 때, 만약 한 번에 한 일만 할 수 있다면 어떤 일로 이 모든 일들을 할 수 있는지 topological sorting을 통해 알 수 있다(예를 들면 스타크래프트 프로토스의 모든 건물을 한 번에 한개씩 짓는 순서). 단, 당연히 한 digraph에 대해 여러가지 topological sorting의 결과가 있을 수 있다.

 

1)

def topological_sorting_1(G):
    topological_array = []
    for i in range(|V|):
        x = a node that does not have child
        topological_array.append(x)
        delete all edges that goes to x
        delete x
    tobological_array.reverse()
    return topological_array

 

2)

def topological_sorting_2(G):
    topological_array = []
    for i in range(|V|):
        x = a node that does not have parent
        topological_array.append(x)
        delete all edges from x
        delete x
    
    return topological_array

 

위 두 알고리즘은 Θ(|V| + |E|)의 시간 복잡도를 가진다.(증명생략)