数据结构：第六章 图

一、图的基本概念

1.1定义

ps：图不可以为空图。
对于图中的边，两头必须要有结点。
边集是可以没有的，如上图最右边。

1.2有向图、无向图

关于无向图和有向图的应用如下

比如你微信里的好友关系，你要和一个人建立关系（也就是图的两个结点连上），你只需要加1次就可以了，也不需要你加我，我还要加你。具体应用有，你可以根据一个人在微信好友这个图中的边有多少条，判断他是不是朋友很多。

再比如微博里面的关注，一般都是吃瓜群众关注一些明星，而明星可能都不知道吃瓜群众这个人。所以这种关注是有方向的。具体应用有，你可以根据某个明星在微博关注这个图中，有多少条指向它的边，来判断这个明星的热度

1.3顶点的度、入度、出度

对于无向图来说，每个边都会给与之相连接的两个结点分别贡献一个度，
所以无向图顶点的度之和应该是无向图边的数量*2

对于有向图来说，任何一条弧，它都会给其中一个结点贡献一个出度，为另一个结点贡献一个入度。
所以有向图所有顶点出度之和 与 入度之和应该是相同的，并且数值上刚好等于弧的条数

1.4顶点-顶点关系的描述

如果G是连通图，则最少有n-1条边
举例如下：
现在有5个顶点，让它们成为连通图，则至少需要4条边

如果G是非连通图，则最多有C²_n-1条边
举例如下：
现有5个顶点，让它们成为非连通图





对于强连通图常见考点就是，如果这个有向图，有n个顶点，保证它强连通最小边数是n条

最少的情况就是，我们让这几个顶点成为一个回路，那么从任何一个结点出发都能找到其他顶点

1.5子图和生成子图

生成子图就是包含原图的所有顶点，但是你可以去掉一些边

1.6连通分量

连通分量是用于描述无向图的

极大连通子图指的是这个子图除了它必须连通之外，它还要包含尽可能多的顶点和尽可能多的边

1.6强连通分量

强连通分量是用于描述有向图的

上图中ABCDE五个顶点是互通的，并且可以到F，但是F不能到ABCDE，所以F和ABCDE不是强连通的。

我们把ABCDE摘出来，它就是一个极大强连通子图。它已经尽可能包含了强连通的顶点。

另外F和G也是单独作为两个极大强连通子图。

所以，这个有向图有三个强连通分量。

1.7生成树

一个连通的无向图，它的生成树是指包含这个图里面全部顶点的一个极小的连通的子图。

也就是说这个子图要包含原图里面所有顶点，且要连通，且要极小，所谓极小就是指在这个子图里面的边要尽可能的少，对于上面的无向图G（共5个顶点）来说，我们可以加入4条边使之连通。
如果再加1条边，就不是极小连通子图了

这样就构造了原图的一个极小连通子图，也可以说是构造了它的一个生成树。注意，生成树是可以有多个的。

对于一棵生成树而言，如果它有n个顶点，那么显然它有n-1条边。
如果再多一条边就生成一条回路了。
如果再少一条边，又会变成非连通图

1.8生成森林

1.9边的权、带权图/网

图这种数据结构，除了在各个结点保存这些顶点相应信息，有时也需要给各个边赋予一些数值。用这些数值来表示一些现实含义的信息。

比如在地图里面，你可以把各个边视为两个地方，看它们相距多少公里。

这种每条边都有一个权值的图，就称为带权图，也称为网。

每条边有了各自的权值之后，我们可以把顶点之间的路径赋予一个新的属性，叫作带权路径长度。
所谓带权路径长度就是某条路径上所有边的权值之和。比如北京到上海，带权路径长度就是200+600=800

1.10几种特殊的图

注意：n个顶点的图，如果边大于n-1条，那肯定是有回路的、

对于有向树，只有一个顶点入度为0，其实就是树的根结点，然后其他的都是入度为1

1.11小结

二、图的存储及基本操作

2.1邻接矩阵法

2.1.1邻接矩阵存储不带权图

其实邻接矩阵的原理很简单，看下图

比如上图的无向图，A和B、C、D之间有一条边。而由于无向图的边是没有方向的，就意味着B、C、D与A之间也有一条边。

无向图的每一条边，在邻接矩阵中都会对应2个1。

而A和E之间是没有边的，所以A和E对应元素为0

在邻接矩阵法中，0表示两个顶点互相不连接。而1则表示两个顶点相互连接

再看上图的有向图，A行B列的元素是1，但是B行A列元素是0。因为有向图的边是有方向的，A可以指向B，但B不可以指向A。

下面是邻接矩阵的实现，我们就用一个二维数组就可以实现了

#define MaxVertexNum 100
typedef struct{
    char Vex[MaxVertexNum];//顶点表
    int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵,边表
    int vexnum,arcnum;//图当前顶点数和边数/弧数
}MGraph;

我们这里定义一个int型的二维数组Edge用来表示各个边的信息，这个二维数组大小为100*100，也就是说，我们这个顺序存储的图里面，最大可以有100个顶点。

我们还定义一个一维数组Vex，这个一维数组用于存放各个顶点的信息，比如我们这个例子中的结点信息其实就是ABCDEF这样的字符，我们定义为char类型。但你也可以在这顶点中存放更多信息，你就定义一个结构体就完了。

由于我们在邻接矩阵中只需要存放0和1两种状态，你可以把边的信息类型，也就是int Edge[MaxVertexNum][MaxVertexNum];这里的int可以换成bool类型或者枚举类型只占1个字节。

需要注意的是，我们每个结点A、B、C…它们有各自的数据A、B、C…，但是另一方面，这些结点的数据在这个数组char Vex[MaxVertexNum]里面存放的具体位置是有一个编号的，比如A是下标0的位置，B是1，C是2。。。

用这些结点在数组中存放的下标，和邻接矩阵的行和列进行对应，就可以对应上了。比如你现在要判断A和B之间是否有相互连接的边，就可以在这个二维数组中找它的第0行第1列找到AB是否相连

总之，如果邻接矩阵的某个元素为1，那么就意味着对应的那条边/弧是存在的。如果是0则反之。

现在思考这样一个问题：给你指定一个结点，要你求这个结点的度、出度、入度？

先看无向图

假设现在要求指定结点B的度，那我们可以检查一下和B对应那行非0元素有几个，我们发现有3个，那B的度就是3呗。

无向图找某个结点的度，你检查邻接矩阵的列也可以

所以，对于无向图来说，求顶点的度，我们可以遍历和它对应的那一行或那一列，检查非0元素个数就可以求出顶点的度了

显然，这个操作的时间复杂度为O（n），n是指顶点的个数。当然你也可以写成O（|v|），|v|表示顶点的个数。

再来看有向图

假设我们现在要你求A这个结点的入度、出度还有度。

A的出度，就是A所在行（第一行）非0元素个数为1
A的入度，就是A所在列（第一列）非0元素个数为2
A的度=出度+入度=1+2=3

推广开来

所以，求有向图某顶点的出度、入度、度的时间复杂度为O（n），n是指顶点的个数。当然你也可以写成O（|v|），|v|表示顶点的个数。

2.1.2邻接矩阵存储带权图

上面是讨论的不带权的图，我们只需要表示除各个顶点有没有邻接的关系就可以。
如果我们要存一个带权图（也称网），我们只需要在对应位置标上两个顶点对应边的权值即可。

如果两个顶点之间不存在边，我们可以用无穷来表示两顶点之间不存在边。

实现代码如下：

#define MaxVertexNum 100//顶点数目的最大值
#define INFINITY //宏定义常量“无穷”
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];//顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];//边的权
    int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

ps：也有的教材是把自己指向自己的值设为0，如下图，这些都是可以的，具体看做题是怎么样。

下面我们对邻接矩阵进行一个性能分析：
既然它是要用于存储的，我们肯定是要关心这个数据结构它所需要占用的空间复杂度是多少的。

如果这个图有n个顶点，存储各个顶点的信息需要定义一个一维数组，也就是需要O(n)这样一个存储空间。

另外还需要n*n的二维数组来存储和这些顶点相关的边的信息，所以存储边又需要O(n^2)

O(n)+O(n^ 2)保留阶数更高的即可，也就是O(n^2)

而一个图里面，如果顶点多，边数少，邻接矩阵很多空间都是浪费掉了。

所以，邻接矩阵这种存储方式适合存储稠密图

另外，由于我们的无向图，邻接矩阵是一个对称矩阵，所以我们可以用对称矩阵压缩存储的方法，也就是只存储上三角区或者下三角区。

2.1.3邻接矩阵的性质

我们这里讨论的邻接矩阵是指不带权的图，也就是矩阵元素只有0和1的图

