存图方案

有几种经典的图存储方法，它们各自适用于不同类型的图，以下是它们的详细讲解和Markdown演示：

邻接矩阵（Adjacency Matrix）:
- 用一个二维数组来表示图，其中 matrix[i][j] 表示从顶点 i 到顶点 j 是否存在边，通常用 0 和 1 表示无向图。
- 适用于稠密图，因为需要 O(V^2) 的空间。
示例：
```
| 0 1 1 0 |
| 1 0 0 1 |
| 1 0 0 0 |
| 0 1 0 0 |
```
邻接链表（Adjacency List）:
- 使用一个数组，每个元素是一个链表，其中包含与该顶点相邻的顶点。
- 适用于稀疏图，因为占用空间较小，而且易于遍历。
示例：
```
0 -> 1 -> 2
1 -> 0 -> 3
2 -> 0
3 -> 1
```
边列表（Edge List）:
- 使用一个列表存储所有的边，通常表示为 (u, v) 表示从顶点 u 到顶点 v 的边。
- 空间利用率较低，但在某些算法中可以快速访问边。
示例：
```
(0, 1), (1, 0), (0, 2), (1, 3)
```
邻接多重表（Adjacency Multilist）:
- 用于存储有向图，每个顶点包含两个链表，一个指向其出边，一个指向其入边。
- 适用于有向图，可以同时表示有向边和无向边。
示例（省略示例）。

最后，让我们来讲解 链式前向星（Forward Star or Edge List）：

链式前向星（Forward Star or Edge List）:
- 主要用于有向图，将所有边存储在一个数组中，同时维护两个数组，分别表示顶点首边和下一条边的位置。
- 适用于有向图，能够高效地支持图的遍历和算法操作。
示例：
```
markdown
Graph:
    0 --> 1
    |     |
    v     v
    2 <-- 3

Forward Star Representation:
Vertices: 0 1 2 3
Edges:    (0, 1) (1, 3) (3, 2) (2, 0)
First Edge: 0 1 -1 2
Next Edge:  -1 3 -1 -1
```
- Vertices 表示图的所有顶点。
- Edges 表示所有边，按照 (u, v) 的顺序。
- First Edge 数组表示每个顶点的第一条边在 Edges 数组中的位置。
- Next Edge 数组表示每条边在 Edges 数组中的下一条边的位置。

链式前向星的存储方法既能高效地表示有向图，也能够高效地支持图的遍历和算法操作。

cpp
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1000;  // 最大顶点数
const int MAXM = 2000;  // 最大边数

struct Edge {
    int to, next;  // to表示边的终点，next表示下一条边的位置
};

int head[MAXN];  // 存储每个顶点的第一条边在边数组中的位置
Edge edges[MAXM]; // 存储边的数组
int edgeCount = 0; // 边的计数器

// 添加有向边 u -> v
void addEdge(int u, int v) {
    edges[edgeCount].to = v;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount;
    edgeCount++;
}

int main() {
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;

    // 初始化链式前向星
    for (int i = 0; i < n; i++) {
        head[i] = -1; // 初始时每个顶点的第一条边为-1
    }

    // 添加有向边
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }

    // 遍历图，例如输出每个顶点的邻居
    for (int u = 0; u < n; u++) {
        cout << "Neighbors of vertex " << u << ": ";
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int v = edges[i].to;
            cout << v << " ";
        }
        cout << endl;
    }

    return 0;
}