dfs,bfs

DFS

 

graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','G','H'],
         'D':['B'],
         'E':['B','F'],
         'F':['E'],
         'G':['C'],
         'H':['C']}

def dfs_iteration(graph, root):
    # visited = 방문한 꼭지점들을 기록한 리스트
    visited = []
    # dfs는 stack, bfs는 queue개념을 이용한다.
    stack = [root]
    
    while(stack): #스택에 남은것이 없을 때까지 반복
        node = stack.pop() # node : 현재 방문하고 있는 꼭지점
        
        #현재 node가 방문한 적 없다 -> visited에 추가한다.
        #그리고 해당 node의 자식 node들을 stack에 추가한다.
        if(node not in visited):
            visited.append(node)
            stack.extend(graph[node])
    return visited

print(dfs_iteration(graph,'A'))

결과: ['A', 'C', 'H', 'G', 'B', 'E', 'F', 'D']

 

---

BFS

 

node.pop() -> 오른쪽에서부터 차례로 제거와 반환

node.popleft() -> 왼쪽부터 차례로 제거와 반환

 

from collections import deque



def BFS(graph,root):
    visited=[]
    adj=deque([root])

    while adj:
        node=adj.popleft()
        if node not in visited:
            visited.append(node)
            adj.extend(graph[node])

    return visited


graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','G','H'],
         'D':['B'],
         'E':['B','F'],
         'F':['E'],
         'G':['C'],
         'H':['C']}

print(BFS(graph,'A'))

결과: ['A', 'B', 'C', 'D', 'E', 'G', 'H', 'F']