我们记图G的邻接矩阵为E

邻接矩阵的n次方，Eⁿ 的元素Eⁿ [i][j]等于顶点i到顶点j的长度为n的路径的数目

举个例子，现在我们有上面这个图的邻接矩阵，用该矩阵乘它自己，得到该邻接矩阵的二次方

那么现在E² 第一行第四列的元素怎么计算？
应该用邻接矩阵的第一行×第四列，然后分别相加

E² [1][4]=(e11 * e14 )+ (e12 * e24) +(e13 * e34) + (e14 * e44) =1

我们来看一下上面这些数值有什么现实意义

比如e12=1，表示矩阵E中1行2列，也就是AB那条边是1，也就是A到B是有条边的。

再看e24，e24就是邻接矩阵2行4列呗，也就是BD那条边，e24=1表示B到D是有条边的。

e12 * e24=1就表示我们可以找一条路径，先从A到B，再从B到D，
E² [1][4]=1就表示，从A到D长度为2的路径有1条

再举个例子：
现在给E的三次方，其实就是E的二次方再乘E

现在来看E³ [1][4]=1，这就表示A到D长度为3的路径有1条

解释一下：
E³ [1][4]=1这个数是由左边矩阵第一行乘右边矩阵第四列得到的，

左边矩阵第1行第1列=1表示从A到A长度为2的路径有1条。
但是左边矩阵第1行第4列=0，表示从A到D长度为1的路径是0条。
那么A->A->D这种情况就不成立。

再来看左边矩阵第1行第3列=1表示A到C长度为2的的路径有1条。
而右边矩阵第3行第4列=1表示从C到D长度为1的路径有1条
那么A->C->D这种情况就是成立的

2.1.4小结

2.2邻接表法

2.2.1定义及代码实现

上小节我们是介绍了顺序存储实现的邻接矩阵，因为我们是用了一个一维数组和一个二维数组实现的。

而该小节中，我们学习的邻接表是用顺序存储和链式存储的方式来实现的

我们用一个一维数组AdjList来存储各个顶点的信息，其中包括顶点的数据域，和指向该顶点的第一条边或者弧的指针。

//顶点
typedef struct VNode{
    VertextType data;//顶点信息
    ArcNode *first;//第一条边/弧
}VNode,AdjList[MaxVertexNum];

当我们声明一个图的时候，其实就是声明了顶点结点的一个数组，另外，我们还需要记录当前这个图里面具体有多少个结点，多少个边。

//用邻接表存储图
typedef struct{
    AdjList vertices;//顶点数组
    int vexnum,arcnum;//顶点数量，边数量
}ALGraph;

而各条边/弧，也会有与之对应的结点

//边/弧
typedef struct ArcNode{
    int adjvex;//边/弧指向哪个结点
    struct ArcNode *next;//指向下一条弧的指针
    //InfoType info;//如果存储的是带权图，可以在这里加入权值
}

ps：这种邻接表法其实和我们之前讲的“树的孩子表示法”是相同的一种实现方式

刚才的例子是一个无向图，同样的，我们也可以用一个邻接表来存储有向图。

原理都是一样的，比如现在有一条弧从A指向B，那么A的first后面就跟一个1,1表示B的下标。

也就是说，如果用邻接表来存储有向图，那么每个结点后面跟的信息其实就是该结点向外射的一条弧。

而对于无向图来说，每条边都会对应2个结点。比如A是0号结点，B是1号结点
那么红色箭头所指的结点表示从0号指向1号的一条边

这个蓝色箭头表示的是从1号指向0号的一条边

但是看图我们可以知道，其实这两条边就是一条边

所以，在无向图中，其实数据是有冗余的边结点的数量应该是边的实际数量的两倍，因为每条边都有这样的两份数据。
所以存储无向图，总共需要的空间复杂度为O(|V|+2|E|)

而有向图，每条弧只会对应一条边结点，所以整体空间复杂度为O(|V|+|E|)

2.2.2如何求无向图顶点的度

对于无向图来说，要求一个顶点的度是多少，我们只需要遍历和这个顶点相关的这个链表。

举个例子，现在有下面的无向图，要求顶点A的度是多少

我们只需要遍历和顶点A相关的边链表就可以，比如这里A的边链表里有3个，那A的度就是3。

同时，遍历A这个边链表，我们就可以找到和顶点A相连的所有边

2.2.3如何求有向图顶点的入度、出度

有向图的度=入度+出度

要找到一个结点的出度很简单，我们只需要遍历和这个结点相关的边结点的链表即可。

比如现在要找E的出度，那么我们发现和E相关的边结点的链表里有1和2，就是从顶点E出去的弧指向1和2呗，就是E到B 和 E到C是存在的

要找到一个结点的入度就比较麻烦了，比如我们现在要统计A结点的入度（或者说，要找到指向A的弧），唯一的办法就是把所有结点的边链表都依次遍历一遍，看边链表里面是否有0

所以，如果用邻接表要找到指向某个结点的弧，那是非常麻烦的，时间复杂度也会很大。

2.2.4邻接表的注意点和邻接矩阵对比

需要注意的是，邻接表的表示方式是不唯一的，比如A这个结点，它和B、C、D结点都相连。到表里面就是0号结点和1、2、3相连。

这个1、2、3的顺序是可改变的
比如下图

也就是说，各个边在链表中出现的先后顺序是任意的。
所以我们给定一个图，它的邻接表表达方式不唯一。

而我们上小节介绍的邻接矩阵，我们只要确定了各个顶点的编号，对于某个给定的图，它所对应的邻接矩阵表示方式一定是唯一的。

ps：这个表达方式唯一不唯一，选择题会比较喜欢考察。

2.2.5小结

邻接矩阵主要问题是空间复杂度高，只适合存储稠密图，空间复杂度为O（|V|²）

而邻接表就可以很好的解决这个问题，
可以让有向图空间复杂度变成O（|V|+2|E|），无向图空间复杂度变为O（|V|+|E|）
所以邻接表更适合存储稀疏图（你要存稠密图也可以）

另外需要注意的是，对于一个给定的图，邻接表表示方式不唯一；邻接矩阵表示方式唯一

对于找到图中某个顶点的度、入度、出度或者找到和某个顶点相连的边时，
邻接矩阵只需要遍历对应的行和列
邻接表要找入度就比较麻烦。

2.3十字链表

对于十字链表，我们直接看图比较好理解

现在有一个有向图，如下，它有结点ABCD，这四个结点分别会存在数组0123的位置

对于A结点来说，有一个弧是A指向B，还有一个弧是A指向C。

所以，从A结点的绿色指针，向右找，会发现第一条弧结点的信息是从0号结点指向1号结点（也就是A指向B）

我们继续顺着绿色指针往下找，可以找到下一个弧结点，表示从0号指向2号结点（也就是A指向C）

然后发现该弧结点绿色指针已经为空了，就说明没有以A为弧尾的边了

这样就找完了从A指向其他结点的弧。

那么现在如果要求指向A的弧呢？
我们前面找从A指出去的弧，是沿着绿色指针找。

那么现在找指向A的弧，我们就沿着橙色指针找即可。

现在由图可以看出，指向A的有两条弧，分别是C指向A、D指向A

我们现在沿着A的橙色指针出发，找到第一个弧结点，发现是2号指向0号（也就是C指向A）

继续沿着橙色指针往下找，找到第二个弧结点，发现是3号指向0号（也就是D指向A）

然后发现橙色指针为空了，说明没有指向A的弧了

这样就找完了指向A的两条弧

显然，十字链表法的空间复杂度为O(|V|+|E|)
|V|表示顶点个数，|E|表示的是边的个数

需要注意的是，十字链表法只能用于存储有向图！！！

2.4邻接多重表

还是老规矩，直接上图帮助大家理解

邻接多重表和刚才介绍的十字链表非常相似。

比如现在有无向图，它有五个顶点ABCDE，对应到数组的0123位置

每个顶点除了数据域外还需要有一个指针，指向和当前顶点相连的第一条边。

举个例子：
比如A这个顶点，和它相连的有B和D

我们顺着A结点的指针往后找，可以找到一个边结点，这个边结点就是0号和1号相连的边（即A和B相连的边）

然后需要注意，我们0号是在橙色里面，也就是i=0，这里橙色指针指向的是依附于i结点的下一条边

那我们继续沿着橙色指针往下找，就可以找到下一条弧结点，是0号和3号（也就是A和D相连的边）

再举个例子：
来看B这个结点，和它相连的有ACE三个

那么我们从B节点指针往后找，找到一个边结点，该边结点是0和1，也就是A和B的边

