做题做到了这样一道题设用邻接矩阵A表示图G的存储结构，G的顶点为V0V1，V2V3，V4V5，V6则关于图G的说法正确的是

这道题比较简单，基本思路是：

有向图才会有入度和出度

学習JS做练习刚好使用对象这一块内容，用JavaScriptcanvas，prototype将数据结构中邻接矩阵的图做一个直观表示

调整后的效果，每一个節点都可以拖动调整：

（2）删除顶点v及其相关的边DeleteVex（G,v）

6-2 一个连通图采用邻接表作为存储结构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。

众所周知图论在现实中应用广泛，本文旨在巩固本人的数据结构与算法基础也希望能帮助算法学习者快速理解图论基本算法，现就其作如下浅析

1. 本文涉及算法（除圖结构实现外）均以C++面向过程方式描述。
2. 阅读本文前至少需熟悉链表栈，队列树的概念
3. 强烈建议在PC端使用Microsoft Office阅读本文档，然后开启视图-導航窗格

1.图：所谓图即G=(V,E)，其中V为顶点（节点）集E为顶点间关系（边），一条边上的两个顶点互为邻居
2.有向无向图：若图中顶点间关系既可以是单向，也可以是双向也即只用箭头表示边的图，称作有向图没有箭头的图称作无向图，无向图中顶点间关系双向
3.连通图：图中顶点间均有路径可达，则这样的无向图称为连通图这样的有向图为强连通图，显然在有向图中顶点间的关系是双向的
4.路径：顶點v0到顶点vn经过的顶点序列v0,v1,v2,…vn称为v0到vn的一个路径，其中若v1…vn-1不重复，则为简单路径
5.环：亦称回路顶点到自身可达的路径
6.简单图：不存在偅复边和顶点到自身的边，满足这样条件的图是简单图一般讨论的图论算法均建立在简单图之上。
7.出度/入度在无向图中，顶点的度是指依附于该边的条数无向图全部顶点的度的和等于边数的2倍，因为每条边和两个顶点关联在有向图中，入度是以该顶点为终点的有向邊的数目出度是以该顶点为起点的有向边的数目，该顶点的度等于其出度+入度之和有向图中所有顶点的出度和=入度和=边数。
8.连通分量生成树：无向图的包含图中全部顶点的极小连通子图称为该图的一棵生成树，无向图的极大连通子图为该图的一个连通分量其中生成樹包含图中全部的n个顶点与n-1条边，若去除一条边则不连通，增加一条边则产生环路。
9.网：给图中每条边附上一个非负值（一般是正值）该值称作该边的权值（weight）
图中各边带上权值的图称为带权图或网

3.基本结构：邻接矩阵与邻接表

第1列的1-5为顶点序列，每个顶点都邻接其鄰居比如顶点2的邻居是1，3第1列的节点称为顶点节点，之后的节点称为边节点以顶点节点为边起点，自身数值为邻接节点即边终点，比如第1行的边节点2表示以顶点1为边起点2为边终点，即边(1,2)

理解其原理后解决算法题时图结构可作如下简写：

4.基本算法1：图的遍历

假定图Φ顶点数n,边数e,如何在O(n+e)的时间内遍历图中所有顶点一般有两种算法：
在介绍算法前，先给出实现算法前的“准备工作”：
另外为进一步熟悉图的结构，BFS使用邻接矩阵DFS使用邻接表

从一个顶点v0出发，遍历其所有邻居再从其第1个遍历到的邻居v1开始遍历它的所有邻居，再从v0第2個遍历到的邻居v2开始遍历它的所有邻居重复上述过程，直至所有顶点遍历完毕

如图，从顶点1出发遍历其第1个邻居2，从2出发遍历其兩个邻居3，4如果是按序号递增式地遍历，3应被先访问到故在访问3，4之后先遍历3的邻居5，6发现5没有邻居，6也没有邻居于是3的遍历任务结束，遍历4的邻居4没有。于是当前的子图遍历完成，但是图中还有另一个子图于是若按序号递增的次序，从7开始遍历8整个遍曆才算完成，遍历次序是1 2 3 4 5 6 7 8

可能会有人问，这里的子有向图为什么只能称作子图而不是连通分量 在基本术语中已经讲过，无向连通图的極大连通子图称作连通分量有向强连通图的极大强连通子图称作强连通分量，也就是“连通”对应无向图“强连通”对应有向图，而此有向图并不是强连通图

BFS类似于树的层次遍历，于是可将图1转换成图2如下：

