graph algorithms - bfs, dfs

그래프구조에서 기초적인 탐색알고리즘으로 이용되는 bfs, dfs를 파이썬으로 구현해보았다.

 

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

- 루트 노드에서 시작해 인접 노드를 먼저 탐색하는 방법

- 넓게 탐색

- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이용

- 재귀적으로 동작하지 않음

- 어떤 노드를 방문했었는지 여부를 반드시 검사해야함

- 큐를 이용해서 넓이부터 탐색

 

DFS = Depth First Search

- 루트 노드에서 시작해 다른 branch로 넘어가기 전 해당 branch를 깊게 완벽하게 탐색

- 모든 노드를 방문하고자 할 때 이용

- Stack 이용

 

 

 

graph_list = {1:set([3,4]),
    2:set([3,4,5]),
    3:set([1,5]),
    4:set([1]),
    5:set([2,6]),
    6:set([3,5])}
 
root_node = 1
 
 
def bfs(graph, root):
    visited = []
    queue = []
 
    queue.append(root)
 
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node]) #append처럼 데이터형을 유지하며 붙이지 않고 데이터의 element(iterable한 element)를 꺼내 붙인다.
 
    return visited
 
def dfs(graph, root):
    visited = []
    stack = []
 
    stack.append(root)
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            stack.extend(graph[node])
 
    return visited
 
 
 
def main():
    a = bfs(graph_list,root_node)
    b = dfs(graph_list,root_node)
    print('given graph : ', graph_list, ' given root : ', root_node)
    print('bfs : ', a, ' dfs : ', b)
 
if __name__ == '__main__':
    main()