由于是无向图，所以B结点的编号1是橙色还是绿色其实无所谓的，因为我们这里是把1放在边结点的绿色，那我们就沿着绿色指针往下找

发现第二个边结点，是2和1的，也就是B和C的边

继续沿着绿色指针往下找，发现是4和1，也就是E和B的边

如果还想继续玩下找，发现当前边结点的绿色指针已经空了，也就是说和B相连的边已经找完

所以和B相连的结点有ACE

ps：如果你的无向图是带权图，那么你可以在边结点中加一个info，表示权值

小结
如果用邻接多重表的方式来存储无向图，想要找的和一个顶点相连的边是很方便的。

同时，由于每条边只会对应一个边结点，所以就不需要向邻接表那样同时维护两份冗余数据。这种特性可以保证我们在删除一个结点或者一条边时方便很多。

注意，邻接多重表只适合存储无向图！！！

由于十字链表和邻接多重表的代码逻辑比较复杂，考研也不太可能出现让你写代码，大家只需要理解这两种存储方式的一些特性。

2.5图的基本操作

考研中最常考的，还是邻接矩阵和邻接表这两种存储结构。所以，该小节我们只探讨邻接矩阵和邻接表怎么实现这些基本操作。

2.5.1判断图G是否存在边<x,y>或（x，y）

2.5.1.1情况1：:无向图

现在如果存储的是无向图，那么用邻接矩阵来存储，要判断两个顶点之间是非常方便的

比如现在要找B和D之间是否有边，那么我们在邻接矩阵中看B行D列的值即可，值为1就是有边，值为0就是无边。

所以，邻接矩阵实现判断是否有边，只需要O（1）的时间复杂度

再来看，用邻接表来判断BD是否有边，我们就可以检查B这个边界点有没有D那个序号

发现B的边结点只有0、4、5没有3号（D结点序号为3），所以B和D之间没有边。

如果要用邻接表，要判断B和D之间是否有边，我们可以检查B的边结点有没有D。

最好的情况就是我们要找的目标结点所对应的编号刚好的第一个边结点，时间复杂度为O（1）

最坏的情况就是我们遍历完B的所有边结点，结果都没有发现D，而假设图一共n个结点，和B相连的最多有n-1条，也就是|v|-1条，那么时间复杂度为O（|V|）

2.5.1.2情况2：:有向图

其实对于有向图思路也是类似的，大家可以自己看下图，思路和上面无向图是一样的

2.5.2列出图G中与结点X相邻的边

2.5.2.1情况1：无向图

对于邻接矩阵来说，要找到和某个顶点相连的所有边，你就遍历那个顶点在邻接矩阵中对应的那一行就行了。

比如你现在要求C结点相邻的边，那就遍历邻接矩阵中C所在的那一行（或列），看哪些是1就行了

所以，用邻接矩阵完成该基本操作时间复杂度为O（|V|）

如果用邻接表的话，如果当前存储的是无向图。那么我们想要找到和某个顶点相连的边，只需要遍历和它相连的边结点的列表就可以

最好的情况就是当前结点只有一个边结点，时间复杂度为O（1）

最坏的情况当前结点有n-1个边，也就是|V|-1个边，遍历完整个链表需要时间复杂度为O（|V|）

2.5.2.2情况2：有向图

如果存储的是有向图，用邻接矩阵方式，你要找到和某个顶点相连的所有边

如果是要找出边，你就横着遍历当前结点的边结点，看哪些是1，一共是遍历|v|这么多个数据。

如果是要找入边，你就竖着遍历当前结点的边结点，看哪些是1，一共是遍历|v|这么多个数据。

所以，用邻接矩阵方式，你要找到和某个顶点相连的所有边，时间复杂度为O（|V|）

如果存储的是有向图，用邻接表方式，你要找到和某个顶点相连的所有边

如果是要找出边，那么和刚才无向图的情况一样，就是遍历当前结点的边结点，看有哪些边结点就行了，时间复杂度为O(1)-O(|V|)

但如果是要找入边，我们就得遍历整个邻接表的结点及它们各自的边结点。只有遍历完所有这些边结点才可以确定到底有几条边指向当前结点。时间复杂度为O（|E|）

所以，如果是存储有向图，显然找出图G中所有与x相接的边。大部分情况肯定是邻接矩阵的方式更合理。当然，这也不是绝对的，因为如果你要存的是一个稀疏图，邻接表又有优势了。

2.5.3在图G中插入顶点x

要在图G中插入一个新的顶点X，那么新插入结点的时候，这个顶点和其他任何顶点都是不相连的，所以插入很方便

如果采用邻接矩阵，我们只需要在保存原先顶点的数组后面一个位置，写入新结点的数据，如下图：

在邻接矩阵中，与新元素对应的那行（列），就可以表示这个新结点与其他结点的连接关系。整个操作时间复杂度为时间复杂度为O（1）

如果采用邻接表的方式，实现在图G中插入顶点x
我们只需要在存储结点的这个数组末尾插入新结点的信息就可以，因为一开始新结点没有连任何边，所以把它的指针设为null即可

整个操作时间复杂度为时间复杂度为O（1）
对于有向图也是类似的，时间复杂度都是O（1），这里不再赘述

2.5.4从图G中删除顶点x

2.5.4.1情况1：无向图

比如说，现在要删除图中的C，如果用邻接矩阵存储，我们就把C对应的行和列全部变成0就行了。

然后，我们可以在顶点的结构体中，新增一个boolean变量，用于判断这个顶点是否是一个空顶点

由于只需要修改一行和一列的数据，所以时间复杂度为O（|V|）

如果我们用邻接表的方式，除了删除C结点和它的边结点，还要删除其他它相连的所有结点的中有C的边界点，如下图

那么，邻接表最好的情况当然是当前删除的结点，本身就没有连任何的边，那么
时间复杂度为O（1）

最坏的情况当然是当前删除的结点，它和其他顶点都相连，那么删除当前结点的边结点链表后，还需要依次去遍历其他顶点的边链表。

那么最坏情况 的最坏情况就是，要删的这个结点，在其他顶点的边链表中还都是最后一个。也就是说，我们要遍历所有这些边的信息，才能完成删除操作时间复杂度为O（|E|）

2.5.4.2情况2：有向图

如果是有向图，存储方式是邻接矩阵，那么删除顶点x的方法和无向图是一样的

如果是有向图，存储方式是邻接表，

删出边，很方便，我们只需要把这个结点的边结点全部删了就行

比如现在要删C这个结点，那你把C及C后面连的这整个链表删了就行了

但如果是要删入边，我们只能遍历整个邻接表了，所以删除入边的时间复杂度很大。

2.5.5若无向边（x,y）或有向边<x,y>不存在，则向图G中添加该边

显然，如果用邻接矩阵的方式，我们只需要修改x结点和y结点对应的行和列即可，时间复杂度为O（1）

如果用邻接表的话，比如我们现在要添加C和F之间的一条边，那我们就在C和F边结点的链表上添加对方的结点信息（尾插法）就行，时间复杂度为O（1），如下图

对于有向图也是类似的

2.5.6求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1

2.5.6.1情况1：无向图

如果采用邻接矩阵的方式，那么只需要从左往右扫描和这个顶点对应的边结点链表，扫描到第一个1。

最好情况就是上图，要找和C的第一个邻接点，然后第一个结点A正好与C相邻，时间复杂度为O（1）

最坏情况就是，你扫描完一整行，都没有发现和当前结点相连的结点，那么时间复杂度O（|V|）

如果采用邻接表，就很简单了，我们就只需要找到当前结点的边结点列表中第一个结点。时间复杂度就是O（1）

2.5.6.2情况2：有向图

如果是有向图，那么在邻接矩阵中找到某个顶点的出边，就需要扫描它的行；找入边，就需要扫描它的列，时间复杂度就是O（1）到O（|V|）

如果是用邻接表，那么找出边也是很方便的，你就找当前结点第一个边结点就行

但是找入边就比较麻烦了，你要遍历其他的结点，看其他结点的边结点中是否找入边最好情况就是你遍历的第一个元素就是指向当前结点的。

最好情况就是你遍历的第一个结点的第一个边结点就是当前结点，时间复杂度就是O（1）

最坏情况就是，你可能需要遍历完整个邻接表的所有边的信息，都找不到指向当前顶点的边，那么时间复杂度就是O（|E|）
由于邻接表找入边时间复杂度过高，所以一般用邻接表都是找出边

2.5.7假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1

这个基本操作需要找到y之后的，下一个和x相连的顶点。

如果是用邻接矩阵，你找到x一个邻接点y之后，你再继续往后扫描直到下一个边结点为1就行

最好情况就是，你扫描到y之后下一个边结点的值就是1，时间复杂度O（1）

