葉子跟葉子間距離

 def build_graph(edges):

    graph = {}

    for u, v in edges:

        if u not in graph:

            graph[u] = []

        if v not in graph:

            graph[v] = []

        graph[u].append(v)

        graph[v].append(u)

    return graph

def find_leaves(graph):

    leaves = []

    for node, neighbors in graph.items():

        if len(neighbors) == 1:

            leaves.append(node)

    return leaves

def dfs(graph, current, target, path, visited):

    path.append(current)

    visited.add(current)

    

    if current == target:

        return True

    

    for neighbor in graph.get(current, []):

        if neighbor not in visited:

            if dfs(graph, neighbor, target, path, visited):

                return True

    

    path.pop()

    return False

def find_path(tree):

    graph = build_graph(tree)

    leaves = find_leaves(graph)

    

    if len(leaves) < 2:

        return []

    

    # 假設選擇 leaves 中的第一個和最後一個作為 start 和 end

    start = leaves[0]

    end = leaves[-1]

    

    path = []

    visited = set()

    

    dfs(graph, start, end, path, visited)

    

    return path, start, end

# 測試

tree = [[1,2],[1,3],[2,4],[3,5],[5,6]]

path, start_node, end_node = find_path(tree)

print(f"從節點 {start_node} 到節點 {end_node} 的路徑: {path}")

tree = [[1,2],[1,3],[2,4],[3,5],[5,6]]
path, start_node, end_node = find_path(tree)
print(f"從節點 {start_node} 到節點 {end_node} 的路徑: {path}")

以下是上述程式的完整解釋：

1. 程式邏輯概述

該程式用於從給定的樹結構中，找出從一個葉節點到另一個葉節點的路徑。主要步驟包括：

1. 構建鄰接表表示樹的結構。
2. 確定哪些節點是葉節點。
3. 使用深度優先搜尋（DFS）在葉節點之間找到路徑。

2. 函數說明

1. build_graph(edges)

• 功能：根據給定的邊列表（tree），構建一個無向圖（鄰接表）。
• 參數：
  • edges：表示樹中各邊的列表，例如 [[1,2],[1,3],[2,4],[3,5],[5,6]]。
• 運作方式：
  • 遍歷所有邊，確保每個節點都在鄰接表中。
  • 為每個節點加入相鄰節點。
• 輸出：返回一個表示樹的鄰接表。

示例輸出：

{
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3, 6],
    6: [5]
}

2. find_leaves(graph)

• 功能：找出圖中所有的葉節點。
• 參數：
  • graph：鄰接表。
• 運作方式：
  • 遍歷每個節點，檢查其鄰居數量，如果只有一個鄰居，就將其視為葉節點。
• 輸出：返回所有葉節點的列表。

示例輸出：

[4, 6]

3. dfs(graph, current, target, path, visited)

• 功能：使用深度優先搜尋（DFS）尋找從 current 到 target 的路徑。
• 參數：
  • graph：鄰接表。
  • current：當前搜尋的節點。
  • target：目標節點。
  • path：記錄當前尋找路徑的列表。
  • visited：已訪問過的節點集合，避免重複訪問。
• 運作方式：
  • 將當前節點加入 path，並標記為已訪問。
  • 如果找到目標節點 target，返回 True，表示成功找到路徑。
  • 遍歷所有鄰居，若鄰居未被訪問，則遞迴進行搜尋。
  • 如果沒有找到路徑，則從 path 中移除當前節點（回溯）。
• 輸出：成功找到目標節點則返回 True，否則返回 False。

4. find_path(tree)

• 功能：綜合使用上述函數，從樹中自動尋找兩個葉節點之間的路徑。
• 參數：
  • tree：樹的邊列表。
• 運作方式：
  1. 使用 build_graph 構建鄰接表。
  2. 使用 find_leaves 找出所有葉節點。
  3. 假設選擇葉節點中的第一個和最後一個作為起點和終點。
  4. 使用 dfs 尋找從選定的 start 到 end 的路徑。
• 輸出：返回從 start 到 end 的路徑，以及 start 和 end 節點。

3. 範例運行流程

假設輸入的 tree 為：

tree = [[1,2],[1,3],[2,4],[3,5],[5,6]]

1. 構建鄰接表：

   {
       1: [2, 3],
       2: [1, 4],
       3: [1, 5],
       4: [2],
       5: [3, 6],
       6: [5]
   }
   

2. 找出葉節點：[4, 6]
3. 選擇 start 和 end：start = 4，end = 6
4. 使用 DFS 找到路徑：[4, 2, 1, 3, 5, 6]

4. 執行結果

從節點 4 到節點 6 的路徑: [4, 2, 1, 3, 5, 6]

這段程式自動找出樹中的葉節點，並從第一個到最後一個葉節點之間尋找路徑，適合用於分析樹狀結構中的連接性和路徑搜尋。