无向图的邻接表和逆邻接表一样吗

无向图的邻接表和逆邻接表是不同的。邻接表是一种表示图形的数据结构，其中每个顶点的相邻顶点列表存储在该顶点的条目中。对于无向图，每个顶点的相邻顶点列表应包括所有与该顶点相邻的顶点。而逆邻接表是指对于每个顶点，存储指向该顶点的所有边的列表。在有向图中，逆邻接表与邻接表不同，因为它存储指向每个顶点的边，而不是从每个顶点出发的边。

因此，无向图的邻接表和逆邻接表是不同的，因为它们分别存储每个顶点的相邻顶点和指向该顶点的边。在无向图中，邻接表和逆邻接表可能包含相同的信息，但它们的实现方式不同。

相关问题

用邻接表表示法编写无向图的邻接表和逆邻接表，编写有向图的邻接表和有向图的逆邻接表，并输出。

邻接表是图的一种常用表示方法，它将每个顶点的所有邻接点存储在一个链表中。对于无向图，每个顶点的邻接表中存储的是该顶点相邻的所有顶点；对于有向图，每个顶点的邻接表中存储的是该顶点的所有出边所连接的顶点。

邻接表的实现可以使用C++ STL中的vector和list容器，也可以手动实现链表。下面我将分别介绍无向图和有向图的邻接表和逆邻接表的实现方法。

【无向图的邻接表和逆邻接表】

#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函数中，我们分别输出了邻接表和逆邻接表。

【有向图的邻接表和逆邻接表】

#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函数中，我们分别输出了邻接表和逆邻接表。

创建图的邻接表存储结构，并用邻接表表示法编写无向图的邻接表和逆邻接表，编写有向图的邻接表和有向图的逆邻接表，并输出。

邻接表是一种用于存储图的数据结构，它将每个顶点的所有邻接点存储在一个链表中。对于一个无向图，我们可以分别使用邻接表和逆邻接表来表示它，而对于有向图，则需要使用邻接表和有向图的逆邻接表来表示它。

以下是无向图和有向图的邻接表和逆邻接表的实现代码：

#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方法来打印出每个顶点的邻接表和逆邻接表。

示例代码：