無向圖最短路徑：基於鄰接表的 BFS 實現與路徑重建

問題定義

給定無向無權圖，求從起點到目標節點的最短路徑（邊數最少）。採用鄰接表存儲，BFS（廣度優先搜索）是最佳選擇。

數據結構設計

#define MAX 100
#define MAXQ 50

struct EdgeNode {
    int no;              // 目標節點編號
    char info;           // 節點名稱
    EdgeNode *next;      // 下一條邊
};

struct VexNode {
    char info;           // 頂點名稱
    EdgeNode *link;      // 第一條出邊
};

VexNode adjlist[MAX];    // 鄰接表
int queue[MAXQ];         // 循環隊列
bool visited[MAX];       // 訪問標記
int parent[MAX];         // 前驅節點，用於路徑回溯

圖的構建

int createGraph(VexNode *adjlist) {
    int n, e;
    cout << "請輸入節點數："; cin >> n;
    cout << "請輸入邊數：";   cin >> e;
    
    for (int i = 1; i <= n; i++) {
        cout << "請輸入節點 " << i << " 的名稱：";
        cin >> adjlist[i].info;
        adjlist[i].link = NULL;
    }
    
    for (int i = 1; i <= e; i++) {
        int v1, v2;
        cout << "請輸入邊 " << i << " 的兩端節點編號：";
        cin >> v1 >> v2;
        
        // 無向圖：雙向插入
        EdgeNode *p1 = (EdgeNode*)malloc(sizeof(EdgeNode));
        p1->no = v1; p1->info = adjlist[v1].info;
        p1->next = adjlist[v2].link;
        adjlist[v2].link = p1;
        
        EdgeNode *p2 = (EdgeNode*)malloc(sizeof(EdgeNode));
        p2->no = v2; p2->info = adjlist[v2].info;
        p2->next = adjlist[v1].link;
        adjlist[v1].link = p2;
    }
    return n;
}

BFS 核心邏輯

int BFS(VexNode *adjlist, int *queue, bool *visited, int *parent) {
    int v1;
    cout << "請輸入起始節點編號："; cin >> v1;
    
    int front = 0, rear = 1;
    queue[rear] = v1;
    
    fill(visited, visited + MAX, false);
    visited[v1] = true;
    
    cout << "BFS 遍歷順序：" << endl;
    cout << "節點 " << v1 << ", 名稱 " << adjlist[v1].info << endl;
    
    while (front != rear) {
        front = (front + 1) % MAXQ;
        int vx = queue[front];
        EdgeNode *p = adjlist[vx].link;
        
        while (p) {
            if (!visited[p->no]) {
                visited[p->no] = true;
                cout << "節點 " << p->no << ", 名稱 " << adjlist[p->no].info << endl;
                rear = (rear + 1) % MAXQ;
                queue[rear] = p->no;
                parent[p->no] = vx;  // 記錄前驅
            }
            p = p->next;
        }
    }
    return v1;
}

路徑重建：遞歸回溯

void print_path(VexNode *adjlist, int *parent, int target) {
    if (parent[target] != 0)
        print_path(adjlist, parent, parent[target]);
    cout << adjlist[target].info << "  ";
}

主程式與測試用例

int main() {
    int cases; 
    cout << "測試用例數："; cin >> cases;
    while (cases--) {
        int n = createGraph(adjlist);
        int start = BFS(adjlist, queue, visited, parent);
        parent[start] = 0;  // 起點無前驅
        
        int target;
        cout << "目標節點："; cin >> target;
        cout << "從 " << adjlist[start].info 
             << " 到 " << adjlist[target].info << " 的最短路徑：" << endl;
        print_path(adjlist, parent, target);
        cout << endl;
    }
    return 0;
}

測試輸出範例

輸入節點：r s t u v w x y (8節點)
輸入邊：10 條
起始節點：2 (s)
目標節點：6 (w)

BFS 遍歷：s → u → r → t → w → v → y → x
最短路徑：s  r  t  w

複雜度與優化建議

• 時間：O(V + E) — 每個頂點入隊出隊一次，每條邊檢查一次
• 空間：O(V) — 隊列、visited、parent 陣列
• 改進點：
  • 用 std::vector 替換手動鏈表，簡化記憶體管理
  • 用 std::queue 替換循環陣列隊列
  • 節點編號改為 0-based，符合 C++ 慣例
  • 輸入改為檔案/參數，便於自動化測試

延伸：帶權圖最短路徑

若邊有權重，BFS 不再適用，需用 Dijkstra（非負權）或 Bellman-Ford（含負權）。