#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; } } };

这是一个 C++ 实现的无向图的邻接表存储结构，包含了以下几个部分：

- 私有成员变量 V 表示图的顶点数，adj 是一个 vector 容器，每个元素都是一个 vector 容器，存储与该顶点相邻的顶点。
- 公有构造函数 Graph(int V) 用于创建一个包含 V 个顶点的图，并初始化邻接表 adj。
- 公有成员函数 addEdge(int v, int w) 用于向图中添加一条从顶点 v 到顶点 w 的边，由于是无向图，所以还需要添加一条从顶点 w 到顶点 v 的边。
- 公有成员函数 printGraph() 用于打印整个图的邻接表，遍历每个顶点的邻接表，输出所有相邻的顶点。

这个实现使用了 vector 容器来存储邻接表，相比于邻接矩阵，邻接表可以节省空间，更适合存储稀疏图。

相关问题

运行#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 方法打印整张图的邻接表。

#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算法的实现原理。在实际应用中，可能需要对输入进行合法性检查和错误处理。