模拟链表实现邻接表

优点：
1. 不用动态申请内存，常数小
2. 没了

下面的代码使用首部插入法。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;
static const int nmax=1000000,mmax=1000000;
//nmax 表示节点最大个数，mmax 表示边的最大个数
struct graph
{
    int to[mmax+5],dis[mmax+5],nxt[mmax+5],head[nmax+5],size;
    //to[i] 为边 i 到达的点，dis[i] 为边 i 的权值，nxt[i] 为边 i 的下一条边的编号
    //head[i] 表示点 i 邻接表中第一条边的编号，size 表示该图中边的个数（已插入的）
    inline graph(){memset(head,-1,sizeof(head)),size=0;}//初始化
    inline void push(int u,int v,int w)//向图中插入一条从 u 到 v，权值为 w 的有向边
    {
        to[size]=v,dis[size]=w,nxt[size]=head[u],head[u]=size,size++;
    }
};
graph g;//定义一个图 g
int main()
{
    g.push(1,2,100),g.push(1,3,200);//加入从 1 到 2 和 3 的两条边
    for(int i=g.head[1];i!=-1;i=g.nxt[i])//遍历节点 1 的邻接表
        cout<<g.to[i]<<' '<<g.dis[i]<<endl;
    return 0;
}

程序输出：

3 200
2 100

一些注意事项

1. graph 别定义在函数内，容易爆栈
2. 对于无向图，记得 mmax 要开大一倍
3. 记得初始化
4. 以 graph 为参数的时候建议传指针
5. 没了