DFS / BFS

02 Nov 2018 in Programming on Python

알고리즘 2. DFS / BFS

github

이론

1. DFS

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 dfs(graph, start):
    visited = []
    stack = [start]

    while stack:
        n = stack.pop()
        if n not in visited:
            visited.append(n)
            print("set(visited)=,",set(visited))
            stack += graph[n] - set(visited)
            print("stack=",stack)
            print("visited=",visited)
    return visited

dfs(graph,'A')

2. BFS

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("queue=",queue)
            print("visited=",visited)
    return visited

bfs(graph,'A')