本
文
摘
要
图是一种重要的数据结构，在学习图的算法之前，需要了解图的基本概念，包括：顶点，边，有向，无向，权，路径回路，连通域，邻接点，度，入边，出边，入度，出度等等。
一、图的遍历
图的遍历是指从图中的某一个结点出发，按照某种搜索方法沿着图中的边对图中的所有结点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历根据访问结点的顺序，主要分为有：广度优先搜索（Breadth-First-Search）和深度优先搜索（Depth-First-Search）和A*搜索算法。
1.广度优先搜索（BFS）
首先访问起始结点v，接着由v出发，依次访问v的各个未访问过的邻接结点w1，w2，…，wi，然后再依次访问w1，w2，…，wi的所有未被访问过的邻接结点；再从这些访问过的结点出发，再访问它们所有未被访问过的邻接结点……依次类推，直到图中所有结点都被访问过为止。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批结点，为了实现逐层的访问，算法必须借助一个辅助队列，以记录正在访问的结点的下一层结点。该算法可以实现最短路径的查找。
2.深度优先搜索（DFS）
深度优先搜索与广度优先搜索类似，不过顾名思义，该算法以深度为先，之后再往广度扩延。
以上两种算法的详细介绍可见图的基本算法（BFS和DFS）。
3.A*算法
A*搜寻算法，俗称A星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。
算法最为核心的部分，就在于它的一个估值函数的设计上： f(n)=g(n)+h(n)。其中f(n)是每个可能试探点的估值，它有两部分组成：一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。h(n)设计的好坏，直接影响着具有此种启发式函数的启发式算法的是否能称为A星算法。
详细介绍参见：A*算法。
二、最短路径算法
4.Dijkstra算法
Dijkstra 算法，又叫迪科斯彻算法（Dijkstra），解决的是单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。该算法依据的是最短路径的最优子结构性质，从起点开始，每一步都走最短的路径，并不断更新每个点到起点的最短距离，则可以得到每个点到起点的最短距离。实际上，迪科斯彻算法是A*算法的特殊情况，即h(n)等于0的情况，此时f(n)=g(n)。Dijkstra算法无法判断含负权边的图的最短路。
详细介绍参见：单源最短路径 Dijkstra标记算法。
5.Bellman-Ford算法
Bellman-Ford算法又称贝尔曼-福特算法，是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
可参阅：Bellman-Ford algorithm。
6.Floyd-Warshall算法
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用，包括有向图、带负权边的图。Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。该算法基本思想：如果从一个点到另一个点的直接路径不是最短的，那最短路肯定要经过第三个点。所以就用所有的点都当一次中间点插入到当前两点间最短路径中，来判断是不是任意两点之间经过中间点路程会减小。核心算法只有5行：
对该算法的理解可参照：Floyd算法和A Libertine in Computer Science
三、最小生成树
7.Prim算法
普里姆算法（Prim算法），可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。
1).输入：一个加权连通图，其中顶点 *** 为V，边 *** 为E； 2).初始化：Vnew = {x}，其中x为 *** V中的任一节点（起始点），Enew = {},为空； 3).重复下列操作，直到Vnew = V： a.在 *** E中选取权值最小的边<u, v>，其中u为 *** Vnew中的元素，而v不在Vnew *** 当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； b.将v加入 *** Vnew中，将<u, v>边加入 *** Enew中； 4).输出：使用 *** Vnew和Enew来描述所得到的最小生成树。8.Kruskal算法
Kruskal算法，求加权连通图的最小生成树的算法。它是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一 *** ，那么就将它们合并，直到所有的点都属于同一个 *** 为止。
对于图G(V,E)，以下是算法描述：
输入： 图G
输出： 图G的最小生成树
具体流程：
(1)将图G看做一个森林，每个顶点为一棵独立的树 (2)将所有的边加入 *** S，即一开始S = E (3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E (4)重复(3)直到所有点属于同一棵树，边集E就是一棵最小生成树。具体参见：最小生成树之Kruskal算法
四、图匹配
9.匈牙利算法
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，用于求解指派问题(assignment problem)，算法时间复杂度为O(n^3)。
匹配：一个匹配即一个包含若干条边的 *** ，且其中任意两条边没有公共端点。选择这样的边数最大的子集称为图的最大匹配问题，最大匹配的边数称为最大匹配数。
具体的讲解请参见：匈牙利算法（二分图）和二分图最大匹配问题匈牙利算法。
五、强连通分支算法与网络流
10.Ford-Fulkerson算法
Ford-Fulkerson算法（FFA）是一种贪婪算法，用于计算流网络中的最大流量。流网络（Flow Networks）指的是一个有向图 G = (V, E)，其中每条边 (u, v) ∈ E 均有一非负容量 c(u, v) ≥ 0。如果 (u, v) ∉ E 则可以规定 c(u, v) = 0。流网络中有两个特殊的顶点：源点 s （source）和汇点 t（sink）。
最大流问题就是在满足容量限制条件下，使从起点s到终点t的流量达到最大。
Ford-Fulkerson方法首先对图中的所有边的流量初始化为零值，然后开始进入循环：如果在残存网络中可以找到一条从s到t的增广路径，那么要找到这条这条路径上值最小的边，然后根据该值来更新流网络。
详情参阅：最大流之Ford-Fulkerson方法详解及实现。
版权声明：本文为CSDN博主「石中路」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：图的十大经典算法_石中路的博客-CSDN博客_图论十大算法
封面图从GraphXR实例操作过程中截取
——————————————————
图客GraphXR官方网站：http://www.graphxr.cn
图客GraphXR试用：http://app.graphxr.cn
若有任何疑问，您可在评论区留言或通过私信联系图客TUKE
期待与您在“图”的世界共绘人类数据应用未来！
