BFS

출처:https://www.fun-coding.org/Chapter18-dfs-live.html

 

BFS : 너비 우선 탐색 

정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다.

 

 

시간복잡도 :

노드수:V

간선수:E

O(V+E)

 

 

graph=dict()

 

graph['A']=['B','C']

graph['B']=['A','D']

graph['C']=['A','G','H','I']

graph['D']=['B','E','F']

graph['E']=['D']

graph['F']=['D']

graph['G']=['C']

graph['H']=['C']

graph['I']=['C','J']

graph['J']=['I']

 

BFS의 알고리즘 표현

2개의 큐를 활용한다.

 

def bfs( 딕셔너리, 처음원소)

큐2개 선언

시작노드 need_visit에 넣고 시작하기

 

while need_visit이 빌때까지

   첫원소를 빼낸다.(왼쪽에서 빼내기)

   그원소가 visited에 없으면 

   append후 

   need_visit의 오른쪽에 원소 넣기.

 

 

BFS도 마찬가지로 extend( reversed( graph[node]) ) 로 바꾸면 후위순회로 변경된다.

 

 

def bfs( graph , start):
    need_visit=[start]
    visited=[]

    while need_visit:
        node=need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

graph=dict()

graph['A']=['B','C']
graph['B']=['A','D']
graph['C']=['A','G','H','I']
graph['D']=['B','E','F']
graph['E']=['D']
graph['F']=['D']
graph['G']=['C']
graph['H']=['C']
graph['I']=['C','J']
graph['J']=['I']

print (bfs(graph,'A') )