#include <iostream> #include <vector> using namespace std; class Graph { private: int V; // 图的顶点数 vector<typename vector<int>::vector> adj; // 邻接表存储结构 public: Graph(int V) { this->V = V; adj.resize(V); } void addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } void printGraph() { for(int i = 0; i < V; i++) { cout << "顶点 " << i << " 的邻接表: "; for(int j = 0; j < adj[i].size(); j++) { cout << adj[i][j] << " "; } cout << endl; } } };

这是一个图的邻接表存储结构的实现，可以用来表示无向图。其中，类 Graph 有三个成员变量，分别为图的顶点数 V，邻接表 adj，以及构造函数 Graph(int V)。构造函数中会初始化邻接表 adj 的大小为 V，即邻接表中有 V 个元素，每个元素都是一个 vector<int> 类型的向量，用来存储与该顶点相邻的其他顶点编号。addEdge 方法用于添加图的边，其中 v 和 w 分别是边的两个顶点编号，因为是无向图，所以需要把两个顶点互相加入对方的邻接表中。printGraph 方法用于打印整张图的邻接表，依次输出每个顶点的邻接表中存储的相邻顶点编号。 你可以在 main 函数中创建一个 Graph 对象，并调用 addEdge 方法添加边，最后再调用 printGraph 方法打印整张图的邻接表。

### 贪心法实现最小生成树的C++代码示例 #### Kruskal算法 Kruskal算法是一种基于贪心策略的经典最小生成树算法。其核心思想是对图中的所有边按照权重从小到大排序，依次尝试加入当前边至最小生成树中，同时利用并查集检测是否会形成环路[^2]。 以下是Kruskal算法的C++实现： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义边的数据结构 struct Edge { int u, v, w; }; // 并查集的相关操作 class UnionFind { private: vector<int> parent; public: UnionFind(int n) { parent.resize(n); for (int i = 0; i < n; ++i) { parent[i] = i; } } int findSet(int x) { if (parent[x] != x) { parent[x] = findSet(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int fx = findSet(x), fy = findSet(y); if (fx != fy) { parent[fy] = fx; } } }; bool cmp(const Edge &a, const Edge &b) { return a.w < b.w; } void kruskalMST(vector<Edge> edges, int V) { sort(edges.begin(), edges.end(), cmp); UnionFind uf(V); int mst_weight = 0; cout << "Edges in the constructed MST:" << endl; for (auto edge : edges) { int set_u = uf.findSet(edge.u); int set_v = uf.findSet(edge.v); if (set_u != set_v) { cout << edge.u << " -- " << edge.v << " == " << edge.w << endl; mst_weight += edge.w; uf.unionSet(set_u, set_v); } } cout << "Total weight of MST: " << mst_weight << endl; } ``` --- #### Prim算法 Prim算法同样是基于贪心的思想来求解最小生成树问题。它的基本思路是从某个起点出发逐步扩展已访问节点集合，并始终选择连接未访问节点的最短边[^1]。 下面是Prim算法的一个C++实现版本： ```cpp #include <bits/stdc++.h> using namespace std; const int INF = INT_MAX; // 使用邻接矩阵表示图 void primMST(vector<vector<int>> graph, int V) { vector<int> key(V, INF); // 存储每个顶点的关键值 vector<bool> inMST(V, false); // 记录顶点是否已在MST中 vector<int> parent(V, -1); // 记录父节点用于重建路径 key[0] = 0; // 初始顶点设为源点 parent[0] = -1; // 源点无父节点 for (int count = 0; count < V - 1; ++count) { int minKey = INF, u; // 找到尚未加入MST且key值最小的顶点 for (int v = 0; v < V; ++v) { if (!inMST[v] && key[v] < minKey) { minKey = key[v], u = v; } } inMST[u] = true; // 将u加入MST // 更新相邻顶点的key值 for (int v = 0; v < V; ++v) { if (graph[u][v] && !inMST[v] && graph[u][v] < key[v]) { parent[v] = u, key[v] = graph[u][v]; } } } // 输出MST的结果 cout << "Edge \tWeight\n"; for (int i = 1; i < V; ++i) { cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << "\n"; } } ``` --- #### 总结 以上展示了如何通过贪心方法分别使用Kruskal和Prim算法计算最小生成树。这两种算法各有优劣，在稀疏图中通常推荐使用Kruskal算法；而在稠密图中则更适合采用Prim算法[^3]。