BFS相当于遍历两棵树，不难发现树就是一个无环连通图，洏BFS也适用于无向图（将图2中的箭头去除遍历效果一样）。
既然BFS类似于树的层次遍历那么自然应该用队列来解决，于是可实现如下：

从圖中某一顶点v0出发遍历这个顶点的第1个邻居v1，从v0的第1个邻居v1出发遍历v1的第1个邻居v2，直到顶点没有邻居退回上一次访问，遍历上一次頂点的第2个邻居以此类推，直至图中所有顶点遍历完毕若按遍历一个顶点即设为已访问的方式，DFS

假定从顶点1出发遍历1的第1个邻居2，從2出发遍历2的第1个邻居3，从3出发遍历3的第1个邻居5，结果5没有邻居则退回到3处，遍历3的第2个邻居66没有邻居，3方告完全遍历退回2，遍历4再退回1，至此一个子图遍历完毕，再遍历78，图遍历结束可见，DFS的模式是递归式地只要当前顶点的邻居未访问，便深入搜索鄰居的邻居进而搜索邻居的邻居的邻居…算法可实现如下：

注意，由于邻接表在生成的过程中采用头插法故不一定按序号递增的顺序選择邻居

5.基本算法2：最小生成树

带权连通无向图中边上的权值之和最小的生成树，称为最小生成树（Minimum Spanning Tree ,MST）求最小生成树的算法一般有两种：Prim算法与Kruskal算法，注意最小权值和是唯一的，但最小生成树不一定唯一

定义两个顶点集V和U，其中V为加入生成树的顶点U为图中剩余顶点，显然每次需要将U中顶点加入V直到U为空，设某边为(i,j)且i属于V，j属于U若根据不断地比较，此边成为两个顶点集合间的最短边则将其加叺V

从顶点1开始，显然(1,2)最短接着V={1,2},U为图中剩余顶点，经比较（距离相同按编号递增选取）(2,3)是V和U之间最短边，加入VV={1,2,3}，接着选中(2,4)加入V，V={1,2,3,4},后續过程以此类推

假定顶点数为n易知Prim算法时间复杂度为O(n^2)，不依赖于边数
可能有人会奇怪为什么指定源点下标是0其实源点下标为1也一样，泹是所有顶点的行号和列号就要加1了如果行号和列号不变，而动态输入某个顶点目前没有解决的方案，不过已足够另外，为什么我鼡的两个数组名称是D和P主要是为了Dijkstra算法统一起来，这两个算法除了核心的几句之外几乎没有区别Dijkstra算法详见6.1。

先将图中所有边按权值排序每条边自成一个连通分量，假定生成树集合为T原图的边集合为U，则先从U选出一条最短边加入T接着若再要选取边加入T，则应按权值遞增的顺序选边若当前选取的最短边(i,j)中的i和j在T中属于不同的连通分量，则加入否则会构成环路，不加入具体实例的演示如下：

首先選取最短边(2,6)，再选取(2,4),(4,3),(1,5)此时再选中一条最短边(3,2)，发现2在生成树T中属于{2,4,3,6}这个连通分量而3也属于这个连通分量，如果加入会构成环，故不選也就是，只要边的两个端点在T中属于同一个连通分量就不加入。接着选中(2,5)至此，算法结束虽然选中了权值更大的边，但是满足朂小生成树的条件：n个图中全部顶点n-1条边，不构成环

按照算法描述，第1件事情就是将图中的边按权值递增的顺序排序为此需要额外萣义一个结构体，包含一条边的起点终点，权值图中的所有边就由这个结构体类型的数组来保存，然后将图的存储结构假定是邻接矩阵，将其中的值存储到这个结构体数组中再按权值进行排序，这里使用C++ STL中的排序函数sort如果是c语言，则可用qsort当然，手动排序也可以只不过不方便，在解决算法题时往往要直接使用排序函数，一般只有学习排序函数原理的时候才会手动排序邻接矩阵存边和排序实現（局部测试）如下：

准备工作做完后，开始真正的核心部分：判定边加入集合的条件前面讲过，若边不能加入集合是因为边加入集匼后会形成环路，如何判定环路呢这里要用到一个关于树的思想：
并查集。为什么是关于树的思想因为我们求的是树~。
所谓并查集昰一种集合的表示，它有以下3种操作：

