unordered_map 邻接表
时间: 2023-06-30 14:14:46 浏览: 43
邻接表通常用来表示图的连通关系,unordered_map 是一个哈希表,可以用来实现邻接表。具体来说,可以使用一个 unordered_map<int, vector<int>> 来表示一个有向图的邻接表,其中 unordered_map 的键是节点编号,值是一个 vector,存储该节点的所有出边的终点编号。例如,对于如下有向图:
```
1 -> 2 -> 3
| |
v v
4 5
```
可以使用如下的 unordered_map 表示其邻接表:
```
{
1: [2, 4],
2: [3, 5],
3: [],
4: [],
5: []
}
```
在实现图算法时,使用邻接表可以有效地减少时间和空间复杂度。
相关问题
无向图图的邻接表c++
以下是使用 C++ 实现无向图邻接表的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 定义邻接表的节点结构体
struct GraphNode {
int val; // 节点编号
vector<GraphNode*> neighbors; // 与该节点相邻的其他节点
GraphNode(int x) : val(x) {};
};
// 构造无向图的邻接表
vector<GraphNode*> buildGraph(vector<vector<int>>& edges) {
vector<GraphNode*> graph;
unordered_map<int, GraphNode*> mp;
for (auto& edge : edges) {
int from = edge[0], to = edge[1];
if (!mp.count(from)) {
mp[from] = new GraphNode(from);
}
if (!mp.count(to)) {
mp[to] = new GraphNode(to);
}
mp[from]->neighbors.push_back(mp[to]); // 无向图需要双向连接
mp[to]->neighbors.push_back(mp[from]);
}
for (auto& it : mp) {
graph.push_back(it.second);
}
return graph;
}
int main() {
vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {2, 3}};
vector<GraphNode*> graph = buildGraph(edges);
for (auto& node : graph) {
cout << node->val << ": ";
for (auto& neighbor : node->neighbors) {
cout << neighbor->val << " -> ";
}
cout << "NULL" << endl;
}
return 0;
}
```
以上代码中,我们定义了一个 `GraphNode` 结构体来表示邻接表中的节点,其中包含了节点的编号和与之相邻的其他节点。然后我们使用一个 `unordered_map` 来将每个节点的编号与其对应的结构体对象建立映射关系。接着我们遍历每条边,在 `unordered_map` 中找到对应的节点,将它们之间建立双向连接,最终将所有节点的结构体对象放入一个 vector 中返回。最后遍历这个 vector,打印每个节点的编号以及与之相邻的其他节点的编号即可。
键盘输入数据,建立一个有向图的邻接表的代码
以下是一个简单的键盘输入数据,建立有向图邻接表的代码。该代码使用了 STL 中的 vector 和 unordered_map 容器。
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, m;
cin >> n >> m; // n 为节点数,m 为边数
unordered_map<int, vector<int>> graph; // 定义邻接表
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // u -> v 有一条有向边
graph[u].push_back(v); // 加入邻接表
}
return 0;
}
```
在这个代码中,我们首先读入节点数 n 和边数 m,然后定义一个 unordered_map 容器 graph,用于存储邻接表。接下来,我们通过循环读入每一条边,将其加入到邻接表中。最后,我们返回 0 表示程序正常结束。