c++ 利用邻接表存储有向图

在 C++ 中，我们可以使用邻接表来存储有向图。邻接表是一种基于链表的数据结构，它可以有效地存储图中的节点和边，并提供快速的遍历和搜索。

邻接表由一个数组和一个链表组成。数组的每个元素对应一个图中的节点，而链表则包含从该节点出发的所有边。具体实现过程如下：

1. 定义一个结构体来表示图中的边：

struct Edge {
    int to;        // 边的终点
    int weight;    // 边的权重（如果有）
    Edge* next;    // 指向下一条边的指针
};

2. 定义一个数组来存储节点和指向其邻接表的指针：

const int MAXN = 100;    // 最大节点数
Edge* head[MAXN];        // 每个节点指向其邻接表的头指针

3. 对于每个节点，初始化其邻接表为空：

for (int i = 0; i < MAXN; i++) {
    head[i] = nullptr;
}

4. 对于每条边，创建一个新的 `Edge` 结构体，并将其添加到起点节点的邻接表中：

void addEdge(int from, int to, int weight) {
    Edge* e = new Edge;
    e->to = to;
    e->weight = weight;
    e->next = head[from];
    head[from] = e;
}

完整代码如下：

#include <iostream>
using namespace std;

const int MAXN = 100;    // 最大节点数

struct Edge {
    int to;        // 边的终点
    int weight;    // 边的权重（如果有）
    Edge* next;    // 指向下一条边的指针
};

Edge* head[MAXN];    // 每个节点指向其邻接表的头指针

void addEdge(int from, int to, int weight) {
    Edge* e = new Edge;
    e->to = to;
    e->weight = weight;
    e->next = head[from];
    head[from] = e;
}

int main() {
    // 添加边
    addEdge(0, 1, 1);
    addEdge(0, 2, 2);
    addEdge(1, 2, 3);
    addEdge(2, 3, 4);

    // 输出邻接表
    for (int i = 0; i < MAXN; i++) {
        if (head[i] != nullptr) {
            cout << i << ": ";
            for (Edge* e = head[i]; e != nullptr; e = e->next) {
                cout << "(" << e->to << ", " << e->weight << ") ";
            }
            cout << endl;
        }
    }

    return 0;
}

这个程序将会输出以下内容：

0: (2, 2) (1, 1) 
1: (2, 3) 
2: (3, 4) 

其中，每行表示一个节点的邻接表，格式为 `节点编号: (邻居节点编号, 边权重) ...`。例如，第一行表示节点 0 与节点 2 之间有一条边权重为 2 的边，与节点 1 之间有一条边权重为 1 的边。