🌐 图算法可视化

交互式学习 Prim、Kruskal、拓扑排序与 AOE 关键路径算法

📖 使用说明

  • 添加节点：点击"添加节点"按钮后，在画布上点击创建节点
  • 添加边：点击"添加边"按钮后，依次点击两个节点创建带权重的边
  • 删除：点击"删除"按钮后，点击节点或边进行删除
  • 运行算法：点击"运行 Prim"按钮，从第一个节点开始构建最小生成树
  • 清空：点击"清空画布"重新开始

🧠 算法逻辑规则

Prim 算法是一种贪心算法，用于寻找加权无向图的最小生成树。其核心逻辑如下：

  • 初始化：从图中任意选择一个节点作为起始节点，将其加入"已访问集合"。
  • 寻找最小边：在所有连接"已访问集合"和"未访问集合"的边中，找到权重最小的一条边。
  • 扩展树：将这条边连接的未访问节点加入"已访问集合"，并将该边加入最小生成树。
  • 重复：重复步骤 2 和 3，直到所有节点都被访问。

算法信息

节点数：0
边数：0
最小生成树权重和：-
💻 C++ 实现示例
// Prim 算法 - 最小生成树
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 1005;

int n, m;
vector<pair<int, int>> adj[MAXN];
bool visited[MAXN];
int key[MAXN];
int parent[MAXN];

void prim(int start) {
    fill(key, key + n, INF);
    fill(visited, visited + n, false);
    
    key[start] = 0;
    parent[start] = -1;
    
    for (int count = 0; count < n; count++) {
        // 找一个未访问且key最小的节点
        int u = -1;
        for (int v = 0; v < n; v++) {
            if (!visited[v] && (u == -1 || key[v] < key[u])) {
                u = v;
            }
        }
        
        if (key[u] == INF) break;
        
        visited[u] = true;
        
        for (auto [v, w] : adj[u]) {
            if (!visited[v] && w < key[v]) {
                key[v] = w;
                parent[v] = u;
            }
        }
    }
    
    int totalWeight = 0;
    for (int i = 0; i < n; i++) {
        if (i != start) totalWeight += key[i];
    }
    cout << "MST权重和: " << totalWeight << endl;
}

📖 使用说明

  • 添加节点：点击"添加节点"按钮后，在画布上点击创建节点
  • 添加边：点击"添加边"按钮后，依次点击两个节点创建带权重的边
  • 删除：点击"删除"按钮后，点击节点或边进行删除
  • 运行算法：点击"运行 Kruskal"按钮，按边权重从小到大构建最小生成树
  • 清空：点击"清空画布"重新开始

🧠 算法逻辑规则

Kruskal 算法也是一种贪心算法，它通过按权重顺序选择边来构建最小生成树。其核心逻辑如下：

  • 排序：将图中所有的边按照权重从小到大进行排序。
  • 遍历边：依次遍历排序后的每一条边。
  • 判断环路：对于当前选中的边，检查它连接的两个节点是否已经属于同一个连通分量（即是否会形成环路）。
  • 合并：如果不会形成环路，则将这条边加入最小生成树，并将两个节点所在的连通分量合并。否则，忽略这条边。
  • 结束：当选中的边数达到 V-1（V为节点数）时，算法结束。

算法信息

节点数：0
边数：0
最小生成树权重和：-
💻 C++ 实现示例
// Kruskal 算法 - 使用并查集
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

class UnionFind {
public:
    vector<int> parent, rank;
    
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};

void kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    
    int totalWeight = 0, edgeCount = 0;
    for (auto& e : edges) {
        if (uf.unite(e.u, e.v)) {
            totalWeight += e.w;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }
    
    cout << "MST权重和: " << totalWeight << endl;
}

📖 使用说明

  • 添加节点：点击"添加节点"按钮后，在画布上点击创建节点
  • 添加有向边：点击"添加边"按钮后，依次点击两个节点创建有向边（从第一个节点指向第二个节点）
  • 删除：点击"删除"按钮后，点击节点或边进行删除
  • 运行算法：点击"运行拓扑排序"按钮，执行拓扑排序算法
  • 清空：点击"清空画布"重新开始

