算法|10种图算法直观可视化解释( 二 ) 算法

用于检测图中的循环。

用于拓扑排序。

用于解决只有一个解的谜题(如迷宫)

最短路径
从一个顶点到另一个顶点的最短路径是图中应该移动的边的权值总和最小的路径。
图4显示了一个动画，其中确定了图中顶点1到顶点6的最短路径。
算法
Dijkstra的最短路径算法、bellman算法
应用
用于在谷歌maps或Apple maps等地图软件中查找从一个地方到另一个地方的路线。
用于网络中解决最小时延路径问题。
在抽象机器中，通过不同状态之间的转换来确定达到某一目标状态的选择(例如，可以用来确定赢得一场比赛的最小可能的走法数) 。
循环检测 Cycle Detection
循环是图中第一个顶点和最后一个顶点相同的路径。如果我们从一个顶点出发，沿着一条路径，最后到达起始点，那么这条路径就是一个循环。循环检测是检测这些循环的过程。图5显示了遍历一个循环的动画。
算法
【算法|10种图算法直观可视化解释】Floyd周期检测算法、布伦特算法
应用

用于基于消息的分布式算法。
用于使用集群上的分布式处理系统处理大规模图形。
用于检测并发系统中的死锁。
在加密应用程序中用于确定可以将消息映射到相同加密值的消息的密钥。

最小生成树
最小生成树是图的边的子集，它连接所有边权值最小和的顶点，不包含任何循环。
图6是一个显示获得最小生成树的过程的动画。
算法
Prim算法、Kruskal算法
应用

用于在计算机网络中构建广播树。
用于基于图的聚类分析。
用于图像分割。
用于社会地理区域的区域化，将区域划分为相邻区域。

强连通分量(strongly connected components)
如果图中的每个顶点都能从其他每个顶点到达，那么这个图就是强连通的。
图7显示了一个示例图，其中包含三个强连接的组件，顶点用红色、绿色和黄色表示。
算法
Kosaraju的算法、Tarjan的强连通分量算法
应用

用于计算Dulmage-Mendelsohn分解，它是完全二分图的一种分类。
在社交网络中，用来寻找一群关系密切的人，并根据共同的兴趣提出建议。

拓扑排序
图的拓扑排序是对它的顶点进行线性排序，因此对于排序中的每条有向边(u v) ，顶点u都在v之前。
图8显示了顶点(1、2、3、5、4、6、7、8)的拓扑排序示例。可以看到顶点5应该在顶点2和3之后。类似地，顶点6应该在顶点4和5之后。
算法
Kahn算法
基于深度优先搜索的算法
应用

用于指令调度。
用于数据序列化。
用于确定在makefile中执行的编译任务的顺序。
用于解析链接器中的符号依赖关系。

图着色
图着色在保证一定条件下给图的元素分配颜色。顶点着色是最常用的图形着色技术。在顶点着色中，我们尝试用k种颜色给图的顶点着色，任何两个相邻的顶点都不应该有相同的颜色。其他着色技术包括边缘着色和脸部着色。
图的色数是为图着色所需的颜色的最小数目。
图9显示了使用4种颜色的示例图的顶点着色。
算法
使用广度优先搜索或深度优先搜索的算法、贪婪着色
应用