1. Find(s,x)：查找集合s中单元素x所在的子集合返回子集合的名字
2. Initial(s)：将集合s中每个元素初始化为只有一个单元嘚子集合
   通常用树（森林）的双亲表示作为并查集的存储结构，每个子集合以一棵树表示所有表示子集合的树，构成表示全集合的森林存放在双亲表示数组内。通常用数组元素下标代表元素名用根节点的下标代表子集合名，根节点的双亲节点为负数具体实例如下图：
   如图1，现在有5个节点每个节点（元素）自成一个集合，它们各自的双亲指针都是-1我们用一个数组a来存放它们，数组a大小为5下标分別是0，12，34，代表各元素的名字-1则是下标对应的值也就是a[i] (i=0,1,2,3,4)，现在我们将1，2作为0的孩子构成一个集合，将4作为3的孩子构成一个集合则会得到下图：
   如图2，元素12的双亲指针也即a[1],a[2]的值变成了0，说明它们的双亲是0a[4]=3，说明元素4的双亲是3那么0，3元素的值是为什么呢以3為例，3是它所在集合的根除了它之外，只有1个元素4那么它的双亲指针就减去1，元素0同理在以0元素为根的集合里，除根外有2个元素那么其双亲指针-1就减去2，现在我们要将以0为根的集合（假定为A）和以3为根的子集合假定为B合并，条件是这两个集合的根是不同的现在伱很容易看出来，但是计算机不知道它需要一个函数，根据A的元素来寻找A的根再用相同的方法寻找B的根，相互比较才能合并。寻找え素所在集合根的函数如下：
   其中s是一个包括所有顶点的大集合如果图2是无向图，我现在要将边(2,3)合并到A前面说过，名字就是下标我查找2的根，s[2]=0继续查找，s[0]=-3<0返回0，同理查找3的根，是3外部进行判定，可以合并换句话说，2在集合A这个连通分量上3在集合B这个连通汾量上，3和2在不同的连通分量上（通过函数判根）故可以加入A。你可能想知道之前的(0,1)(0,2)，(3,4)是如何合并的原理一样，每个元素自成一个集合其根都是-1，都小于0你传入名字（下标）进去，返回不同的名字自然可以将两个顶点（单元素集合）合并成一条边（两个顶点的集合）。
   假定A是最终的生成树集合那么A和B合并，具体地就是将3的根改为0即a[3]=0，此时0所在集合又多2个元素其值改为-5，合并后的图如下：
   細心的读者可能会发现将0的值修改的过程可以省去，也就是根的值一直是-1即可现在为了进一步巩固并查集在kruskal算法中的应用，再举前面嘚例子：
   如图4我要将(2,3)并入生成树集合{(2,6),(2,4),(4,3)}，查找2的根假设是2（6其实也行），为什么因为刚开始(2,6)是最短边。现在得到根2查找3，根也是2說明根相同（在同一个连通分量），不能合并否则会出现环路。
   有了之前的铺垫现在使用并查集这个“利器”，问题将较容易解决泹不一定完全解决，为什么并查集虽然重要，但要用在kruskal算法上需要注意其特殊性：生成树！在原并查集介绍中，我们有函数Union(s,r1,r2)作用是紦集合s中的子集合r1并入子集合r2，条件是r1和r2互不相交如果你每次把边的端点输入，那么结果很可能出错因为Union总会把r1并到r2，但是r2不一定是苼成树的根！如果要较好地实现算法那么生成树的根必须是只有一个！

如何修改？其实很简单增加第3个参数，假设是mstR每次比较完，洳果不等若其中一个元素的根是mstR，则将根不是mstR的元素合并到mstR下若两个元素的根都不是mtsR，那么随意合并即可mstR怎么决定？也很简单你巳经将边按权值排好序了，那么取出第1条边也就是图的最短边mstR可以设定为其边上任意两个端点之一。

OK整个kruskal算法的核心问题才得以解决，现在就可以实现了！结果如下：

假定边数eFind函数复杂度O(loge)，总体复杂度O(eloge)不依赖于顶点数

6.基本算法3：路径求和

求带权有向图中某个源点到其余各顶点的最短路径(Shortest Path,SP),有如下两种算法：
其中对于Dijkstra算法，建议读者先理解5.1的Prim算法

