BFS ( Breath First Search, 너비 우선 탐색 ) python으로 구현하기

- BFS ( Breath First Search )

: Root Node 방문 후, 그 Node의 후손과 같은 level에 있는 Node들을 먼저 Search 

BFS

 

 

-  구현 방법 

1. GRAPH 표현해주기 ( python )

: Dictionary 과 List 자료형을 사용해준다
1개의 Node와 연결되어있는 Node들을 모두 다 표현해준다

# 1. GRAPH로 나타내기 - Dictionary 사용
graph={ 'A': ['B','C'],
'B':['A','D','E'],
'C':['A','F','G'],
'D':['B','H', 'I'],
'E':['B','J'],
'F':['C'],
'G':['C'],
'H':['D'],
'I':['D'],
'J':['E']
}

 

 

2. BFS 구현하기 ( python )

: Queue를 이용하여 구현한다. 

# BFS
def BFS(graph,root):
    visit=[] # 방문한 Node모음 
    queue=[]
    queue.append(root) # Root Node를 Queue에 넣어주기 

    while queue:
        node=queue.pop(0) # 제일 처음 값 꺼내기 
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node]) # 해당 Node와 연결된 Node들을 Queue에 추가
    return visit

print(BFS(graph,'A'))

 

 

< Queue에 담기는 순서 >

 

- 전체 코드

# 1. GRAPH로 나타내기 - Dictionary 사용
graph={ 'A': ['B','C'],
'B':['A','D','E'],
'C':['A','F','G'],
'D':['B','H', 'I'],
'E':['B','J'],
'F':['C'],
'G':['C'],
'H':['D'],
'I':['D'],
'J':['E']
}

# BFS
def BFS(graph,root):
    visit=[] # 방문한 Node모음 
    queue=[]
    queue.append(root) # Root Node를 Queue에 넣어주기 

    while queue:
        node=queue.pop(0) # 제일 처음 값 꺼내기 
        if node not in visit:
            visit.append(node)
            queue.extend(graph[node]) # 해당 Node와 연결된 Node들을 Queue에 추가
    return visit

print(BFS(graph,'A'))