最坏情况就是，你扫描了一整行，都没有找到下一个邻接点，这种情况返回-1时间复杂度O（|V|）

如果是用邻接表，给定一个边信息，你往后找一位就行，时间复杂度O（1）

2.5.7获取（设置）图G中边（x,y)或<x,y>对应的权值

给图中指定的某条边或弧获取（设置）一个权值

那这两个基本操作也就是找边（弧），所以实现这两个操作其实 和判断一条边是否存在时间开销基本一样，不再赘述

2.5.8小结

考研中比较常用到的就是图中黄色标注的FirstNeighbor（G，x）和NextNeighbor（G，x，y）。这两个操作会经常在图的遍历中使用，你在考研中直接调用这两个函数接口就行

文章来源地址https://www.toymoban.com/news/detail-620470.html

三、图的遍历

3.1图的广度优先遍历

3.1.1与树的广度优先遍历的联系与区别

我们曾经学过树，树就是一种特殊的图。对于树的层序遍历，其实就是图的广度优先遍历。

我们本节从树的角度来看图的广度优先遍历

先来回顾一下树的层序遍历：
现在有如下树

先从根结点出发，找到和根结点相邻的所有结点2、3 、4

再从结点2、3、4出发，找到和2 、3 、4相邻的所有结点5 、6、 7、 8

这样就可以依次逐层的找到树里面所有结点，并且我们在查找这些结点时，都是尽可能横向的找，这也是为什么是叫广度优先的原因。

图的广度优先遍历和这种遍历也是很类似的。
举个例子，现有如下图：

现在要从2号结点出发进行广度优先遍历，
那么首先应该访问2号结点

然后通过2号结点找到下一层的1和6两个结点

然后从1和6出发，找到它们附近的其他结点5、 3、 7（已访问过的不再访问）

然后从5、3 、7出发，找到它们附近的其他结点4、 8（已访问过的不再访问）

这样我们就完成了图的广度优先遍历。

下面我们看一下树的广度优先遍历（层序遍历）和图的广度优先遍历的联系和区别

第一、不论是树还是图，在进行广度优先遍历时，我们都需要实现这样一个操作：通过某个结点找到与之相邻的其他结点。

因为只有实现了这个操作，我们才可以一层一层的往下找到所有的结点。

对于树来说，要找到与一个结点相连的其他结点很简单，就是找它的孩子结点。

而对于图来说，我们可以用我们之前介绍的FirstNeighbor（）和NextNeighbor（）这两个基本操作来实现

第二、对于树这种数据结构，由于各个结点之间路径就不可能存在回路、环路的。所以，通过树某个结点搜索其他结点时，搜索到的结点一定是之前没有访问过的结点。

但是对于图来说就不一样了，由于图这种结构可能出现环路，如下图

而且如果是无向图，每条边可以正着走，可以逆着走，你是非常可能通过一个结点找到之前已经找过的结点的。
而解决办法也很简单，就是给各个结点加一个标记，如果被访问过就给标记赋个值。下次遇到被访问过的结点，你跳过就可以了。这样就能保证在遍历过程中，每个结点只会被访问一次。

第三、我们在实现树的广度优先遍历，也就是层序遍历时，我们需要一个辅助队列。

举个例子，现有如下树

用肉眼看，我们知道和第二层2、 3、 4相邻的是5、 6、 7、 8但是对于计算机来说，它只能一个个处理这些结点。那么，暂时还没有被处理的这些结点，我们就需要用一个队列把它保存起来。

对于图的广度优先遍历，我们也可以类似的设置一个辅助队列

图的广度优先遍历，对于上面说的三点，我们给出以下解决方案

3.1.2代码实现

bool visited[MAX_VERTEX_NUM];//访问标记数组

//广度优先遍历
void BFS(Graph G,int v){//从顶点V出发，广度优先遍历图G
    visit(v);
    visited[v]=TRUE;
    Enqueue(Q,v);//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            //检测v所有邻接点
            if(!visited[w]){//w为v未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);//顶点w入队列
            }
        }
    }
}

刚开始我们visited这个数组初始值全部设为False

现在我们从2号顶点出发，然后把visited里面的对应的2号设为true。然后让2号结点入队表示它已经被访问过了

代码往下走，是一个while循环，如果队列不为空，那么我们让队头元素出列，也就是2号顶点出队。

然后在for循环里面，我们用到刚刚提到的两个基本操作。通过2号顶点找到和2号顶点相邻的所有顶点，也就是1和6两顶点

由于1和6这两点顶点的visited数组还是False，所以我们让1和6入队，visited数组对应值置为True

然后进行下一轮while循环，由于此时队列是非空的，所以需要让队头元素出队，也就是让1号出队

然后是for循环找和1号相邻的结点，也就是2和5。但是由于我们2号的visited此时是True，所以2号不考虑。访问5号，5号visited置为True让5号入队.

然后继续下一轮while循环，处理队头的6号结点，6号结点出队，6号结点相邻的有237，由于2已经被访问过了，所以访问37，37visited置为True，37入队

然后继续下一轮while循环，处理队头的5号结点，5号结点出队，5号结点相邻的有1,1已经被访问过了，不用做别的操作了。

然后继续下一轮while循环，处理队头的3号结点，3号结点出队，3号结点相邻的有467，由于67已经被访问过了，所以访问4，4visited置为True，4入队

然后继续下一轮while循环，处理队头的7号结点，7号结点出队，7号结点相邻的有3468，由于346已经被访问过了，所以访问8，8visited置为True，8入队

然后继续下一轮while循环，处理队头的4号结点，4号结点出队，4号结点相邻的有378，由于378已经被访问过了，所以不用做别的操作了

然后继续下一轮while循环，处理队头的8号结点，8号结点出队，8号结点相邻的有47，由于47已经被访问过了，所以不用做别的操作了

至此，队列已空，整个代码流程结束，完成对图的广度优先遍历

3.1.3广度优先遍历序列

上面我们已经很详细的讲解了怎样进行图的广度优先遍历，现在我们来做几个练习：给一个出发点，完成对图的广度优先遍历，写出遍历序列

我们上面给出的序列是按你给一个顶点，然后找出它相连顶点（相邻顶点按递增顺序排的）

计算机中，如果你用邻接矩阵存，那图的广度优先遍历肯定是唯一的（图确定，邻接矩阵唯一确定）

但如果你用邻接表存，那图的广度优先遍历不唯一（图确定，邻接表不唯一），比如你现在从2出发，你找到2的相邻结点1和6。你在邻接表里面可以存1-6也可以存6-1

3.1.4广度优先遍历BFS的改进

如果我们用之前给到的代码，一旦遇到非连通图，你从2结点出发是永远无法访问到9、 10 、11的

如何处理呢？

我们不是定义了一个visited数组吗？这个数组里面记录了所有顶点是否已经被访问。

那我们在第一次调用了BFS这个函数后，我们可以检查一下visited里面是否还有结点没有被访问。如果还有没有被访问的结点，我们从这个结点出发，继续一轮BFS就可以了。

所以，我们对之前代码增加一些东西

不难发现，对于一个无向图来说，调用BFS函数的次数应该等于无向图里连通分量的数量

比如上图，我们有两个极大连通子图，也就是两个连通分量。所以要调用两次BFS

3.1.5复杂度分析

3.1.6广度优先生成树

上面介绍的图中，我们如果把结点第一次被访问是从哪些边找到的进行一个标红，我们可以得到下面这样的图

举个例子，4号结点第一次被访问其实是3号结点找过来的，我们就把34这条边进行一个标红

用这样的方式，我们对于这n个顶点的图来说，我们总共标红了n-1条边，我们把每标红的边去掉，其实就变成了树了。

这就是图的广度优先生成树了。

而同一张图，如果用邻接表存储，可能生成的树也是不同的。

但如果用邻接矩阵存储，生成的树是唯一确定的。

3.1.7广度优先生成森林

比如我们现在有非连通图

3.1.8练习：有向图的BFS过程

3.1.9小结

3.2图的深度优先遍历

3.2.1与树的深度优先遍历的联系与区别

对于树的深度，分为先根和后根遍历。而图的深度优先遍历比较类似树的先根遍历，我们这里先给大家回顾一下树的先根遍历。

比如现在有如下的树，我们用递归算法来实现树的先根遍历：

首先要visit访问的是1号结点，然后2是1的子树，访问2号

5又是2的子树，访问5号

然后5号结点下面已经没有子树了，那就无法进入下一层递归，返回到2号


对于2号结点，它还有一个子树6号，访问6号

然后6号结点下面已经没有子树了，那就无法进入下一层递归，返回到2号


而此时，2号已经没有子树了，再次往上返回到1号

