邻接表建图 acwing
时间: 2023-09-24 12:08:58 浏览: 54
邻接表是一种常用的数据结构,用于表示图的连接关系。在建立邻接表时,我们可以使用数组和链表结合的方式来存储图的边。
下面是使用邻接表建立图的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 图的边结构体
struct Edge {
int from, to;
int weight;
Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight) {}
};
// 邻接表建图
void buildGraph(vector<vector<Edge>>& adj, int n, int m) {
// 初始化邻接表
adj.resize(n);
// 读入边信息,建立邻接表
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(Edge(u, v, w));
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<Edge>> adj;
buildGraph(adj, n, m);
// 输出邻接表
for (int i = 0; i < n; i++) {
cout << "Node " << i << ": ";
for (const auto& edge : adj[i]) {
cout << "(" << edge.to << ", " << edge.weight << ") ";
}
cout << endl;
}
return 0;
}
```
以上代码会根据输入的节点数和边数建立邻接表,并输出每个节点的相邻节点及其对应的边权重。可以根据实际需要进行修改和扩展。