圖的遍歷與最小生成樹：DFS、BFS、Kruskal、Prim 完整 C++ 實現

圖的抽象基類與鄰接矩陣實現

// Graph.h：抽象介面
template 
class Graph {
    virtual void depth_first(V) = 0;
    virtual void broad_first(V) = 0;
    virtual void min_spantree_kruskal() = 0;
    virtual void min_spantree_prim(V) = 0;
    // ... 基本操作介面
};

// GraphMtx.h：鄰接矩陣實現
template 
class GraphMtx : public Graph {
    V* vertices;
    E** edges;
    // ... 實現所有虛函式
};

深度優先搜尋（DFS）

策略：一條路走到黑，走不通回溯。遞迴實現，需 visited[] 防環。
代碼：

void depth_first(V start) {
    int n = numVertices;
    bool* visited = new bool[n]();
    depth_first(start, visited);
    delete[] visited;
}
void depth_first(V v, bool* visited) {
    cout << v << "->";
    int i = getVertexIndex(v);
    visited[i] = true;
    for (int j = getFirstNeighbor(v); j != -1; j = getNextNeighbor(v, vertices[j]))
        if (!visited[j]) depth_first(vertices[j], visited);
}

廣度優先搜尋（BFS）

策略：層層推進，隊列實現。
代碼：

void broad_first(V start) {
    int n = numVertices;
    bool* visited = new bool[n]();
    queue q;
    int s = getVertexIndex(start);
    visited[s] = true; q.push(s); cout << start << "->";
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int j = getFirstNeighbor(vertices[v]); j != -1; j = getNextNeighbor(vertices[v], vertices[j])) {
            if (!visited[j]) {
                cout << vertices[j] << "->";
                visited[j] = true;
                q.push(j);
            }
        }
    }
    delete[] visited;
}

最小生成樹——Kruskal 算法

策略：邊排序，依權重遞增加入，並查集檢測環。
關鍵結構：

struct MSTEdge { int begin, end; E cost; };
int compare(const void* a, const void* b) { return ((MSTEdge*)a)->cost - ((MSTEdge*)b)->cost; }

bool isSame(int* parent, int u, int v) { // 尋找根節點
    while (parent[u] != u) u = parent[u];
    while (parent[v] != v) v = parent[v];
    return u == v;
}
void unionSets(int* parent, int u, int v) { // 合併
    while (parent[u] != u) u = parent[u];
    while (parent[v] != v) v = parent[v];
    parent[v] = u;
}

void min_spantree_kruskal() {
    // 收集所有邊
    MSTEdge* edges = ...;
    qsort(edges, edgeCount, sizeof(MSTEdge), compare);
    int* parent = new int[n]; iota(parent, parent+n, 0);
    for (each edge in sorted edges) {
        if (!isSame(parent, e.begin, e.end)) {
            cout << vertices[e.begin] << "-" << vertices[e.end] << " cost=" << e.cost << endl;
            unionSets(parent, e.begin, e.end);
        }
    }
    delete[] parent; delete[] edges;
}

最小生成樹——Prim 算法

策略：從起點擴展，維護 lowcost[v]（v 到樹的最小邊權）與 mst[v]（對應樹中頂點）。
代碼：

void min_spantree_prim(V start) {
    int n = numVertices;
    int* lowcost = new int[n];
    int* mst = new int[n];
    int s = getVertexIndex(start);
    // 初始化
    for (int i = 0; i < n; ++i) { lowcost[i] = edges[s][i]; mst[i] = s; }
    lowcost[s] = 0; // 起點已納入

    for (int i = 1; i < n; ++i) {
        // 選擇 lowcost 最小且未納入的頂點
        int min = MAX_COST, k = -1;
        for (int j = 0; j < n; ++j)
            if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; k = j; }
        cout << vertices[mst[k]] << "-" << vertices[k] << " cost=" << min << endl;
        lowcost[k] = 0; // 標記納入
        // 更新 lowcost
        for (int j = 0; j < n; ++j)
            if (lowcost[j] != 0 && edges[k][j] < lowcost[j]) {
                lowcost[j] = edges[k][j];
                mst[j] = k;
            }
    }
    delete[] lowcost; delete[] mst;
}

測試驗證

測試代碼驗證 DFS、BFS、Kruskal、Prim 在同一圖上的輸出結果。