1号还有子树3，访问3号

3号已经没有子树了，返回1号


1号还有子树4，访问4号

4号有子树7，访问7号

7号没子树了，返回4号


4号还有子树8，访问8号

8号没子树了，返回4号


4号也没子树了，返回1号


最后1也没子树了，递归就全部执行结束，完成对树的先根遍历。

由于树的特性，我们在探索这些新结点时，新找到的结点肯定是没有被访问过的结点

但是图就不一样了，我们通过某个顶点找到的与之相邻的顶点可能是已经被访问过的

所以，和广度优先一样，我们这里也设置一个visited数组来记录顶点是否被访问过

图的深度优先遍历算法和树的先根遍历是很类似的，都是先访问一个结点，然后用一个循环依次检查和这个顶点相邻的其他顶点，然后进行更深一层的访问。

现在我们来模拟一下图的深度优先遍历的实现过程：

现在要求从2号结点出发，对这个图进行深度优先遍历
那我们刚开始传参的v应该是2，接下来就是把visited里面的2设为true，

然后往下走就是for循环，for循环就是检查与2号结点相邻的其他结点

那和2相邻的是1和6两个结点，但是第一个和2相邻的应该是1，而1号此时没有被访问过，我们访问1号，将1号设为true。

接下来检查和1号顶点相邻的其他顶点，和1号相邻的有2和5，第一个相邻顶点应该是2，但是2已结被访问过，所以我们访问5，然后将visited中的5设为true

访问完5号之后，由于和5号相邻的只有1，而1已经被访问过，所以从5号返回上一层递归，也就是1号那层


而由于之前处理的5号顶点已经是1号顶点最后一个邻接点，所以1号顶点的for循环也执行结束，返回上一层递归，也就是2号

在前面已经处理了2号顶点的第一个邻接点也就是1号，而2号还有一个邻接点6号没有被访问过，那么现在进入2号的第二个邻接点6号


进入6号后，通过for循环找到和6号相邻的其他顶点237，还没有被访问过的有37，我们先访问3号

和3号顶点相邻的有674，还没有被访问的有47，我们先访问4


和4相邻的有378，还没有被访问的有78，先访问7


和7相邻的有3468，还没被访问的有8，访问8


而在8号这里，它的所有相邻结点都被访问过了，所以返回上一层递归到7号

而在7号这里，它的所有相邻结点都被访问过了，所以返回上一层递归到4号

剩下都是类似的，不再赘述

3.2.2代码实现

而上述代码也存在我们之前在广度优先遍历中提到的问题，如果是遇到非连通图，则无法遍历完所有结点

处理方法和上小节也是类似的，我们进行一次DFS之后，还可以再扫描一次visited数组，如果在visted数组中发现一个元素它的visited值为False，那么从这个结点出发再进行DFS

所有，最终改进后的，图的深度优先遍历代码如下

3.2.3复杂度分析

3.2.3.1空间复杂度

该算法的时间复杂度主要是来自于函数的递归调用

最坏情况：如下图，如果我们从1号顶点出发进行深度优先遍历，那么我们DFS函数递归调用的深度应该是和这个结点数相同的，所以最坏空间复杂度为O|V|

最好情况：如下图，我们从1号顶点出发，用深度优先遍历这个图，显然，这种情况下我们函数递归调用栈最多两层，所以空间复杂度为O（1）

如果题目没有特殊说明，对于时间复杂度答最坏情况的

3.2.3.2时间复杂度

而对于时间复杂度，分析方法和广度优先是类似的。我们在计算BFS/DFS的时间复杂度时，都可以把时间开销化简为——访问各个结点，探索各个边的两部分时间

无论是广度优先还是深度优先，如果是采用邻接矩阵存储，
那么访问|v|个顶点共需要O（|V|）这么多的时间
而要探索和各个顶点相连的边则需要遍历和当前顶点对应的一整行的顶点
所以时间复杂度为O（|V²|）

如果是采用邻接表存储
访问|v|个顶点需要O（|V|）的时间
而查找各个顶点的邻接点需要O（|E|）的
所以时间复杂度为O（|V|+|E|）

深度优先和广度优先这两种算法，它们的时间复杂度都是一样的，主要区别就是我们到底用什么样的存储结构来存储这个图

下面是我们的深度优先遍历序列的一些练习

如果我们用邻接矩阵存储，或者你用邻接表（邻接表中边结点出现顺序是递增的），那么从某个结点出发的深度优先遍历序列是唯一的

但是如果你用邻接表，却不规定边结点的出现顺序，那么遍历出的序列也是不同的
比如，现在有如下邻接表，

那么同样从2号出发，得到的遍历序列为26784315

3.2.4深度优先生成树

我们把上图中红色边保留，黑色边去掉，就是我们的生成树

而既然有生成树就有生成森林。如果一个图是非连通的，也就是说，我们需要多次DFS，每调用一次DFS就会生成一棵深度优先生成树

比如上图，有两个连通分量，所以需要调用两次DFS函数，也就是会对应生成两棵树

3.2.5图的遍历和图的连通性

对于一个无向图来说，无论是广度优先遍历还是深度优先遍历，调用BFS/DFS函数的次数应该是等于这个无向图的连通分量的数量

比如下面的图，有3个连通分量，所以，无论是进行广度优先遍历还是深度优先遍历，我们都需要调用3次对应的函数

而对于有向图，情况就稍微复杂一些

如果你一开始选的顶点到其他顶点都有路径，那么就只调用一次BFS/DFS，比如下图中的7号

但如果我们从2号顶点开始，我们只能找到1和5，所以肯定没法用1次就完成遍历的

还有一种特殊情况就是，如果给的图是强连通图，如下图，无论你从哪个顶点出发都只需要调用1次BFS/DFS

3.2.6小结

四、图的应用

4.1最小生成树

4.1.1最小生成树概念

我们前面已经学过什么是生成树：对于一个连通的无向图，如果能找到一个子图，该子图包含所有的顶点，同时各个顶点还能保持连通，但是边的数量又只有n-1条，那么这样的子图就是所谓的生成树。

一个连通图可能会有多个生成树，比如你通过广度优先遍历或者深度优先遍历所得到的生成树是不一样的。

而本小结，我们要学的生成树叫最小生成树（最小代价树）

假设现在有个p城市，该城市周围规划了学校、农场、矿场、电站、渔村
各个地方之间可能会有下图的要修路的地方（图中的边）
图中边的权值表示修路的成本

而为了节省开支，我们每必要把所有的路都修起来。
我们只需要确定一个修路方案，让上图中所有的地方连通（可以相互到达），并且成本花销尽可能低。

比如说我们现有如下两种方案：

一个带权连通图，它可能会有多个生成树，我们要从它所有的生成树中 找到各边权值之和最小的那棵（代价最小的那棵）

需要注意，最小生成树可能会有多个
比如下图，假设图中各个边权值都为1

另外，如果一个连通图，它本身就是一棵树。也就是说它里面各个顶点连通，但又不存在环。那么该图最小生成树就是它自己。
举例如下：

ps：只有连通图会有生成树。如果是非连通图，则是生成森林。
所以，最小生成树，我们研究的对象是带权的连通的无向图。

接下来，我们就将介绍如何求最小生成树的算法：Prim算法和Kruskal算法，这两个算法代码考察概率不高，我们主要是介绍算法思想，如何用手算模拟执行过程、

4.1.2Prim算法

首先，从图里挑选任意一个顶点，比如我们现在挑选P城作为开始顶点。

然后，我们每次把需要代价最小的新顶点纳入生成树。
而目前我们现在要构建的生成树只有p这个顶点，那么我们只能选和p城相连的最小权值的顶点


继续从剩下顶点中找代价最小的顶点，注意，此时的生成树有学校和p城，
你可以在与学校和p城相连的顶点中找代价最小的那个
现在最小的代价是4，你可以选矿场或者渔村，我这里挑选矿场


继续在剩下顶点中找代价最小的，发现代价最小的是矿场到渔村（代价为2）


继续在剩下顶点中找代价最小的，可能有同学要连p城到渔村，但是我们是生成树，是不能有环的，所以不能连
那么剩下的代价最小的，就是p城到农场（代价为5）


最后把电站连到生成树里面，我们挑选农场到电站（代价3）


这样就得到了一棵最小生成树，代价为15

4.1.3Kruskal算法

我们每次要挑选一条权值最小的边，然后让那个这条边的两个顶点相互连通，如果已经连通了，则不选。

现在，我们要从所有边中选出权值最小的，显然是学校和p城，而这两个顶点还没有连通，我们将它们连起来。


继续挑选权值最小的，矿场和渔村，两个顶点还没有连通，将它们连起来。


