图论基础 [从入门到黑题]

前言

楼主打模拟赛自闭就出来写blog了

本编blog目的是写一篇全网最详细的图论从基础到各种算法（在我会的范围，因此目前会不断更新）。

update : 如果这个人没有退役就会把这篇blog更完

图

Q ：什么是图？

A ：在计算机科学里，图大概长这个样子（这是一张我随手画的图）：

因此，图的非正式定义很简单，就是 有一些结点(node)，有一些边(edge)将点连起来。

我们可以形象的理解为 有若干个城市，每个城市间有一些道路相连，其中，城市就是结点，道路就是边。图就是整个城市群（这个是最短路里常用的图论模型）

我们发现图就两个东西 ：结点和边，因此可以看见一些学术性的blog或百科里把图抽象成 点集 \(V\) 和 边集 \(E\) （这里是集合知识，不知道不大要紧）。

因此，我们要保存一个图，或获得一个图的信息，就只要知道它的 结点与边 的情况即可。接下来我们从 结点 与 边 角度继续来了解图（下面还是基础知识，只要了解，理解，留下印象）

有向图 与 无向图

这里是从边的角度来了解图

Q ：什么是有向图和无向图？

A ：这你得知道什么是有向边和无向边。

Q ：那什么是有向边和无向边？

A ：

上图是一条无向边，我们称这是一条由 1 到 2 的无向边，（标了 1 就是编号为 1 的结点）。边的一般形式是 \((u,v)\) ， 所以这里就是\(（1,2）\)

在无向边里，1可以通向2, 2可以通向1

用城市群这个比喻：我们可以把它看成 城市1 与 城市2 之间有一条道路，这条路是双向公路。这就是无向边的意义。

上图是一条有向边。与上上这条无向边一样，就是多了一个箭头。这个箭头表示 只能由 1 通向 2

我们同样可以把它看成 城市1 与 城市2 之间有一条道路，但是是一条单向公路

所谓 无向图 与 无向边，就是在一张图中的边是无向边还是有向边。

• 无向图中的边就是无向边，每条边的两个端点可以互相到达。相当于城市之间全部是双向公路，汽车可以来回通行

• 有向图中的边就是有向边，端点只能沿箭头方向走到另一边。相当于城市之间是单向公路，汽车只能沿公路方向通行

（下图是一张经典的有向图）

有向图与无向图一般会由题目给出

小问题：有向图中的两个城市可否互相到达（达到无向图这个效果）？

可以。其实无向图就相当于一种特殊的有向图。就是建了方向相反的两条有向边。

从边的角度浅显的了解了一下图，接下来抽象地来理解一下图

状态与状态间的关系 和 图的联系

之前一直在用城市来理解图，为了能让自己的知识与思维扩展开来，我们要从图的本质上来理解它。

图可以用来表示状态与状态之间的关系

Q ：如果来理解 图可以表示状态与状态间的关系？

我们可以把一个状态看成一个结点，如果能从状态\(u\) 通过某些方式达到 状态\(v\) 我们就可以在图上把 \(u->v\) 连一条边。连完边后，整个状态之间就变成一张有向图。

（这里要自己联想联想，感悟一下。。。）

这样说太抽象了，我们来看一道例题：

P1135 奇怪的电梯

有n层电梯，每个电梯可以到按按钮通向另一层电梯。问从A电梯到B电梯最少要多少步

（其实是Bfs的模板题） 我们把每个电梯看成一个结点，通向其他电梯就是其他结点，建一条有向边，整个问题就可以抽象成一张图了。

目前为止，我们初步知道了图是什么————表示问题的一种方式；图的样子————结点和边；可以说，我们从理论上理清了图的概念。接下来，我们要把概念用代码实现出来，学习 图的储存

图的储存

图的储存有三种常用的方法，邻接矩阵存图，链式前向星存图，vector存图，其中邻接矩阵存图代码简易但效率低下，前向星和vector效率相当，vector略慢。读者务必掌握前向星，因为掌握了前向星也不难理解其他两种存图，并且本篇blog的代码多用前向星存图。

邻接矩阵存图

（我才不会告诉你邻接矩阵就是一个二维数组）

给你一张有向图 输入n,m 表示这张图有n个点m条边，之后有m行，每行有两个数 u,v 。请你把这个图保存下来。

（这是一般图论题最前面部分）

const int N = 1007;    //n<=1000
int g[N][N];    //graph 图； 这个二维数组就是邻接矩阵，请看下面
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i) {    //输入m条边
        int u,v;
        cin>>u>>v;
        g[u][v] = 1;    //因为开始g[u][v]=0表示u->v没有路径，如果为1则表示有一条边
    }
    return 0;
}

可以看出，邻接矩阵存图的代码浅显易懂。如果 g[u][v]==1 就表示 \(u->v\) 有边。

链式前向星

邻接矩阵的空间大小与点数有关，当结点达到 n=10000 时，它不再适用。因为一般题目中的点很多，但是边往往只有 m<=10 0000，于是算法大神发明了以边数的存图算法————链式前向星

我们来看一张图：

1 点有三条连出的边，（1,2），（1,3），（1,4），我们可以称这是 1点的三条出边。

所谓链式前向星，就是把每个点的出边保存在一起。代码

int cnt,head[N];
struct Edge {
    int next,to;    //next表示链表中下一个元素的下标，to是当前点边指向的点
}edge[M];