BFS

깊이1     A
깊이2   B   C
깊이3  D  E  F

import queue

#graph표현 방식으로는 인접리스트와 인접행렬이있다.
#노드개수에 비해 엣지 개수가 훨씬 적은 그래프라면 인접 행렬보다는 인접리
#스트를 사용하여 탐색하는게 효율적이다.
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def bfs(graph, start):
    visited =[]
    queue = [start]
    while queue:
    n = queue.pop(0)
    if n not in visited:
        visited.append(n)
        queue +=graph[n] -set(visited)
    print(visited)
return visited

def bfs_paths(graph, start, goal):
    queue = [(start,[start])]
    result = []

while queue:
    n,path = queue.pop(0)
    #print(path)
    if n ==goal:
        result.append(path)
    else:
        for m in graph[n]-set(path):
            queue.append((m,path+[m]))
            print(queue)
return result

bfs(graph,'A')
print(bfs_paths(graph,'A','F'))