#include <iostream> #include <vector> #include <queue> using namespace std; struct Edge { int u, v, weight; Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {} }; class Graph { private: int V; vector<vector<pair<int, int>>> adj; public: Graph(int V) : V(V) { adj.resize(V); } void addEdge(int u, int v, int weight) { adj[u].push_back(make_pair(v, weight)); adj[v].push_back(make_pair(u, weight)); } int primMST() { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector<bool> visited(V, false); int minCost = 0; pq.push(make_pair(0, 0)); while (!pq.empty()) { int u = pq.top().second; int weight = pq.top().first; pq.pop(); if (visited[u]) continue; visited[u] = true; minCost += weight; for (auto neighbor : adj[u]) { int v = neighbor.first; int w = neighbor.second; if (!visited[v]) pq.push(make_pair(w, v)); } } return minCost; } }; int main() { int V, E; cout << "Enter the number of vertices: "; cin >> V; cout << "Enter the number of edges: "; cin >> E; Graph g(V); cout << "Enter the edges in the format (u, v, weight):" << endl; for (int i = 0; i < E; i++) { int u, v, weight; cin >> u >> v >> weight; g.addEdge(u, v, weight); } int minCost = g.primMST(); cout << "Minimum cost of the MST: " << minCost << endl; return 0; }

这是一个使用Prim算法求最小生成树的C++程序。它通过输入顶点数、边数和边的信息来构建图，并计算最小生成树的最小权重。

程序首先定义了一个结构体`Edge`来表示图的边，包括起点、终点和权重。然后定义了一个`Graph`类来表示图，包括顶点数和邻接表。

类中的`addEdge`函数用于向图中添加边，将边的信息存储在邻接表中。`primMST`函数使用Prim算法计算最小生成树的最小权重。它使用优先队列来选择权重最小的边，并使用visited数组来标记已经访问过的顶点。

在主函数中，首先输入顶点数和边数，然后逐个输入边的信息，并调用`addEdge`函数将边添加到图中。最后调用`primMST`函数计算最小生成树的最小权重，并输出结果。

请注意，这只是一个示例程序，用于演示Prim算法的实现原理。在实际应用中，可能需要对输入进行合法性检查和错误处理。

相关问题

#include <iostream> #include <vector> #include <queue> using namespace std; // 定义图的边结构体 struct Edge { int to; // 边的终点 int weight; // 边的权重 Edge(int t, int w) : to(t), weight(w) {} }; // 定义图的邻接表结构体 struct Graph { int n; // 节点数 vector<vector<Edge>> adj; // 邻接表 Graph(int n) : n(n), adj(n) {} // 添加一条边 void addEdge(int from, int to, int weight) { adj[from].push_back(Edge(to, weight)); } // 深度优先遍历 void dfs(int cur, vector<bool>& visited) { visited[cur] = true; cout << cur << " "; for (auto e : adj[cur]) { if (!visited[e.to]) { dfs(e.to, visited); } } } // 广度优先遍历 void bfs(int cur, vector<bool>& visited) { queue<int> q; q.push(cur); visited[cur] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; for (auto e : adj[u]) { if (!visited[e.to]) { visited[e.to] = true; q.push(e.to); } } } } }; int main() { int n, m; cin >> n >> m; Graph g(n); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g.addEdge(u, v, w); g.addEdge(v, u, w); // 无向图需要添加反向边 } // 深度优先遍历 cout << "DFS: "; vector<bool> visited(n, false); g.dfs(0, visited); cout << endl; // 广度优先遍历 cout << "BFS: "; visited.assign(n, false); g.bfs(0, visited); cout << endl; return 0; }给代码添加注释

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 定义图的边结构体
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重
    Edge(int t, int w) : to(t), weight(w) {} // 构造函数
};

// 定义图的邻接表结构体
struct Graph {
    int n;                  // 节点数
    vector<vector<Edge>> adj; // 邻接表
    Graph(int n) : n(n), adj(n) {} // 构造函数

    // 添加一条边
    void addEdge(int from, int to, int weight) {
        adj[from].push_back(Edge(to, weight));
    }

