图论是一个“巨大”的专题，有大量的知识点，有众多广为人知的问题，有复杂的应用场景。

图论算法常常建立在复杂的数据结构之上。本文讲解了基础的图论考点，帮助读者了解图论专题。

在对图进行操作之前需要先存储图。图的存储方法有3种：邻接矩阵、邻接表、链式前向星。邻接矩阵用空间换取时间，代码极为简单且访问效率高，但是只能用于小图。邻接表的存储效率高且代码简单，是最常见的存储方法。链式前向星是最节省空间的存储方法，不过代码稍微复杂一点。

01、邻接矩阵

直接用矩阵graphN存储边，N为节点总数，节点的编号范围是0~N-1。如果希望节点编号范围为1~N，那么定义矩阵graphN+1。若i和j是直连的邻居，用graphi表示边(i，j)的权值；若i和j不直连，不是邻居，一般把graphi赋值为无穷大(INF)。在稠密图中，大部分点之间有边，此时graph[][]大部分是权值；在稀疏图中，大部分点之间没有边，此时graph[][]大部分是INF。一般情况下，只需要存储存在的边的权值，不存在的边并不需要存储，所以邻接矩阵适合稠密图，不适合稀疏图。

邻接矩阵的存储空间大小为N2，如当N=5000时，N2=25000000。

邻接矩阵的优点很多：①简单直接，编程极简；②查找边(i，j)非常快，复杂度为O(1)；③适合稠密图。邻接矩阵的缺点是：①在表示稀疏图时十分浪费空间；②边有多个权值时不能存储，即不能存储重边。

矩阵能表示有向边或无向边。若是无向图，可以定义边(i，j)的权值为graphi=graphi；若是有向图，graphi是边i->j的权值，graphi是边j->i的权值。

02、邻接表

为解决邻接矩阵浪费空间的问题，可以使用邻接表。所谓邻接表，即每个节点只存储它的直连邻居，一般用链表存储这些邻居。规模大的稀疏图一般用邻接表，因为非直连的节点不用存储，所以节省了空间，存储效率非常高，存储复杂度为O(n+m)，n为节点数量，m为边数，几乎已经达到了最优的复杂度，而且能存储重边。邻接表的缺点是找一个节点的邻居时，需要逐个遍历它的邻接表，速度不如邻接矩阵快，不过邻居的数量一般不多，影响不大。

常用STL vector实现邻接表。

struct edge{                         //定义边
int from, to, w;                 //边：起点from，终点to，权值w
edge(int a, int b,int c){from=a; to=b; w=c;}  //对边赋值
};
vector<edge> e[N];                   //e[i]：存第i个结点连接的所有的边
//初始化：
for(int i=1; i<=n; i++)   
e[i].clear();
//存边：
e[a].push_back(edge(a,b,c));         // 把边(a,b) 存到结点a的邻接表中
//遍历结点u的所有邻居：
for(int i=0; i < e[u].size(); i++) { //结点u的邻居有e[u].size()个
//for(int v : e[u])  //上一行的简单写法。见5.6节洛谷P1352和10.6节洛谷P2607的代码
    int v = e[u][i].to, w = e[u][i].w;
    …  
}

提示/

本文分析图算法复杂度时，用n表示点的数量，m表示边的数量。

03、链式前向星

分析邻接表的组成，存储一个结点u的邻接边，其方法的关键是：先定位第1个边，第1个边再指向第2个边，第2个边再指向第3个边......根据这个分析，可以设计一种极为紧凑、没有任何空间浪费、编码非常简单的存图方法。用图1的例子说明，图中没有标注边权。

■ 图1 有向图例子

图2是生成的存储空间。head[]是一个静态数组，u是结点编号，head[u]指向u的一个邻居的存储位置。struct edge是一个结构静态数组，edge[i].to存储邻居结点编号，edge[i].next指向下一个邻居结点的存储位置。

■ 图2 链式前向星存图

以结点2为例，从点2出发的边有4条(2-1)、(2-3)、(2-4)、(2-5)，邻居是1、3、4、5。

（1）定位第1个边。用head[]数组实现，head[2]指向结点2的第1个边，head[2] = 8，它存储在edge[8]这个位置。

