unit 5. dfs/bfs

vertexList = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
edgeList = [(0,1), (1,2), (1,3), (3,4), (4,5), (1,6)]
 
# vertexList = ['0', '1', '2', '3', '4', '5', '6']
# edgeList = [(0,1), (0,2), (1,0) , (1,3) , (2,0) , (2,4) , (2,5) , (3,1), (4,2) , (4,6), (5,2), (6,4)]
 
graphs = (vertexList, edgeList)
 
def dfs(graphs, start):
    stack = [start]
    adjacencyList = [[] for vertex in vertexList]
    visitedList = []
 
    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])
 
    while stack:
        current = stack.pop()
        for neighbor in adjacencyList[current]:
            if neighbor not in visitedList:
                stack.append(neighbor)
        visitedList.append(current)
    return visitedList
 
def bfs(graphs, start):
    queue = [start]
    adjacencyList = [[] for vertex in vertexList]
    visitedList = []
 
    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])
 
    while queue:
        current = queue.pop()
        for neighbor in adjacencyList[current]:
            if neighbor not in visitedList:
                queue.insert(0, neighbor)
        visitedList.append(current)
    return visitedList
 
print dfs(graphs, 0)
print bfs(graphs, 0)
 

 DFS와 BFS는 동일한 구조를 지니지만 neighbor를 담는 자료구조가 stack과 queue로 다릅니다.  코드를 설명하겠습니다.

 vertex 리스트와 edge 리스트 둘을 사용하여 adjacency 리스트를 만듭니다.  adjacency 리스트는 각 vertex가 가지는 edge에 연결되어 있는 vertex들을 각각 저장합니다.  이후 start 노드를 시작으로 인접 vertex들을 저장하면서 queue나 stack을 사용하여 pop하며 depth first 또는 breadth first로 방문합니다.