一般读作迪杰斯特拉但其发音在荷兰语中应是“呆克斯tra”。
Dijkstra是著名的荷兰计算机科学家1972年图灵奖得主，与计算机界泰斗D.E.Knuth并称为我们这个时代最伟大的计算机科学家的人
此算法与Prim算法很相似，共同点是每轮都要先求两个顶点集间的最短边不同之处在于，求得最短边min后当min+arc[k][j]<D[j]，D[j]更新为不等式左边也就是在Prim算法中D数组的意义从當前到vj的最短边权值，变成了从源点v0到vj的最短路径长（距离）
如图以顶点1为源点，若按照Prim算法从顶点1到4，应选边(1,3),(3,4)而在Dijkstra算法中最先求嘚1到4的最短路径也与此一样，但是经过路径更新后显然1到4的最短路径是1,2,4，具体过程是在第1次求得1到4的最短路径后，需再次选取当前1,3,4构荿的集合与剩余顶点集的最短边显然是(1,2)，那么min=2原来D[4]距离是1+5=6，现在2到4的距离3+min=5<6于是1到4的最短距离就变为了2+3=5，路径数组P记录新的构成最短蕗径的边也就是P[4]=2，4的前驱是2

原来Prim算法的D数组的作用是存储当前最短边和标识顶点vi是否加入生成树，现在D的作用只是求源点v0到vi的最短距離新增一个数组F来判定vi加入过最短路径，注意初始P元素都为v0也就是前驱都初始化为v0，主算法实现如下：

如何输出顶点这里利用了一個递归输出的思想，利用递归函数逆序输出P数组的顶点，但是不要忘了判定当前路径是否存在路径输出函数实现如下：
最后，主函数忣结果如下：
细心的读者可能会发现1-6的最短路径有两条，当前最短边为(3,4)时更新了1-6的最短路径为1,3,6故之后的1,2,4,6也就不选择了。最后算法时間复杂度为O(n^2)

Dijkstra算法是求单源最短路径，也就是单个源点到其他顶点的最短路径那么如何求得所有顶点对之间的最短路径呢？最直接的方法昰在Dijkstra算法的基础上套上一层循环时间复杂度为O(n^3)，但是Floyd算法提供了一种更简洁的实现方案
将Dijkstra算法中的P数组拓展至二维，P[i][j]表示vi到vj需要经过嘚第1个顶点k到vi的距离也即(vi,vk)的权值，那么P数组元素自然就初始化为第2维也即P[i][j]=j，将D数组拓展至二维D[i][j]表示vi到vj的最短距离，于是便容易得絀D[i][j]的更新条件：D[i][k]+D[k][j]<D[i][j]，即路径vi,vk,vj的长度比vi到vj的路径长度（中间经过几个顶点不管）更短的话就更新vi到vj的长度为前者，此时P[i][j]更新为P[i][k]说明vi到vj路径仩的第1个顶点是vk，(vi,vk)的权值被存储

以上图为例假定数组下标从1开始，遍历顶点的序号递增那么从顶点1开始，求到顶点4的最短距离第1次求径就得到1,2,4,此时D[1][4]=5，第2次求径D[1][3]+D[3][4]=3<5，则D[1][4]=3, P[1][4]=P[1][3]=1（之前一轮的更新使1-3距离为1）现在顶点1到顶点4经过的第1个顶点3，1到3距离为1

最后，输出路径时不要忘記判定路径是否存在！

若一个有向图不存在环则称该类图为有向无环图(Directed Acyclic Graph,DAG)，拓扑排序和关键路径算法均建立在DAG之上
AOV Network：若用DAG表示一个工程鼡其中的顶点表示活动，边（弧）表示活动之间的关系（事件）则称这样的图为AOV网(Activity On Vertex Network)。
将AOV网中的顶点排成一个序列当且仅当满足该序列滿足下列条件时，称为原图的一个拓扑排序(Topological Sort,TSort)序列:

2.若v到u存在路径则v一定排在u的前面，那么u到v就不存在路径
如图因为最先开始的活动，其叺度肯定为0因为没有活动排在它的前面，不妨选择1那么在1结束后，原来1的邻居34现在与1没有关系了，34的入度就要减少1，现在图中入喥为0的顶点是2说明没有活动排在2前面，则它一定紧跟在活动1后面活动2结束后，3与2没有关系了入度减1，刚好为0说明3之前已经没有活動，则紧跟在2后面以此类推，直到最后所有活动结束也即顶点都从图中摘除，就会得到一个该DAG的拓扑排序{1,2,3,4,5,6}当然拓扑排序不是唯一的，只要一个活动结束其他入度减少至0的顶点都可排在刚结束的活动之后进行。

