[Graph] DFS(Depth First Search), 깊이우선탐색

DFS,

---

깊이우선탐색은 게임에서 주로 많이 쓰인다. 

먼저, vertextList, edgeList를 만들어 adjacencyList를 만들어 준다.

adjacencyList를 만들어 주면 DFS를 이용할 수 있다 ^_^

[[1, 2],  <- 0이 연결되어 있는 vertext(1, 2)

 [0, 3], <- 1 ...

 [0, 4, 5],

 [1],

 [2, 6], 

 [4]]

 

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 dfs(graph, start):
    vertextList, edgeList = graph
    visitedVertex = []
    stack = [start]
    adjacencyList = [[] for vertex in vertextList]

    for edge in edgeList:
        adjacencyList[edge[0]].append(edge[1])

    while stack:
        current = stack.pop()
        for neighbor in adjacencyList[current]:
            if neighbor not in visitedVertex:
                stack.append(neighbor)
        visitedVertex.append(current)
    return visitedVertex

print(dfs(graphs, 0))​

허민석님의 유투브는 최고인듯