请编程创建无向图的邻接表、有向图的邻接表和逆邻接表。
时间: 2024-05-22 15:08:20 浏览: 96
创建无向图的邻接表可以使用vector或者list等STL容器来实现。例如,以下是一个使用vector实现的无向图邻接表的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m; // n为节点数,m为边数
cin >> n >> m;
vector<int> adj[n+1]; // 邻接表,下标从1开始
// 添加边
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // 无向图,需要添加反向边
}
// 输出邻接表
for(int i=1; i<=n; i++) {
cout << i << ": ";
for(auto j : adj[i]) {
cout << j << " ";
}
cout << endl;
}
return 0;
}
```
创建有向图的邻接表可以使用类似的方法,只需要将添加反向边这一步省略即可。以下是一个使用vector实现的有向图邻接表的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m; // n为节点数,m为边数
cin >> n >> m;
vector<int> adj[n+1]; // 邻接表,下标从1开始
// 添加边
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
// 输出邻接表
for(int i=1; i<=n; i++) {
cout << i << ": ";
for(auto j : adj[i]) {
cout << j << " ";
}
cout << endl;
}
return 0;
}
```
创建有向图的逆邻接表也可以使用类似的方法,只需要在添加边时将终点和起点交换即可。以下是一个使用vector实现的有向图逆邻接表的代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m; // n为节点数,m为边数
cin >> n >> m;
vector<int> adj[n+1]; // 邻接表,下标从1开始
vector<int> radj[n+1]; // 逆邻接表,下标从1开始
// 添加边
for(int i=0; i<m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
radj[v].push_back(u); // 终点和起点交换,得到逆邻接表
}
// 输出逆邻接表
for(int i=1; i<=n; i++) {
cout << i << ": ";
for(auto j : radj[i]) {
cout << j << " ";
}
cout << endl;
}
return 0;
}
```
阅读全文