继续挑选权值最小的，农场和电站，两个顶点还没有连通，将它们连起来。


继续挑选权值最小的，p城和矿场（你挑p城和渔村也可以，代价都是4），两个顶点还没有连通，将它们连起来。

继续挑选权值最小的，农场和p城，两个顶点还没有连通，将它们连起来。

4.2最短路径问题——BFS算法

先来看问题背景：

现在有一个G港，它是一个港口，需要向各个城市运输货物。我们现在要求G港到其他城市可走的最短路径

这也是考研中比较第一种喜欢考察的最短路径问题：单源最短路径。
所谓单源就是指只有一个单独的源头，从该源头出发，到达其他任意顶点可走的最短路径是什么。
对于单源最短路径，我们会介绍BFS和Dijkstra算法

考研中第二种比较喜欢考的就是：各个城市也需要互相输送货物，那相互之间怎么走最短。
对于各个顶点的最短路径，我们会介绍Floy算法

好，我们下面将介绍如何用我们熟悉的BFS进行不带权的图的单源最短路径的求解

其实不带权的图，你也可以把它理解为每条路径的权值都相同，为了简单，我们就设这权值为1

那么我们现在要求从2出发到底其他所有顶点的路径。

从2出发，可以找到和它相邻的顶点1和6，和2直接相连的距离为1

接下来，再通过1和6找到下一层相邻的顶点537，第二波找到的顶点和源点2的距离就是2


继续通过当前层的顶点往下找，可以找到48，48和源点2最短距离为3


所以，对这个图进行一次广度优先遍历，我们就可以得到这个源点到其他所有顶点的最短路径

BFS代码如下：

bool visited[MAX_VERTEX_NUM];//访问标记数组

//广度优先遍历
void BFS(Graph G,int v){//从顶点V出发，广度优先遍历图G
   visit(v);//访问初始顶点v
   visited[v]=TRUE;//对v做已访问标记
   Enqueue(Q,v);//顶点v入队列Q
   while(!isEmpty(Q)){
       DeQueue(Q,v);//顶点v出队
       for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
           //检测v所有邻接点
           if(!visited[w]){//w为v的尚未访问的邻接顶点
              visit(w);//访问顶点w
              visited[w]=TRUE;//对w做已访问标记
              EnQueue(Q,w);//顶点w入队列
           }
       }
   }
}

在上述BFS算法中，我们用了visit函数抽象的表示出队某一个顶点的访问。
那我们要改造成刚才我们图示的情况，只需要对visit进行相应改造即可

改造代码如下：

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;i++){
        d[i]=∞//初始化路径长度
        path[i]=-1;//最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){//BFS算法主过程
        DeQueue(Q,u);
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
           if(!visited[w]){//w为u的尚未访问的邻接顶点
              d[w]=d[u]+1;//路径长度加1
              path[w]=u;//最短路径应从u到w
              visited[w]=TRUE;//设已访问标记
              EnQueue(Q,w);//顶点w入队
           }
        }
    }
}

我们在原有BFS算法中增加了d[ ]和path[ ]数组
d数组是用来记录各个顶点到原始顶点的最短路径长度问题
path数组则是用来记录每个顶点在最短路径上的直接前驱

下面我们要求2号顶点到其他顶点的最短路径，来走一遍代码流程：

刚开始，我们把d数组全部设为无穷，path数组全部设为-1

接下来把源点的d设为0，因为2号本来就是起始顶点，它到它自己肯定是0

下面两步和广度优先一样，标记2号顶点已经被访问过，然后把2号顶点放到队列中。

接下来执行while，如果队头非空，弹出队头元素，这里弹出2号
然后下面的for循环就是从2号出发，找到和它相邻的所有顶点

如果和它相邻的顶点中有顶点没有被访问过，那我们就需要更改它的最短路径长度。
新修改的路径长度=上一个过来的顶点到源点距离+1
然后还要修改一下path，记录上一个到达当前结点的是哪个结点

再往下就是和广度优先遍历一样了，我们把这些相邻顶点visited值设为TRUE，然后入队

后面过程请看下图，不再赘述：

上面就是通过广度优先遍历求无权图的单源最短路径问题
而我们之前也说过，通过广度优先遍历可以得到一个广度优先生成树，其实这个生成树的每个结点在第几层，直接反应了从起点2到该结点的最短距离。

也就是说，我们用广度优先构造出的生成树，它的深度（高度）肯定是最小的

4.3最短路径问题——Dijkstra算法

上小节，我们学习了用广度优先搜索来解决单元最短路径问题，这个算法只能用于不带权的图，但是遇到带权图就不行了。

举个例子：比如现在要求G港到R城最短距离，如果你用广度优先，那么应该是红线，就是G港直接连R城，路径长度为10

但实际上还有一条更短的，G港—>p城—>R城，路径长度只需要7

综上，广度优先搜索不适合解决带权图的单源最短路径问题

所以，带权图的单源最短路径问题，我们用Dijkstra算法来解决

在学习Dijkstra算法前，我们来回顾一个概念

我们假设要找到v0到其他顶点的最短路径，那么我们需要初始化下面三个数组final、dist、path

final数组：表示我们目前为止有没有找到从v0到达对应顶点的最短路径
刚开始的时候，我们把v0对应的final设为true，它到自己的最短路径就是0

dist数组：表示目前为止我们能够找到的最短的、最优的一条路径总长度为多少。
刚开始的时候，我们只知道v0到v1的边，所以目前来看从v0到v1最短的一条路径我们认为是10
刚开始，v0和v4也有一条相邻的边，所以我们把v4对应的值设为5
而刚开始，v2和v3并没有直接与v0相连的边，所以我们把这两个顶点对应值设为∞

path数组：和上小节的BFS算法的path数组一样，是记录每个顶点在最短路径上的直接前驱
比如v1这个顶点，我们刚开始能够确定的比较好的一条路径就是从v0过来的，我们把v1的path值设为0。表示目前能够找到的最好路径为v0到v1

在进行了上面一系列的初始化之后，接下来开始第一轮处理

首先要遍历所有这些结点相关的数组信息，要从中找到目前还没有确定最短路径，也就是final值为false，同时distance值最小的点

显然，在v1，v2，v3，v4中能找到distance最小的应该是v4

我们选定v4这个顶点，然后把它的final设为true，表示现在已经可以确定，对于v4这个顶点，它的最短路径长度为5。并且它的直接前驱为v0
ps：为什么能确定这里v4就已经是最短路径了呢？我们知道v0到其他顶点距离是要大于v4距离的，如果你这时不采取v0直接到v4的方案，也就是说你要绕一圈再回到v4，这时由于v0到其他顶点距离就已经大于直接到v4距离了，你再加上其他顶点到v4距离肯定是要更大的。
所以，由于当前v4的final是flase而它的distance是最小，就可以确定v4的最小路径了

接下来，还要检查和v4相连的顶点，也就是v1，v2，v3。看看对于这三个顶点，如果从v4过来，能否比之前找到的路径更短。

先来看v1：对于v1来说，我们之前确定的最短路径是从v0到v1，长度为10
但现在我们可以确定，从v0到v4有长度为5的路，从v4到v1有长度为3的路，总长8<10
新的路径显然比旧的路径更好，所以我们更新v1的distance为8，更新v1path为4

再来看v2：之前都没有v0到v2的路径，但如果现在从v0到v4有长度为5的路，从v4到v2有长度为9的路，总长14<∞
我们把v2的dist改为14，path改为4

最后是v3：如果从v4过去，总长为7<∞
我们把v3的dist改为7，path改为4

接下来开始第二轮处理
我们同样需要遍历这几个数组信息，发现此时还没有找到最短路径的这些顶点中，目前能够找到的最小的distance值应该是7，也就是v3这个顶点

选定v3，把它的final设为true，表示已经可以确定到达v3的最短路径长度为7，并且这条路是从v4顶点过来的

接下来要检查能够从v3过去的所有顶点，当然，你只需要检查final为false的顶点，已经是true的就不需要你后面进行修改了，还检查它干啥。

从v3可以到达v0和v2，但是由于目前v0的final为true，已经是最短路径了，不考虑v0

对于v2来说，前面找到的最好的路径长度为14，是从4号顶点过去的。
但是现在v3到v2长度为6，而v0到v3最短长度是7，v0—>v3—>v2长度是13<14
所以我们更新v2的dist为13，path为3

接下来开始第三轮处理

在剩下的还没有找到最短路径的结点中，找一个distance值最小的点，也就是v1

我们把v1的fina设为true

接下来检查和v1相连的所有顶点v2和v4，而v4前面已经确定最短路径了，所以我们只需要检查v2