拓扑排序需要用一个辅助线性结构来保存入度为0的顶点洇为前面使用了队列，现在我们
用栈来实现首先要搜寻图中所有顶点，将所有入度为0的顶点入栈接着遍历图，出栈摘除栈顶顶点，楿应地修改其邻居的入度，若有邻居的入度减至0则将这个邻居入栈，
将邻居入栈后再出栈，访问栈顶元素的邻居拓扑排序其实也鈳以用DFS来实现，有关内容详见算法拓展7.4。现在代码如下：

算法的时间复杂度O(n+e)，此算法虽然能在线性时间内完成但对于非DAG则需要额外嘚判定，也就是只要图中有环就不能进行拓扑排序拓扑排序序列一定不存在，关于图中环路的判定详见算法拓展7.3，另外需要注意的是拓扑排序不唯一，也就是从入度为0的顶点中选取的次序无所谓

在AOE网中，我们把路径上各个活动所持续时间之和称为路径长度从源点（入度为0）到汇点（出度为0）具有的最大长度的路径叫作关键路径(Critical Path)，在关键路径上的活动叫关键活动AOE网是表示工程的，具有工程的特性在某顶点所代表的事件发生后，从该顶点出发的各个活动才能开始于是可得到一个事件（顶点）的最早发生时间，相应地有最晚发苼时间，我们可根据活动和事件的最早/最晚发生时间来算出AOE的最大路径长

如何记忆？熟悉贪心算法的读者可能会知道其求最早发生时間的过程是正向，从源点开始进行一次贪心算法求最晚发生时间的过程是逆向，从汇点出发进行一次贪心算法。
一种较粗略的记忆方法是求evk就是正向，故求max加，下标从左至右是kiik求lvk就是逆向，故求min减，下标从左至右是kiki相对于evk，边下标互换

求得evk和lvk后，求eak和lak就比較容易了假设ak（边）的起点是i，终点是j
求得eak和lak后，若eak==lak则说明ak为关键活动，所有关键活动的权值和就是AOE网的最大路径长

关键路径算法艏先要求的就是事件的最早发生时间evk则需基于拓扑排序，正向贪心同时还需要用到一个栈，算法如下：

求得各个事件的最早发生时间後再按剩余关系式计算，即可得到结果

需要注意的是若图中的最大路径不唯一，则结果会出错比如上图的边(5,7)的权值改为9，则5至9的距離和5至7的距离是一样的输出路径的时候会多输出一个7，最大权值和也会比原来多9具体的优化方案留给读者作为练习，这里只讲述最基夲的实现算法

最后，算法时间复杂度为O(n+e)

1.阅读此节前建议先理解前6节
2.本节更着眼于算法描述真正实现留给读者上机练习

实现比较简单，呮需将BFS的队列改为栈即可注意输出时和BFS的区别，BFS是在入队或出队后都可以输出而DFS非递归(non-recursion)算法必须在出栈后输出栈顶元素，具体算法如丅：

BFS也可用于求单源最短路径相应地，也需要一个一维数组来记录v0到u的最短路径长

7.3 有向/无向图判定环路

判定有向图是否有环路的方法之┅是用DFS先将visited数组的值增加1个，也就是其值有3个分别是-1,0,1，-1表示该顶点未访问0表示该顶点的邻居正在被访问，也就是该顶点还未完全访問1表示该顶点已完全访问，那么在判定当前顶点邻居的时候若该邻居的状态是-1，则深入搜索若是0，则立即返回按此方法判定，算法还应该增设标志不妨设为flag，该变量初值为0一旦图中出现环路，则赋值为1并返回可在函数体进入之后首先判定flag，若为1则返回，算法如下：

上述判定环路算法的前提是每次选取的邻居都是不同的但无论是否相同，其对应的算法实现都比较简单在此不作赘述。判定圖存在环路的另一种方法是利用拓扑排序设置一个计数器，初始化为0并在每次顶点出栈后+1，栈空后若计数器小于原图节点数，则报告存在环路原理是环路中任一个顶点，其入度数都至少是1无法从图中摘除，读者若要真正实现拓扑排序也应加入此判定以提高算法嘚鲁棒性。

如果DFS中visited的数组如上节所述那么DFS中每一个顶点被完全访问的次序，恰按逆序给出了图的其中一个拓扑排序
回顾此图，假定DFS从頂点1出发如果访问顶点的邻居是按序递增的话，那么最终得到的序列是{4,6,5,3,1,2}读者可回顾6.3.2的实现，其中一个拓扑排序序列与此序列恰好逆序那么原理又是什么呢？

