Deep-First Search

Iterative

procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
          v = S.pop()
          if v is not labeled as visited:
              label v as visited
              for all edges from v to w in G.adjacentEdges(v) do 
                  S.push(w)

Recursive

procedure DFS(G,v):
      label v as visited
      for all edges from v to w in G.adjacentEdges(v) do
          if vertex w is not labeled as visited then
              recursively call DFS(G,w)

Code

"""
  procedure DFS(G,v):
      label v as visited
      for all edges from v to w in G.adjacentEdges(v) do
          if vertex w is not labeled as visited then
              recursively call DFS(G,w)
"""
def dfs(graph, start, visited=[]):
    # DFS 有三個重要元素: 
    # 1.圖(陣列或dict) 2. 起始點 3. visited list
    # 缺點: DFS 無法保證最小路徑
    visited.append(start)
    for next in graph[start]:
        if next not in visited:
            dfs(graph, next, visited)
    return visited
    
graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

dfs(graph, 'C') 
# ['C', 'A', 'B', 'D', 'E', 'F']