对于v2，前面记录的最短路径是13，是从v3过来的。
那么如果从v1到v2，长度为1，而v0到v1最短长度是8，所以v0—>v1—>v2长度为9<13
所以我们更新v2distance为9，path为1

接下来开始第四轮处理
由于只剩下v2的final是flase了，所以我们把v2的final设为true，就不需要其他操作了

综上，算法到此结束。这就是迪杰斯特拉算法执行流程。
最终得到了下面的数组，来看看这些数组的信息有什么用

比如说我们现在要找到v0到v2的最短路径，通过查dist数组可以知道v0到v2最短路径为9

而通过pass数组，可以查到v0到v2最短路径的完整信息
v2前面是从v1过来的

而v1又是从v4过来

而v4又是从v0过来

这样就找到了v0到v2的最短路径信息

考研初试一般都是只考该算法的手算模拟过程，代码基本很少考。大家只需要学会手动模拟算法流程即可。下面是代码实现的简单流程，感兴趣可以自己查看

4.4最短路径问题——Floyd算法

Floyd算法可以用于求解各个顶点之间的最短路径，该算法是很典型的动态规划算法。

所谓动态规划算法这种求解的思想：就是把一个大问题的求解步骤划分为多个阶段，每个阶段之间有一个递进的关系。

比如该小结求解各个顶点之间的最短路径，我们会把该问题分为n个阶段来求解。

4.4.1算法流程

文字过于晦涩难懂，我们直接流程图跑一遍，大家就明白了。

现在我们有一个有向图，我们要求这几个顶点之间的最短路径，那么我们会设置下面两个初始的矩阵（二维数组）

矩阵A表示：当前，我们能找到各个顶点之间的最短路径长度为多少。
刚开始我们设定的初始状态，是指我们不允许各个顶点之间的路径存在其他中转顶点。
所以就目前来看，v0到v2的最短路径就是13，因为当前我们不允许以v1作为中转顶点。

矩阵path表示：我们当前能够找到的最短路径中，两个顶点之间的一个中转点。
刚开始所有顶点之间都不能有中转点，所以我们初始化时，把path全部设为-1

上面是初始阶段两矩阵的状态，下面我们看下一个阶段的最优解，也就是允许从V0中转看看最短路径能否进一步缩短
那我们要基于上一个阶段的A^(-1)和path^(-1)来进行A⁽⁰⁾和path⁽⁰⁾的求解

我们需要遍历上一个阶段的矩阵A，对于矩阵A中的每个元素，我们都要进行下面的检查

比如说，对于上一个阶段的A，我们检查它的A₂₁，也就是v2到v1，前面我们不允许有v0作为中转点它们距离为∞，现在允许v0作为中转的。

也就是说我们现在可以先从v2到v0，再从v0到v1，这个距离为5+6=11<∞

新找到的路径是比之前的路径更好的，所以我们把A₂₁改成11，
而此时v2到v1是以0号作为中转点，所以我们把path₂₁改成0

当然，对于A矩阵中的所有元素，我们都需要进行上面的判断，然后决定是否要更新A和path

而经过我们的一系列判断之后，我们发现从初始的-1阶段到0号阶段，我们需要更新的也就是上面说的A₂₁和path₂₁

那么开始下一阶段的判断，基于0号阶段来推出1号阶段的A和path，1号阶段允许以v0和v1作为中转点

所有的元素扫描完之后，发现只有A₀₂需要修改

A₀₂表示从v0到v2的最短路径，之前A₀₂=13表示上一轮v0到v2的找到的最短路径为13。

但是当前我们可以额外用v1作为中转结点，可以v0到v1，v1再到v2
我们发现新的路径v0—>v1—>v2路径长度为6+4=10<13

所以我们更新A₀₂=10，path₀₂=1

再下一个阶段，2号阶段要以1号阶段为基础，2号阶段允许以v2为中转点

和前面一样，依次扫描A中所有元素，判断是否符合条件。
我们扫描完后，发现只有一个地方满足，就是A₁₀这个位置

从v1到v0，以前我们能找到的最短路径长度为10，然后发现path₁₀=-1，也就是说以前的v1到v0是不需要中转点的，直接过去的路径长度为10

现在我们可以以v2作为中转点，那么可以v1—>v2—>v0，新的路径长度为4+5=9<10

所以我们更新A₁₀=9，path₁₀=2

综上，我们经过n轮的递推，每轮我们都会多增加一个顶点作为中转结点进行考虑。
ps：n为结点个数

经过n轮递推之后，可以得到最终的A和path
而基于最终的A和path，我们就可以得到任意两个顶点的最短路径长度和路径信息。

比如说，我们要看v1到v2的最短路径，发现A₁₂=4，path₁₂=-1
也就是说v1到v2最短路径是4，v1到v2不需要中转结点，即v1—>v2

再比如，我们要看v0到v2的最短路径，发现A₀₂=10，path₀₂=1
也就是说v0到v2最短路径长度为10，要经过v1作为中转结点，即v0—>v1—>v2

4.4.2代码实现

刚才我们分析的Floyd算法流程好像比较复杂，但其实用代码实现很简单

//准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){//考虑以Vk作为中转点
  for(int i=0;i<n;i++){//遍历整个矩阵，i为行号，j为列号
    for(int j=0;j<n;j++){
        if(A[i][j]>A[i][k]+A[k][j]){//以Vk为中转点的路径更短
         A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
         path[i][j]=k;//更新中转点
      }
    }
  }
}

总共n个顶点，每层循环n次，共3层循环。所以一共要n³次循环

所以，基本考试不会考4次及以上的，你想想，n=4就已经要遍历64次了，再往上的话，遍历次数太多，考试出这种题不现实。

所以大家把n=3的情况弄透就行。

4.5有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，
简称DAG图（Directed Acyclic Graph）

举个例子，下面右图中，v0-v4-v3-v0，这是存在环路的，所以不是有向无环图

该小节中，我们要学习如何用有向无环图来描述表达式

我们在前面的章节说过，我们的算术表达式都可以用树来进行表示

细心观察可以看到，这棵树中有一些重复的部分

从计算的角度看，红色子树和绿色子树计算结果是一样的，我们完全可以省略其中一个，保留另一个。如下图：

我们可以看到，表达式中三角标注的“+”和“*”其实右操作数都是(c+d)*e，所以我们把这两个的指针都指向(c+d)*e这个公共部分

ps：省略掉一个公共部分后，就是形成了一个有向无环图

按照刚才的思路，继续往后看，我们发现还是有重复的地方可以合并的

继续往后，发现还有两个b也是可以合并的

然后我们来看一下考研真题

我们按照前面的思路把重复的去掉，就变成了下面这样，那就是选A了

当然，可能有同学会说：“我有时候找不全怎么办？”
下面是一些方法，大家根据这个方法就基本可以保证找全了。

我们看刚才举的两个例子：

我们可以发现，我们最终的有向无环图里面顶点中是不可能出现重复的操作数的
比如上面的左图，操作数x和y各1个
比如上面的右图，操作数abcde各1个

step1，我们要把上面式子中出现的操作数不重复的排成一排，比如这里的abcde

step2，标记好各个运算符生效的次序
当然了，这些运算符生效顺序前后有一点不同也没关系
我们把这些运算符标上数字，只是为了一会我们在构建有向无环图时，不要遗漏任何一个运算符。

step3，我们根据标出的运算符的生效顺序来依次的把这些运算符对应的结点加到图中，注意“分层”
分层是啥意思？先往下看就知道了

第一个生效的运算符我们根据前面标记的数字知道，是一个“+”，它的左边是a，右边是b，所以该运算符对应的结点如下

第二个生效的是“+”，左边是c，右边是d

第三个生效的是“ * ”，左边是b，右边是（c+d），这里需要注意，要把*放到上一层，也就是我们前面说的分层

为什么是分层？就是说，当前这个运算符，它是基于前面运算符的运算结果的，所以它要在前面运算符上一层

第四个生效的是“*”，它利用了第1个加号的运算结果，和第3个乘号的运算结果，这里也需要分层

第五个生效的是“+”，左边是c右边是d，这个没有利用前面的运算符的结果，就不用分层了。

第六个生效的是*，左边是（c+d），右边是e，它利用了第五个的+，所以要分层

第七个生效的加法，需要在第四个 * 和第六个 * 的运算结果，所以要分层

第八个是+，左边是c，右边是d，不用基于其他运算符结果，不用分层

第九个*，需要用到第八个运算符结果，和e进行相乘，这里分层

第10个*，需要用到第七个加的结果，我们需要分层

这样就初步构建完成一个有向无环图，下面我们来观察哪些东西需要合并

由于刚开始，对于各个操作数，我们只保留了一个顶点，所以对于这些操作数顶点我们不需要合并。

