蓝桥集训之BFS、DFS和链式前向星

配套视频

https://www.bilibili.com/video/BV1RD4y1F7Fq

一、建图基础 前言

图一般定义为二元集；

由顶点集与边集构成。

或者更抽象的说，由一个集合(顶点)，和集合上的关系（边）构成

图的基本概念名词

邻接矩阵

邻接表

度，出度，入度

• 在有向图中，箭头是具有方向的，从一个顶点指向另一个顶点，这样一来，每个顶点被指向的箭头个数，就是它的入度。从这个顶点指出去的箭头个数，就是它的出度

有向边，无向边，重边。

环，自环。

闭包等

有向图和无向图

有向图就是边在表示的时候有一个单向性，无向图就是在边表示的时候有一个双向性，这一点在我们建图的时候也能提现到

邻接矩阵（稠密图）

我们用一个二维矩阵来表示这个图，二维矩阵的两个维度就分别对应着起点，和终点，我们习惯把第二维度的作为起点，第一维度的作为终点

那么对于有向图来说我们只用不断地维护顶点地关系即可，举个栗子

m p [ i ] [ j ] mp[i][j] mp[i][j]表示地是 i i i这个点指向j这个点的时候地边的权值

邻接表（稀疏图）

对于邻接表而言，我们建图的方式就很多了，我这里举两个常用的方式

使用容器vector

大家都知道，vector是一个变长数组的容器，它会根据你的需求来分配对应的空间，所以我们就可以根据这个来建图

我们先定义一个结构体，这个结构体要包含哪些信息呢：终点信息、边权值

那么我们就能写出来了：

struct Edge{
    int v,w;//v表示的是终点、w表示的是起点到重点的权值
};
vectorE[N];//这个N是根据你的顶点的大小来决定的

这样一来我们发现，我们也能维护这个图push_back(node)

使用原生数组

由于数组不能是变长的，有些时候又因为点不多，但是都挺大，造成了数组空间不够，我们因此就能想到链表的结构来维护这个图，于是你就得到了下面这个结构体

struct Edge{
    int v,w;
    struct Edge* next;
};
Edge E[N];

这样每一个点就是一条链表，这样我们也能很好的维护这个图

链式前向星 前向星

前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.

我们用 l e n [ i ] len[i] len[i]来记录所有以 i i i为起点的边在数组中的存储长度.

我们用用 h e a d [ i ] head[i] head[i]记录以 i i i为边集在数组中的第一个存储位置.

举个栗子：

假设我们有这样一个图：

这个边的输入情况如下：

1 2

2 3

3 4

1 3

4 1

1 5

4 5

排完序后可以得到如下边顺序：

编号：1234567起点：1112344终点：2353415

然后我们就能获得head数组和len数组的信息了

headlenhead[1] = 1len[1] = 3head[2] = 4len[2] = 1head[3] = 5len[3] = 1head[4] = 6len[4] = 2

这个建图的方法能帮我们优化后面要学的DFS和BFS，但是仅仅是这样就足够了吗？答案显然是不够，我们可以学到一种更优的建图方法：链式前向星

链式前向星

我们根据前面所学的启发可以想到建立一种新的边的结构体

struct Edge{
    int last;
    int to;
    int w;
};

其中edge[i].to表示第 i i i条边的终点,edge[i].last表示与第 i i i条边同起点的上一条边的存储位置,edge[i].w为边权值.

另外受到前向星的启发，我们还有一个head数组，它是用来表示以 i i i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实在以 i i i为起点的所有边的最后输入的那个编号.

我们将head数组初始化为-1或者0，cnt初始化为0，cnt表示的是当前加的边数，然后对它不断地更新操作，很显然我们能得到这样地一个加边地操作

void add(int u,int v,int w)
{
    edge[cnt].w = w;//更改边权
    edge[cnt].to = v;//更改下一个点的位置
    edge[cnt].last = head[u];//记录上一个以u为终点的边的位置
    head[u] = cnt++;//更新一下head数组
}

还是用上面的图，我们就能得到如下的边权关系

edge[i].toedge[i].lasthead[i]edge[0].to = 2edge[0].last = -1head[1] = 0;edge[1].to = 3edge[1].last= -1head[2] = 1edge[2].to = 4edge[2],last = -1head[3] = 2edge[3].to = 3edge[3].last = 0head[1] = 3edge[4].to = 1edge[4].last = -1head[4] = 4edge[5].to = 5edge[5].last= 3head[1] = 5edge[6].to = 5edge[6].last = 4head[4] = 6

head[i]就是保存的最后的那条边的编号、这个链式前向星在遍历图的时候是倒着遍历的，所以我们用其中一个成员last表示上一个节点的位置，这样对图也不会有什么影响

所以我们就能得到一个遍历的方式：

for(int i=head[u];i!=-1;i=edge[i].last)//中间那个循环判断也可以写成~i，不懂得同学可以去了解一下负数补码

二、DFS（深度优先搜索） 问题引出

我们想知道在一个迷宫里面是否有一个路线能让我们从起点走到终点，无论改路径是否是最优的

例题：http://acm.mangata.ltd/p/E427

思路

由于我们只想知道这个迷宫有没有解，所以我们期望能够一条路就走到终点，然后保存这个信息，但是这个过程中我们很可能就走到了一个死路，正常的思维会怎么想呢？退回来，一只退回到有没走过的岔路口，然后走向另一个方向，然后重复这个过程直到找到了终点，或者说所有的点都走过了，那么我们就退出，这就是深度优先的思想。

重点

重点理解一下这个递归的过程，递的过程其实就是往下一个地方走，归的过程就是走到死胡同了，我们要返回到岔路口。这里归的过程也就是回溯，回溯的状态是非常关键的，有的时候我们要利用回溯这个过程记录一些信息，比如路径、权值和等，所以DFS不仅能运用到路径的搜索，在很多地方都能用到

实现的方式

实现的方式也就是通过递归实现，不断向下探索，然后遇到死胡同就归上来

给出一个模板：

void dfs(int x,int y){//x、y表示的是坐标点的位置
	if(vis[x][y]) return;//这个表示已经访问过了
	vis[x][y] = true;//如果没有访问过，那么我们现在访问过了
	ans++;
	for(int i = 0;i  0 && nx  0 && ny