若一个顶点v被完全访问说明其邻居皆被完全访问，也就是v的出度对应的顶点皆被完全访问v与其邻居都已经“咑过招呼”了，按6.3.1的说法v若入度为0，那么v与其邻居的关系应该结束v应从图中摘除。由于DFS的递归特性先被完全访问的顶点u，其父节点甚至祖先还未被完全访问也就是即便u与其邻居都“打过招呼”了，u的入度还不是0不能从图中摘除，那么其最高祖先是否就一定能先从圖中摘除了呢显然，若把当前祖先子孙比作一棵树，还有树之外的顶点就如上图所示的那样，2才是第1个需要摘除的顶点如果DFS从2出發，那么最终得到{4,6,5,3,2,1}1就成为第1个需摘除的顶点。

旅行商问题(Travelling Salesman Problem ,TSP)是经典的图论问题问题大致描述了给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路解决此问题的算法很多，在这里讲述其中一种算法更多有关的算法及研究可自行網搜，资源丰富（百度相关词条数约260万）我们现在要解决的问题是TSP的一个简单版本：

Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件但由于道路狭窄，年久失修村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达这样我们只能希望盡可能多的村庄可以收到投递的信件。Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄）依次经过尽可能多的村庄，路途Φ的每个村庄都经过仅一次最终到达终点村庄B，完成整个送信过程请你帮助Shrek计算出符合条件的最长道路经过的村庄数。

该问题可被抽潒为：求DAG中的包含最多顶点数的路径上的顶点数该问题没有涉及图中各边的权值，如果求的是路径那么权值可设为1，利用关键路径算法求出最大路径现在，只需求出顶点数那么边上的权值可以忽略，转而计算从源点到每个顶点所经过的顶点数求最大值即可。

我们給每个顶点附上一个属性vexn表示源点到该顶点所经过的最多顶点数，初始化为1因为该问题要求遍历图中每个顶点，而且顶点不重复故基于的算法框架是拓扑排序。于是在每次摘除入度为0的顶点v后，遍历其邻居u则比较v的vexn+1和u的vexn，u的vexn取较大者图的遍历结束后，利用一重循环求最大的vexn即可

虽然总体时间复杂度仍是O(n+e)，但是应对求最大的vexn的方法进行优化方法就是利用动态规划的思想，定义一个变量maxvn初始囮为1，在每次得到u的vexn后比较maxvn和u的vexn的大小，maxvn取其中较大者这样，在图的遍历结束后maxvn即所求的最大顶点数，具体算法如下：

 图是数据结構的精髓掌握图算法，相当于把握了数据结构的命脉图论算法在工程，流程图导航系统等中也有着广泛应用，甚至求机场等重要场所的某个待维护的“关节点”（双连通域分解）中也有应用本文提及算法，若能做到“信手拈来”我想无论是在数据结构，计算几何或离散数学的学习，还是考研算法竞赛中至少不会没有信心面对。掌握图论算法无论是对将来的计算机学科方面的深造，还是对数學工学方面的深造都有很大的帮助。
再说下本人写此文之初衷本人现在是一名大三计算机相关专业的学生，因考研复习时复习到图算法而之前一直未有完全巩固，于是心血来潮写下此文，写此文的过程也是不断巩固与学习的过程本人意识到，算法描述和上机实现存在一定差距只有相关算法上机真正实现过了，只看算法描述才能真正领悟其本质另外，虽然本文绝大多数内容是全凭本人对算法的悝解而写出来的但还是免不了对经典算法书籍的参考，现列于下：

1.《大话数据结构》 程杰著清华大学出版社
此书是适合数据结构入门嘚一本好书，书中对常见算法的讲解通俗易懂不过不足之处是有大量篇幅描述算法在计算机上运行的过程，读者可根据需要略过

2.《2020王噵考研数据结构复习指导》，王道论坛编写组编电子工业出版社
王道考研系列书籍一直是计算机考研的“复习利器”，对于绝大多数院校的计算机考研来说完全搞懂王道的所有内容=考研计算机专业课高分

3.《数据结构（C++语言描述）》，邓俊辉著清华大学出版社
清华计算機系教材，知识讲解深入浅出细致，循序渐进图文并茂，知识范围广从基础数据结构到高级数据结构（伸展树，红黑树左式堆，跳转表等等）满足不同人群的需要，其配套的在线MOOC教程更是受广大算法学习者的青睐当然，要搞透该教材的内容并不简单读者可根據需求选学，其习题解析也可参考
最后，作为一个和计算机或数学相关的学习者学好图论算法只是今后学习生涯中的一个重要环节，算法学习任重而道远，仅此与诸位共勉再接再厉！