然后就是一层一层的自底向上的检查同一层的操作符是否可以合并

比如现在观察操作符最下面一层，这层全是加法。
最左边的加法是a+b，后面三个加法都是c+d，所以合并一下

比如现在观察操作符倒数第二层
可以发现，这层有三个*，其中两个 *的操作数都是（c+d）和e
我们将这两个进行合并

再往上三层都是只有一个运算符，所以就不用考虑合并了，到此为止我们就得到了一个最简的、用有向无环图表示的算术表达式。

4.6拓扑排序

4.6.1AOV网

前面的章节我们已经学习了什么是有向无环图，这里我们新增一个概念：AOV网

上面的图表示你怎么做番茄炒蛋，最后把它吃掉的流程。

首先，上图是一个有向无环图，这些顶点表示的是一个个活动。

这些有向边则表示某个活动必须先于另一个活动进行。
比如说，我们洗番茄之前要先买菜，你得先有番茄才能洗番茄。
再比如，你切番茄前需要番茄已经洗好，并且你已经准备了厨具。

所谓的AOV网，每个活动是用一个个顶点来描述的

并且，AOV网一定是一个有向无环图，如果图里面存在环路，那就不是一个AOV网
比如现在新增一条切番茄到洗番茄的边，那么洗番茄和切番茄将形成回路
那么图示的意思就是，你切番茄前要洗番茄，这没有问题。
但是又要求你洗番茄之前把番茄切好？？这根本不是正常人的逻辑啊

所以，AOV网里面不允许存在环路

4.6.2拓扑排序概念

下面大家可以看一下拓扑排序的概念，这个看不懂也没事，我们后面老规矩流程走一遍就懂了。

所谓的拓扑排序，如果放在AOV网里面其实就是要求我们找出做事的先后顺序

4.6.3拓扑排序流程

那么做番茄炒蛋，我们可以从准备厨具/买菜开始做起

我们这里选择先准备厨具

工具有了，我们还需要准备材料，也就是下件事必须是买菜

现在买完菜，鸡蛋有了，番茄也有了。你可以选择先打鸡蛋或者先洗番茄。
我们这里选先洗番茄


再往后，你可以选择打鸡蛋或者切番茄，我们这里选择把番茄切好

现在番茄都处理完了，就打鸡蛋吧，因为没鸡蛋你怎么番茄炒蛋？

鸡蛋和番茄都处理好了，现在开炒


炒好了，开吃！


由上面的顺序，你就可以完成番茄炒蛋的活动
结合我们刚才拓扑排序的例子，我们知道，每个AOV网可能有一个或者多个拓扑排序序列，
比如你一开始可以选择先买菜，而不是先准备厨具

刚才我们对AOV网进行拓扑排序的过程，就可以总结成下面这样的步骤

对于第3点：如果按照1、2点操作到最后发现当前网中还有不存在前驱的顶点，就说明有回路

举个例子，我们加上一条切番茄到洗番茄的边，这样就形成了一条回路。

我们现选择准备厨具

接下来是买菜

接下来我们只能选择打鸡蛋，因为是选择入度为0的结点。
原先洗番茄也可以选，但是现在加了切番茄到洗番茄的边，入度就变为1，不能选了。

然后我们发现，图里面居然一个都选不了了，所有结点入度都大于0

所以，如果原图存在回路的话，那么这样的图是一定不存在拓扑排序的。

4.6.4代码实现

其实就是把我们刚才说的那两个步骤一直重复。

下面是关于代码一些解释

首先，我们这个代码是基于邻接表写的，大家看上面的图示也能看出来

然后函数中的indegree是表示每个顶点当前的入度的数组
print数组则是记录得到的拓扑排序序列
还需要定义一个栈来保存当前度为0的顶点。
这个你如果不想用栈，你用队列、数组什么的都可以

下面是代码的执行流程：

我们已经定义了空栈，

初始化indegree数组：
0号顶点入度为0，
1号顶点入度为1，
2号顶点入度为0
3号顶点入度为2,
4号顶点入度为2

print数组刚开始全部初始化为-1

接下来的第一个循环，会检查当前入度为0的所有顶点，可以发现当前入度为0的顶点分别是0号顶点和2号顶点，把0号和2号顶点放入栈中。

然后代码往下走，定义了一个count的变量，刚开始是0

我们之前说过，对一个图进行拓扑排序的过程，就是删除当前入度为0的顶点。

目前来看，度为0的0号顶点和2号顶点已经放入栈中了，那么我们可以通过栈中保留的信息来确定我们拓扑排序的第一个结点

当前弹出栈顶的是2号结点，所以我们把count所指位置记为2
表示在这个拓扑排序的序列中，第一个顶点排序编号为2

然后count++

再往下的for循环，是要把当前弹出的结点，也就是2号结点，
把所有和2号结点相连的顶点入度都减一。
和2号相连的有3号和4号这两个结点，这两个结点的入度都进行减减操作，如下图

这个操作就相当于，我们逻辑上把2号顶点和与2号顶点相连的边删除了

ps：只是逻辑上删除了，图的邻接表的信息没改

到这里完成了第一轮while循环，此时栈依然是非空的
我们还是要弹出栈里面保存的元素，因为栈中元素表示该元素对应顶点的入度是0，我们是可以把它删除的

接下来弹出的是0号顶点，我们把0号顶点的数字记录在print数组里面，

接下来，在for循环里面我们会处理所有和0号顶点相连的顶点。也就是1号顶点，把1号顶点入度值减减。就相当于在逻辑上把0号顶点还有与之相连的边删除了

这导致1号结点此时已经没有前驱结点了，接下来就删除1号结点，把1号结点放到栈里面。

下一步要删除1号结点，先把它记录到print里面

然后就是把1号结点相连的结点入度减减，也就是三号结点入度减减

这导致3号结点的入度变成0，那么我们下面就是删除3号顶点，先把3号放到栈里面

再往后，要删除3号结点，先把3号结点记录在print里面

然后把与3号结点相连的4号结点入度进行一个减一的操作

这会导致4号结点入度为0，把4号结点压入栈中。

最后4号结点出栈，记录到print里面，count++

此时count==5，也就是等于结点的数量，那就表示我们拓扑排序成功了。
如果最后我们算法停止时，count值小于顶点个数，那就表示这个图里面存在回路。

该算法中我们每个顶点都会被处理一次，每条边都要被遍历一次，所以时间复杂度为O（|V|+|E|）。
但是如果我们用邻接矩阵来存储，我们要遍历完所有的边，其实就是要扫描整个邻接矩阵。

4.7关键路径

4.7.1AOE网

先来认识一个概念AOE网

上小节我们学了一个类似的概念AOV网，AOV网的V是指vertes也就是顶点

这里的AOE网，E是指Edge，也就是用边来表示一个个活动，用顶点表示一个个事件。

举个例子：
现在要做番茄炒蛋这个菜，假设我们已经有原材料了

首先我们需要花2分钟的世界来打鸡蛋，
花1分钟时间来洗番茄，
洗完番茄之后还需要花3分钟切番茄，
切完番茄并且打完鸡蛋后，我们需要花2分钟炒菜

像“打鸡蛋”这些表示的是一个个活动，这是用边表示的，边上的权值表示完成这个活动所需时间

各个顶点表示的是一个个的事件

可以这么理解，这些活动是要持续一段时间的，而事件则是一瞬间完成的

对于AOE网有如下性质：

ps：关于第二点，有些活动是可以并行进行的。比如说要完成番茄炒蛋这一工程的人有两个，一个人可以先打鸡蛋，另一个人可以先洗番茄。
但是，你不可能一边洗番茄一边炒菜，炒菜必定是你番茄已经洗好切好，并且鸡蛋打好的情况下发生的。你现在番茄还没洗好就不可能炒菜了。

4.7.2开始顶点&结束顶点

下面再看两个相关概念：

4.7.3关键路径

从源点（开始顶点）到汇点（结束顶点），我们可以在AOE网中找到多条路径
比如v1——v3——v4

再比如v1——v2——v3——v4

所有这些从源点到汇点的路径中，具有最大长度的路径就是关键路径，
而关键路径上的活动，称为关键活动。

显然，图中v1——v2——v3——v4是路径总长度最长的，所以v1——v2——v3——v4就是关键路径。

这条关键路径的长度，其实就是整个工程能够完成的最短时间。
比如上图中关键路径总长是6，也就是说我们要做完番茄炒蛋至少需要6mins

4.7.4最早开始时间、最晚开始时间

实战演练：

4.7.5关键活动、关键路径的特性

4.7.6小结

到了这里，关于数据结构：第六章 图的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！