🧠 算法逻辑规则

拓扑排序是一种对有向无环图（DAG）的顶点进行线性排序的算法。其核心逻辑如下：

  • 入度计算：首先计算每个节点的入度（指向该节点的边的数量）。
  • 初始化队列：将所有入度为 0 的节点加入队列。
  • 处理节点：从队列中取出一个节点，将其加入结果序列，并将该节点指向的所有邻接节点的入度减 1。
  • 更新队列：如果某个邻接节点的入度变为 0，则将其加入队列。
  • 检测环路：重复步骤 3 和 4，直到队列为空。如果结果序列中的节点数少于图中的总节点数，则说明图中存在环路，无法进行拓扑排序。

算法信息

节点数：0
边数：0
拓扑序列：-
💻 C++ 实现示例
// 拓扑排序 - Kahn 算法
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
vector<int> adj[MAXN];
int inDegree[MAXN];
vector<int> topoOrder;

bool topologicalSort() {
    queue<int> q;
    
    // 找所有入度为0的节点
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);
        
        // 更新u的所有邻接节点
        for (int v : adj[u]) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 检查是否存在环路
    if (topoOrder.size() != n) {
        cout << "图中存在环路!" << endl;
        return false;
    }
    
    // 输出拓扑序列
    for (int node : topoOrder) {
        cout << node << " ";
    }
    cout << endl;
    return true;
}

📖 使用说明

  • 添加节点：点击"添加节点"按钮后，在画布上点击创建事件节点
  • 添加活动（有向边+工期）：点击"添加活动"按钮后，依次点击两个节点创建有向边，并输入工期（正整数）
  • 删除：点击"删除"按钮后，点击节点或边进行删除
  • 运行算法：点击"运行 AOE"按钮，计算 ve/vl 并标出关键活动（关键路径上的边）
  • 清空：点击"清空画布"重新开始

🧠 算法逻辑规则

AOE（Activity On Edge）网把活动表示为边、把事件表示为点。关键路径是决定工期的最长路径，其核心步骤如下：

  • 拓扑排序：对 DAG 做拓扑序，若无法得到完整序列则说明有环，AOE 不成立。
  • 最早发生时间 ve：按拓扑序推进：对每条活动 (u→v, w)，更新 ve[v] = max(ve[v], ve[u] + w)。
  • 最迟发生时间 vl：令工程总工期 T = max ve[*]，初始化 vl[*]=T；按逆拓扑序回推：对 (u→v, w)，更新 vl[u] = min(vl[u], vl[v] - w)。
  • 关键活动判定：活动最早开工 e = ve[u]，最迟开工 l = vl[v] - w；若 e == l，则该活动为关键活动。

算法信息

节点数：0
活动数（边数）：0
工程总工期：-
关键活动：-
💻 C++ 实现示例
// AOE 关键路径（CPM）- ve/vl + 关键活动
#include <bits/stdc++.h>
using namespace std;

struct Edge { int u, v, w; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    vector<Edge> edges;
    vector<int> indeg(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        edges.push_back({u, v, w});
        indeg[v]++;
    }

    // 拓扑序 + ve
    queue<int> q;
    vector<int> topo;
    vector<int> ve(n, 0);
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto [v, w] : g[u]) {
            ve[v] = max(ve[v], ve[u] + w);
            if (--indeg[v] == 0) q.push(v);
        }
    }

    if ((int)topo.size() != n) {
        cout << "存在环，非 AOE 网" << "\n";
        return 0;
    }

    int T = 0;
    for (int i = 0; i < n; i++) T = max(T, ve[i]);

    // vl 逆拓扑回推
    vector<int> vl(n, T);
    for (int i = n - 1; i >= 0; i--) {
        int u = topo[i];
        for (auto [v, w] : g[u]) {
            vl[u] = min(vl[u], vl[v] - w);
        }
    }

    // 关键活动：e==l
    for (auto& e : edges) {
        int ee = ve[e.u];
        int ll = vl[e.v] - e.w;
        if (ee == ll) {
            cout << e.u << "->" << e.v << " (" << e.w << ")" << "\n";
        }
    }

    cout << "总工期: " << T << "\n";
    return 0;
}

输入边的权重