Python 題目

PROBLEM

深度優先搜尋 (DFS)

一題一題刷

概念

深度優先搜尋是一種樹的遍歷方式，會先遞迴地訪問子節點，再訪問兄弟節點。

程式碼實作

from collections import defaultdict

def dfs(Tree, now_node):
    print(now_node, end=" ")  # 先訪問當前節點
    for next_node in Tree[now_node]:  # 再遞迴訪問所有子節點
        dfs(Tree, next_node)

# 建立樹結構
tree = defaultdict(list)
root = ""

# 讀取輸入建立樹
while True:
    try:
        st, *sts = input().split()
        if root == "":
            root = st  # 第一個輸入的節點為根節點
        tree[st].extend(sts)  # 將子節點加入父節點的列表
    except:
        break

dfs(tree, root)

特點