邻接表，邻接矩阵和十字链表

1. 邻接表的实现

邻接表使用一个数组或 vector 来存储每个顶点的边列表。每个顶点的边列表存储在一个链表或 vector 中。

#include <iostream>
#include <vector>
using namespace std;

class Graph {
    int V; // 顶点数量
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int V) {
        this->V = V;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    void printGraph() {
        for (int i = 0; i < V; i++) {
            cout << "Vertex " << i << ":";
            for (int v : adj[i]) {
                cout << " -> " << v;
            }
            cout << endl;
        }
    }
};

int main() {
    Graph 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;
}

2. 邻接矩阵的实现

邻接矩阵使用一个二维数组来存储顶点之间的边。每个元素表示顶点之间是否存在边。

#include <iostream>
#include <vector>
using namespace std;

class Graph {
    int V; // 顶点数量
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    Graph(int V) {
        this->V = V;
        adjMatrix.resize(V, vector<int>(V, 0));
    }

    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        // 如果是无向图，也要添加下面这一行
        // adjMatrix[v][u] = 1;
    }

    void printGraph() {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph 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;
}

3. 十字链表的实现

十字链表是一种复杂的数据结构，特别适用于有向图。它包含每个顶点的出边和入边链表。

#include <iostream>
#include <vector>
using namespace std;

struct EdgeNode {
    int tail;  // 边的起点
    int head;  // 边的终点
    EdgeNode *nextOut; // 下一条出边
    EdgeNode *nextIn;  // 下一条入边
    EdgeNode(int t, int h) : tail(t), head(h), nextOut(nullptr), nextIn(nullptr) {}
};

struct VertexNode {
    int data; // 顶点的数据
    EdgeNode *firstOut; // 出边链表头节点
    EdgeNode *firstIn;  // 入边链表头节点
    VertexNode(int d) : data(d), firstOut(nullptr), firstIn(nullptr) {}
};

class OrthogonalList {
    vector<VertexNode*> vertices;

public:
    OrthogonalList(int V) {
        for (int i = 0; i < V; ++i) {
            vertices.push_back(new VertexNode(i));
        }
    }

    void addEdge(int u, int v) {
        EdgeNode* edge = new EdgeNode(u, v);

        // 添加到出边链表
        edge->nextOut = vertices[u]->firstOut;
        vertices[u]->firstOut = edge;

        // 添加到入边链表
        edge->nextIn = vertices[v]->firstIn;
        vertices[v]->firstIn = edge;
    }

    void printGraph() {
        for (int i = 0; i < vertices.size(); ++i) {
            cout << "Vertex " << i << ":" << endl;
            
            // 打印出边链表
            cout << "  Out-edges:";
            for (EdgeNode* e = vertices[i]->firstOut; e != nullptr; e = e->nextOut) {
                cout << " -> " << e->head;
            }
            cout << endl;

            // 打印入边链表
            cout << "  In-edges:";
            for (EdgeNode* e = vertices[i]->firstIn; e != nullptr; e = e->nextIn) {
                cout << " <- " << e->tail;
            }
            cout << endl;
        }
    }
};

int main() {
    OrthogonalList 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;
}

十字链表（Orthogonal List）是一种用于表示有向图的链式存储结构，它同时包含了每个顶点的入边和出边信息。十字链表是一种扩展的邻接表，能够方便地访问有向图中的边和顶点的入度、出度关系。该结构特别适合处理复杂的有向图问题。

十字链表的定义

在十字链表中，每个顶点既有一个出边链表，也有一个入边链表，分别存储从该顶点出发和指向该顶点的边。具体来说：

每条边由两个链表节点表示：出边节点（表示从某顶点出发的边）和入边节点（表示指向某顶点的边）。
顶点包含两个指针：一个指向该顶点的出边链表的头节点，另一个指向该顶点的入边链表的头节点。

结构描述

顶点结构（Vertex Node）：每个顶点有两个指针，一个指向该顶点的出边链表（out-edge list），另一个指向该顶点的入边链表（in-edge list）。
边结构（Edge Node）：每条边有两个指针，一个指向下一个出边（out-edge），另一个指向下一个入边（in-edge）。此外，边节点会记录边的起点和终点信息（通常是用来标识的起点和终点索引）。

