Bfs如何找出起點與終點間的最短距離

BFS（廣度優先搜尋）是一種圖算法，可以用來找出圖中兩個節點之間的最短路徑。以下是使用BFS找出圖中兩個節點之間最短路徑的步驟：

1. 初始化一個隊列，用來存放待訪問的節點。
2. 將起始節點放入隊列中，並設置一個訪問標記來跟蹤已經訪問過的節點。
3. 重複以下步驟直到隊列變空或者找到終點節點：
   • 從隊列中取出一個節點。
   • 如果該節點未被訪問過，將其標記為訪問過，並將其所有未訪問的鄰居節點放入隊列中。
   • 如果取出的節點是終點節點，則停止算法，並返回成功找到最短路徑。

以下是一個簡單的Python實現：

from collections import deque

def bfs(graph, start, end):
    # 初始化隊列和訪問標記
    queue = deque([start])
    visited = set()

    # 開始BFS
    while queue:
        current = queue.popleft()
        if current not in visited:
            visited.add(current)
            if current == end:
                return True
            for neighbor in graph[current]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return False

# 示例圖形
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': ['G'],
    'E': ['H'],
    'F': [],
    'G': [],
    'H': []
}

# 開始BFS
if bfs(graph, 'A', 'H'):
    print("最短路徑存在")
else:
    print("沒有從起點到終點的路徑")

在上面的示例中，我們定義了一個圖形graph，然後使用BFS算法從節點'A'開始尋找到節點'H'的最短路徑。如果找到了這樣的路徑，算法會返回True，否則返回False。

請注意，這個算法假設圖形是無向的，並且邊的權重都是1。如果圖形是有向的或者邊有不同的權重，你可能需要對算法進行相應的修改。