如何使用遞歸查詢遍歷圖結構數據

遞歸查詢是一種在圖結構數據中遍歷節點的方法，通過重復調用自身來實現

1. 確定圖結構：首先，你需要有一個圖結構數據。這可以是一個包含節點和邊的列表、鄰接矩陣或鄰接表。為了演示，我們將使用鄰接表表示圖結構。

2. 創建遞歸函數：編寫一個遞歸函數，該函數接收當前節點作為輸入，并返回從該節點開始的所有路徑。在函數內部，遍歷當前節點的所有鄰居，對每個鄰居調用遞歸函數，然后將結果與當前節點組合在一起。

3. 處理已訪問節點：為了避免無限循環，需要跟蹤已訪問過的節點。可以使用一個集合或列表來存儲已訪問過的節點。在遞歸調用之前，檢查當前節點是否已經訪問過。如果已訪問過，則跳過該節點。

4. 初始化遞歸：從圖中的一個起始節點開始遞歸查詢。將已訪問節點集合清空，然后調用遞歸函數。

下面是一個使用Python實現的簡單示例：

# 圖結構（鄰接表）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}

# 遞歸查詢函數
def recursive_traversal(node, visited, path=None):
    if path is None:
        path = []
    
    # 將當前節點添加到路徑中
    path.append(node)
    
    # 如果當前節點已訪問過，直接返回路徑
    if node in visited:
        return [path]
    
    # 標記當前節點為已訪問
    visited.add(node)
    
    # 遞歸遍歷鄰居節點
    paths = []
    for neighbor in graph[node]:
        neighbor_paths = recursive_traversal(neighbor, visited, path.copy())
        paths.extend(neighbor_paths)
    
    return paths

# 從節點'A'開始遍歷
start_node = 'A'
visited = set()
all_paths = recursive_traversal(start_node, visited)

# 打印所有路徑
for path in all_paths:
    print(path)

這個示例將遍歷給定的圖結構，并打印出從節點’A’開始的所有路徑。請注意，這個示例沒有考慮圖中可能存在的環。如果圖中存在環，可以在遞歸調用之前檢查當前路徑，以避免重復訪問相同的節點。