    // 深度优先遍历
    void dfs(int cur, vector<bool>& visited) {
        visited[cur] = true;
        cout << cur << " ";
        for (auto e : adj[cur]) {
            if (!visited[e.to]) {
                dfs(e.to, visited);
            }
        }
    }

    // 广度优先遍历
    void bfs(int cur, vector<bool>& visited) {
        queue<int> q;
        q.push(cur);
        visited[cur] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            for (auto e : adj[u]) {
                if (!visited[e.to]) {
                    visited[e.to] = true;
                    q.push(e.to);
                }
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.addEdge(u, v, w);
        g.addEdge(v, u, w); // 无向图需要添加反向边
    }

    // 深度优先遍历
    cout << "DFS: ";
    vector<bool> visited(n, false);
    g.dfs(0, visited);
    cout << endl;

    // 广度优先遍历
    cout << "BFS: ";
    visited.assign(n, false);
    g.bfs(0, visited);
    cout << endl;

    return 0;
}

注释已添加在代码中。

dijkstra算法代码实现。输入：第一行，三个整数，$vn,en,s $，用空格分开，分别表示图G中：顶点数目（顶点编号从0开始），弧的数量（无向图每对顶点之间有两条弧），Dijkstra算法指定的起点。其中：1≤ vn ≤ 1000， 1≤ en ≤ vn×（vn-1）。注意：案例中提供的弧可以有重复的，图应该按照最后一次的弧的设置为准，即SetEdge的语义当存在该弧时，设置权值。 之后会有en行，每行表示一对顶点之间的一条弧，形式为："<"+from+", "+to+", "+weight+">"，其中from为弧的起点，to为弧的终点，weight为弧上权值（每对顶点之间的不同的弧上的权值可以不同）输出：共vn行，第i行表示编号为i的顶点（第i个顶点，i从0开始）到起点s的最短路径长度len，以及该最短路径中的前驱顶点p（起始顶点s的前驱设为自身顶点编号s）。示例：输入10 32 0 <2, 1, 2> <1, 2, 2> <5, 8, 52> <8, 5, 52> <1, 7, 141> <7, 1, 141> <0, 8, 185> <8, 0, 185> <3, 8, 43> <8, 3, 43> <7, 8, 136> <8, 7, 136> <1, 2, 122> <2, 1, 122> <6, 8, 150> <8, 6, 150> <2, 1, 6> <1, 2, 6> <6, 3, 16> <3, 6, 16> <7, 9, 34> <9, 7, 34> <3, 1, 10> <1, 3, 10> <8, 9, 193> <9, 8, 193> <7, 8, 49> <8, 7, 49> <0, 1, 198> <1, 0, 198> <0, 5, 179> <5, 0, 179>输出：<0, 0, 0> <1, 198, 0> <2, 204, 1> <3, 208, 1> <4, INF, 0> <5, 179, 0> <6, 224, 3> <7, 234, 8> <8, 185, 0> <9, 268, 7>

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
const int maxm = 1e6 + 10;
int vn, en, s;
int head[maxn], cnt;
int dis[maxn], vis[maxn], p[maxn];
struct Edge {
    int to, nxt, w;
}e[maxm];
inline void AddEdge(int u, int v, int w) {
    e[++cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}
inline void Init() {
    memset(head, -1, sizeof(head));
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(p, -1, sizeof(p));
    cnt = -1;
}
inline void Dijkstra() {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, s));
    dis[s] = 0;
    while(!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                p[v] = u;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}
int main() {
    Init();
    scanf("%d%d%d", &vn, &en, &s);
    for(int i = 1; i <= en; i++) {
        int u, v, w;
        char c;
        scanf(" <%d, %d, %d%c", &u, &v, &w, &c);
        AddEdge(u, v, w);
        if(c != '>') {
            scanf(" %c", &c);
            scanf("%d", &w);
            AddEdge(v, u, w);
        }
    }
    Dijkstra();
    for(int i = 0; i < vn; i++) {
        if(dis[i] == INF) printf("<%d, INF, %d>\n", i, p[i]);
        else printf("<%d, %d, %d>\n", i, dis[i], p[i]);
    }
    return 0;
}