深度優先ナビゲーション(DFS:Depth First Search)

深度優先ナビゲーション(DFS)とは?

1つのノード上でそのノードの深さ上のすべてのノードを検索し、次の幅上のノードを検索するアルゴリズム.(BFSとは反対)

深度優先ナビゲーション(DFS)の特徴

深度優先ナビゲーション(DFS)の原理

深度優先ナビゲーション(DFS)Pythonコードの実装

def DFS(graph, start_node):
    visited = []
    stack = [start_node]

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

def DFS(graph, start, visited=[]):
    
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            DFS(graph, node, visited)
    
    return visited```