创建图的邻接表存储结构,并用邻接表表示法编写无向图的邻接表和逆邻接表,编写有向图的邻接表和有向图的逆邻接表,并输出。
时间: 2024-05-22 07:08:20 浏览: 111
邻接表是一种用于存储图的数据结构,它将每个顶点的所有邻接点存储在一个链表中。对于一个无向图,我们可以分别使用邻接表和逆邻接表来表示它,而对于有向图,则需要使用邻接表和有向图的逆邻接表来表示它。
以下是无向图和有向图的邻接表和逆邻接表的实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 无向图的邻接表和逆邻接表
class UndirectedGraph {
public:
// 初始化顶点数和边数
UndirectedGraph(int vertices, int edges) {
V = vertices;
E = edges;
adj = new vector<int>[V];
reverse_adj = new vector<int>[V];
}
// 添加一条边
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
reverse_adj[v].push_back(u);
reverse_adj[u].push_back(v);
}
// 打印邻接表和逆邻接表
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "顶点 " << i << " 的邻接表: ";
for (auto x : adj[i])
cout << "-> " << x;
cout << endl;
cout << "顶点 " << i << " 的逆邻接表: ";
for (auto x : reverse_adj[i])
cout << "-> " << x;
cout << endl;
}
}
private:
int V, E; // 顶点数和边数
vector<int>* adj; // 邻接表
vector<int>* reverse_adj; // 逆邻接表
};
// 有向图的邻接表和逆邻接表
class DirectedGraph {
public:
// 初始化顶点数和边数
DirectedGraph(int vertices, int edges) {
V = vertices;
E = edges;
adj = new vector<int>[V];
reverse_adj = new vector<int>[V];
}
// 添加一条边
void addEdge(int u, int v) {
adj[u].push_back(v);
reverse_adj[v].push_back(u);
}
// 打印邻接表和逆邻接表
void printGraph() {
for (int i = 0; i < V; ++i) {
cout << "顶点 " << i << " 的邻接表: ";
for (auto x : adj[i])
cout << "-> " << x;
cout << endl;
cout << "顶点 " << i << " 的逆邻接表: ";
for (auto x : reverse_adj[i])
cout << "-> " << x;
cout << endl;
}
}
private:
int V, E; // 顶点数和边数
vector<int>* adj; // 邻接表
vector<int>* reverse_adj; // 逆邻接表
};
```
以上代码中,我们首先定义了一个UndirectedGraph类和一个DirectedGraph类来分别表示无向图和有向图。在这两个类中,我们都使用了vector来存储邻接表和逆邻接表。在初始化时,我们需要传入顶点数和边数,然后使用addEdge方法来添加一条边。最后,我们可以使用printGraph方法来打印出每个顶点的邻接表和逆邻接表。
示例代码:
阅读全文