图遍历算法的名称(Names of Graph Traversal Algorithms)

我正在寻找的是图的遍历算法的完整列表，与它们的目的简要说明，作为一个跳下点研究他们。 到目前为止，我所知道的：

• Dijkstra的 - 单源最短路径
• 克鲁斯卡的 - 找到一个最小生成树

什么是其他一些知名的呢？ 请您的每一个答案的提供每个算法的简要说明。

Answer 1:

井的已知，分别是：

• 深度优先搜索http://en.wikipedia.org/wiki/Depth-first_search
• 广度优先搜索http://en.wikipedia.org/wiki/Breadth-first_search
• Prim算法http://en.wikipedia.org/wiki/Prim's_algorithm
• Kruskal算法http://en.wikipedia.org/wiki/Kruskal's_algorithm
• Bellman-Ford算法http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
• 弗洛伊德- Warshall算法http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
• 反向删除算法http://en.wikipedia.org/wiki/Reverse-Delete_algorithm
• Dijkstra's_algorithm http://en.wikipedia.org/wiki/Dijkstra's_algorithm

网络流量

• 福特Fulkerson算法http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
• 最大流量http://en.wikipedia.org/wiki/Maximum_flow_problem

Answer 2:

我的头顶部的几关：

深度优先和广度优先遍历，实际上它是两个接触的所有节点的不同方式。

Floyd-Warshall算法发现的任何一对点，在（大-θ）（V ^ 3）时间之间的最短路径。

Prim算法是克鲁斯卡对MST的替代品。

也有寻找完全连接组件，它们的节点，您可以从任何成员获得在组件中任何其他成员的组算法。 这只事项“有向图”，在这里你可以遍历边只有一个方向。

我个人认为，图论的最酷的扩展名（不完全关系到你的问题，但如果你有兴趣了解更多关于一般的当然值得您光顾图表）是“流动网络”的概念： HTTP：// en.wikipedia.org/wiki/Flow_network 。 它是计算一下，比如说，一个多少电力可以分布在房屋有各种功率的需求和要求的方式，以及各种发电站。

Answer 3:

图形算法

• http://en.wikipedia.org/wiki/List_of_algorithms#Graph_algorithms

在一个地方所有算法

• http://en.wikipedia.org/wiki/List_of_algorithms

的算法和数据结构词典：

• 词典： http://xlinux.nist.gov/dads/

• 通过地区： http://xlinux.nist.gov/dads/termsArea.html

• 通过术语类型： http://xlinux.nist.gov/dads/termsType.html

• 在DIFF所有实现的列表。 语言： http://xlinux.nist.gov/dads/termsImpl.html

文章来源: Names of Graph Traversal Algorithms