有向图的正邻接链表和逆邻接链表。

有向图的正邻接链表和逆邻接链表是用来表示有向图中节点之间关系的数据结构。

正邻接链表是指对于每个节点，记录其指向其他节点的边的信息。逆邻接链表是指对于每个节点，记录指向该节点的边的信息。

下面是一个示例来说明正邻接链表和逆邻接链表的概念：

假设有以下有向图：

1 -> 2
1 -> 3
2 -> 3
3 -> 4

对于节点1，其正邻接链表为：[2, 3]，表示节点1指向节点2和节点3。

对于节点2，其正邻接链表为：，表示节点2指向节点3。

对于节点3，其正邻接链表为：，表示节点3指向节点4。

对于节点2，其逆邻接链表为：，表示指向节点2的边来自节点1。

对于节点3，其逆邻接链表为：[1, 2]，表示指向节点3的边来自节点1和节点2。

对于节点4，其逆邻接链表为：，表示指向节点4的边来自节点3。

通过正邻接链表和逆邻接链表，我们可以方便地获取节点的出度和入度，以及节点之间的关系。

相关问题

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

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

邻接表的实现可以使用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函数中，我们分别输出了邻接表和逆邻接表。

一有向图ABCD的邻接表和逆邻接表和十字链表怎么写

在图论中，一有向图可以用多种数据结构表示，其中邻接表、逆邻接表和十字链表都是常用的方法：

1. **邻接表**：这是一种常用的图的数据结构，用于表示图中每个顶点与其相邻顶点的关系。对于有向图ABCD，邻接表可以这样表示（假设A到B、C、D都有边）：
- 对于顶点A，邻接链表包含指向B、C、D的指针；
- 同理，顶点B的邻接链表包含指向A的指针；顶点C和D也是如此。

# 示例用Python表示
class Node:
    def __init__(self, vertex):
        self.vertex = vertex
        self.neighbors = []

graph = {
    'A': [Node('B'), Node('C'), Node('D')],
    'B': [Node('A')],
    'C': [Node('A')],
    'D': [Node('A')]
}

2. **逆邻接表**：也称为出度列表，存储的是每个顶点的所有出边目标及其对应的边信息。同样以ABCD为例：
- 每个顶点有一个列表，存储其所有指向其他顶点的边，如A的逆邻接表包含B、C、D作为元素，对应边的信息。

graph_inverted = {
    'A': {'B': None, 'C': None, 'D': None},
    'B': {'A': None},
    'C': {'A': None},
    'D': {'A': None}
}

3. **十字链表（Cross-Edge List）**：一种特殊的邻接表形式，将每条边作为一个单独的节点连接起始和结束顶点。对于ABCD，如果A到B有一条边，会创建一个新节点`edge(A, B)`，然后分别添加到A和B的邻接链表中。这里省略了详细的代码示例，因为实际操作起来比较复杂。

edge_node = Edge('A', 'B')
graph[A].append(edge_node)  # 添加到A的邻接链表
edge_node.src_neighbors.append(graph[B])  # 将B添加到edge_node的src_neighbors

# 类似地处理其他边...