[Graph] BFS(Breadth first Search), 넓이우선탐색

[Graph] DFS(Depth first Search), 깊이우선탐색에서는 stack을 이용하고,

BFS에서는 queue를 이용하면 된다.

 

vertextList = [0, 1, 2, 3, 4, 5, 6]
edgeList = [(0, 1), (1, 0), (0, 2), (2, 0), (1, 3), (3, 1),
             (2, 4), (4, 2), (2, 5), (5, 2), (4, 6), (6, 4)]
graphs = (vertextList, edgeList)


def bfs(graph, start):
    vertextList, edgeList = graph
    visitedVertex = []
    queue = [start]
    adjacencyList = [[] for vertex in vertextList]
    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])
    
    while queue:
        current = queue.pop()
        for neighbor in adjacencyList[current]:
            if neighbor not in visitedVertex:
                queue.insert(0, neighbor)
        visitedVertex.append(current)
    return visitedVertex

print(bfs(graphs, 0))

 

* list.insert(index, value): 원하는 인덱스에 값 넣기