用邻接表表示法编写无向图的邻接表和逆邻接表,编写有向图的邻接表和有向图的逆邻接表,并输出。
时间: 2024-05-22 08:08:20 浏览: 116
邻接表是图的一种常用表示方法,它将每个顶点的所有邻接点存储在一个链表中。对于无向图,每个顶点的邻接表中存储的是该顶点相邻的所有顶点;对于有向图,每个顶点的邻接表中存储的是该顶点的所有出边所连接的顶点。
邻接表的实现可以使用C++ STL中的vector和list容器,也可以手动实现链表。下面我将分别介绍无向图和有向图的邻接表和逆邻接表的实现方法。
【无向图的邻接表和逆邻接表】
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 无向图的邻接表和逆邻接表
class UndirectedGraph {
private:
int V; // 顶点数
vector<list<int>> adjList; // 邻接表
vector<list<int>> revAdjList; // 逆邻接表
public:
// 构造函数
UndirectedGraph(int V) {
this->V = V;
adjList.resize(V);
revAdjList.resize(V);
}
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
revAdjList[u].push_back(v);
revAdjList[v].push_back(u);
}
// 输出邻接表和逆邻接表
void printGraph() {
cout << "Undirected Graph:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (auto j : adjList[i])
cout << j << " ";
cout << endl;
}
cout << "Reverse Adjacency List:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (auto j : revAdjList[i])
cout << j << " ";
cout << endl;
}
}
};
int main() {
UndirectedGraph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
return 0;
}
```
上述代码中,我们定义了一个UndirectedGraph类,它包括了一个无向图的顶点数V、邻接表adjList和逆邻接表revAdjList。在构造函数中,我们初始化了这三个变量,并调用resize函数设置了它们的大小为V。在addEdge函数中,我们将边(u, v)和边(v, u)都添加到邻接表和逆邻接表中。最后,在printGraph函数中,我们分别输出了邻接表和逆邻接表。
【有向图的邻接表和逆邻接表】
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 有向图的邻接表和逆邻接表
class DirectedGraph {
private:
int V; // 顶点数
vector<list<int>> adjList; // 邻接表
vector<list<int>> revAdjList; // 逆邻接表
public:
// 构造函数
DirectedGraph(int V) {
this->V = V;
adjList.resize(V);
revAdjList.resize(V);
}
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
revAdjList[v].push_back(u);
}
// 输出邻接表和逆邻接表
void printGraph() {
cout << "Directed Graph:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (auto j : adjList[i])
cout << j << " ";
cout << endl;
}
cout << "Reverse Adjacency List:" << endl;
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (auto j : revAdjList[i])
cout << j << " ";
cout << endl;
}
}
};
int main() {
DirectedGraph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 2);
g.addEdge(4, 1);
g.addEdge(4, 3);
g.printGraph();
return 0;
}
```
上述代码中,我们定义了一个DirectedGraph类,它包括了一个有向图的顶点数V、邻接表adjList和逆邻接表revAdjList。在构造函数中,我们初始化了这三个变量,并调用resize函数设置了它们的大小为V。在addEdge函数中,我们将边(u, v)添加到邻接表中,将边(v, u)添加到逆邻接表中。最后,在printGraph函数中,我们分别输出了邻接表和逆邻接表。
阅读全文