（2）定位其他边。用struct edge的next参数，指向下一个边。edge[8].next= 6，指向下一个边在edge[6]这个位置；然后edge[6].next = 4；edge[4].next =1；最后edge[1].next = -1，-1表示结束。

struct edge的to参数记录这个边的邻居结点。例如edge[8].to = 5，第一个邻居是点5；然后继续通过to找其他邻居，edge[6].to = 4，edge[4].to = 3，edge[1].to = 1，得到邻居1、3、4、5。

上述存储方法被称为“链式前向星”，是空间效率最高的存储方法，因为它用静态数组模拟邻接表，没有任何浪费。

下面的代码用函数addedge()存一条新的边。按以下顺序存储图中所有的边：(1-2)、(2-1)、(5-2)、(6-3)、(2-3)、(1-4)、(2-4)、(4-1)、(2-5)、(4-5)、(5-6)，得到图10.2。输入的顺序会影响存储的位置。从执行过程可知，每加入一个新的边，都是根据递增的cnt直接存在edge[]的末尾空位置。代码中的from表示边(u, v)的起点u，一般情况下可以省去，因为head[u]的u就是起点，查u的邻居时，u本身是已知的。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5, M = 2e6+5;           //1百万个点,2百万条边
int head[N],cnt;                          //cnt记录当前存储位置
struct {
    int from, to, next;   //from=边的起点u；to=边的终点v；next = u的下一个邻居
    int w;                //边权，根据题目设定有int，double等类型
}edge[M];                 //存边
void init(){                                    //链式前向星初始化
    for(int i=0; i<N; ++i) head[i] = -1;        //点初始化
    for(int i=0; i<M; ++i) edge[i].next = -1;   //边初始化
    cnt = 0;
}
void addedge(int u, int v, int w){    //前向星存边(u,v)，边的权值为w
   edge[cnt].from = u;                //一般情况下，这一句是多余的。
   edge[cnt].to = v;
   edge[cnt].w = w;
   edge[cnt].next = head[u];
   head[u] = cnt++;
}
int main(){
    init();                            //前向星初始化
    int n, m;  cin>>n>>m;              // 输入n个点，m条边
    for(int i=0;i<m;i++){int u,v,w; cin>>u>>v>>w; addedge(u,v,w);}      //存m条有向边
    for(int i=0;i<=n;i++) printf("h[%d]=%d,",i,head[i]); printf("\n");  //打印head[]
    for(int i=0;i<m;i++) printf("e[%d].to=%d,",i,edge[i].to); printf("\n");    //打印edge[].to
    for(int i=0;i<m;i++) printf("e[%d].nex=%d,",i,edge[i].next); printf("\n"); //打印edge[].next
    for(int i=head[2]; ~i; i=edge[i].next)    //遍历结点2的所有邻居。~i可写为i!=-1
        printf("%d ",edge[i].to);        //printf("%d-%d ",edge[i].from,edge[i].to);
    return 0;
}

下面是输入和输出的例子：

示/

上面代码默认结点编号范围是1 ~ n，但有的题目是0 ~ n-1，请根据情况灵活处理。

上面的链式前向星代码可以简化，在以下代码中，用0而不是-1表示空，这样做能省去init()函数。本书部分图论例题采用了这个写法。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5, M = 2e6+5;             //1百万个点,2百万个边
int cnt=0,head[N];                          //cnt等于其他值也行，根据题目要求赋值 
struct {int to, next, w;} edge[M];
void addedge(int u,int v,int w) {
    cnt++;
    edge[cnt].to = v;   
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
int main() {
    int n, m;  cin>>n>>m;    
    for(int i=0;i<m;i++){int u,v,w; cin>>u>>v>>w; addedge(u,v,w);}  
    for(int i=head[2]; i>0; i=edge[i].next)  //遍历结点2的所有邻居
        printf("%d ",edge[i].to);            //输出：5 4 3 1
    return 0;
}

示/

除了这三种存图方法，其实还有别的方法。例如一种极为简单的存图方法：直接用一个结构体数组存所有的边。这个方法的优点是省空间，缺点是无法快速查某个边。它也有自己的应用场景，见“10.8.4 Bellman-ford”、“10.9.1 Kruskal算法”，在这两个算法中不需要查特定的边。