너비우선탐색, data 탐색을 할 때 너비를 기준(특정노드에 인접해있는 모든 노드들을 탐색대상으로 설정)으로 탐색을 하는 탐색방법의 일종이다.
최단거리탐색 및 미로찾기 등 경로탐색에 사용할 수 있으며, Queue 자료구조를 이용하면, 자료구조의 특징을 이용하여 BFS를 구현할 수 있다.
위 graph에서
queue 자료구조에 따라 다음 탐색대상은 3이고, 그 후에 2의 인접노드들이 탐색대상이 된다.
graph 상태를 표현하는 방법은 여러가지가 있는데, 본 방법에서는 객체내에서 key값과 인접노드를 연결하는 방식으로 구현하였다.
from queue import Queue
graph = {
1: [2,3],
2: [1,3,4,5],
3: [1,2,6,7],
4: [2,5],
5: [2,4],
6: [3,7],
7: [3,6]
}
def bfs(graph, start):
checked = []
q = Queue()
q.put(start)
while q.qsize() > 0:
node = q.get()
if node not in checked:
checked.append(node)
for adj in graph[node]:
q.put(adj)
return checked
print(bfs(graph, 1))
깊이우선탐색, data 탐색을 할 때 깊이를 기준(특정노드에 인접해있는 노드, 해당 노드에 인접해있는 노드 즉 노드가 연결되어있는 깊이 및 수준을 계층적으로 탐색)으로 탐색하는 방법의 일종이다.
stack 자료구조를 사용하여 구현할 수 있다.
graph = {
1: [2,3],
2: [1,3,4,5],
3: [1,2,6,7],
4: [2,5],
5: [2,4],
6: [3,7],
7: [3,6]
}
def bfs(graph, start):
checked = []
stack =[]
stack.append(start)
while stack :
node = stack.pop()
if node not in checked:
checked.append(node)
for adj in graph[node]:
stack.append(adj)
return checked
print(bfs(graph, 1))
graph structure
https://www.section.io/engineering-education/graph-data-structure-python/
bfs, dfs
https://ebbnflow.tistory.com/234
DFS/BFS
https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16