十字链表的节点结构

假设有向图有 ( V ) 个顶点， ( E ) 条边，十字链表的基本节点可以定义为以下形式：

顶点节点（Vertex Node）：
- data：顶点的值或标识。
- firstOut：指向该顶点的出边链表的头节点。
- firstIn：指向该顶点的入边链表的头节点。
边节点（Edge Node）：
- tail：起点（边的出发顶点）。
- head：终点（边的目标顶点）。
- nextOut：指向出边链表中的下一条边（从相同顶点出发的下一条边）。
- nextIn：指向入边链表中的下一条边（指向相同顶点的下一条边）。
- weight（可选）：如果是加权图，则可以包含边的权重信息。

十字链表的示例

我们通过一个简单的有向图来说明十字链表的结构。假设有如下有向图：

1 2	顶点：A, B, C, D 边：A → B, A → C, B → C, C → D

1. 顶点的出边链表和入边链表

顶点 A 的出边链表：A → B, A → C
顶点 A 的入边链表：无
顶点 B 的出边链表：B → C
顶点 B 的入边链表：A → B
顶点 C 的出边链表：C → D
顶点 C 的入边链表：A → C, B → C
顶点 D 的入边链表：C → D

2. 十字链表表示

顶点节点：

A: firstOut -> (A → B), firstIn -> null
B: firstOut -> (B → C), firstIn -> (A → B)
C: firstOut -> (C → D), firstIn -> (A → C)
D: firstOut -> null,      firstIn -> (C → D)

边节点：

(A → B): nextOut -> (A → C), nextIn -> null
(A → C): nextOut -> null,      nextIn -> null
(B → C): nextOut -> null,      nextIn -> (A → C)
(C → D): nextOut -> null,      nextIn -> null

在这个结构中，顶点 A 通过 firstOut 链接了出边 (A → B)，并通过 nextOut 指向下一条出边 (A → C)，而 firstIn 为 null，因为没有指向 A 的边。同样，边 (A → B) 的 nextIn 为空，因为没有指向 B 的其他边。

十字链表的优缺点

优点

方便处理有向图：十字链表同时存储了出边和入边信息，因此可以方便地遍历从顶点出发的边以及指向该顶点的边。这使得在处理有向图的算法中（如拓扑排序、求解强连通分量等）非常高效。
高效的边操作：可以快速获取某个顶点的所有出边和入边，适合需要频繁查询边信息的场景。
适合稀疏图：十字链表只存储实际存在的边，因此在边数较少的稀疏图中节省空间。

缺点

复杂性高：相比于普通的邻接表或邻接矩阵，十字链表的数据结构较为复杂，构建和维护成本较高。每条边需要维护两个链表，代码实现上较为复杂。
空间占用较大：由于每条边需要存储两个链表指针（nextOut 和 nextIn），十字链表比简单的邻接表占用更多的空间。

十字链表的时间复杂度

空间复杂度：由于每条边都需要额外维护两个指针，十字链表的空间复杂度为 ( O(V + 2E) )，即每个顶点存储两个指针，每条边也存储两个指针。
遍历所有出边/入边：从某个顶点出发，遍历所有出边或入边的时间复杂度是 ( O(d) )，其中 ( d ) 是该顶点的度数。
查找特定边：查找某个顶点的所有出边或入边仍然需要遍历整个链表，时间复杂度为 ( O(d) )。

应用场景

有向图的遍历：十字链表适合处理需要同时遍历出边和入边的有向图算法，例如：
- 拓扑排序：需要同时考虑入度和出度，十字链表方便在 O(1) 时间内访问这些信息。
- 强连通分量算法：在求解强连通分量时，需要遍历有向图的逆图，十字链表能够高效支持这种操作。
网络流：在最大流或最小费用流等问题中，十字链表能够高效表示网络中的有向边及其流量信息。

十字链表是一种用于表示有向图的链式结构，通过同时维护顶点的出边和入边链表，能够高效处理有向图的遍历和操作，尤其适用于那些需要频繁查询边信息和入度、出度关系的应用场景。虽然其空间开销较大，结构复杂，但在有向图的高级算法中，十字链表提供了很高的效率。