图遍历算法的名称

Question

我正在寻找的是一个完整的图遍历算法列表,简要描述了它们的目的,作为研究它们的跳转点.到目前为止我知道:

• Dijkstra的 - 单源最短路径
• Kruskal's - 找到最小的生成树

还有哪些其他众所周知的？请为每个答案提供每种算法的简要说明.

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
• Floyd-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

网络流量

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

Answer 2

我头顶的几个:

深度优先和广度优先遍历,实际上只是触摸所有节点的两种不同方式.

Floyd-Warshall算法在(big-theta)(v ^ 3)时间内找到任意一对点之间的最短路径.

Prim的算法是Kruskal用于MST的替代算法.

还有用于查找完全连接的组件的算法,这些组件是节点组,您可以从组件中的任何成员到任何其他成员.这仅适用于"有向图",您只能在一个方向上遍历边.

就个人而言,我认为图论的最酷扩展(与你的问题没有完全相关,但如果你有兴趣了解更多关于图形的信息,那肯定是值得的),这就是"流动网络"的概念:http:// en.wikipedia.org/wiki/Flow_network.这是一种计算方式,例如,可以分配多少电力来满足具有各种电力需求和要求的房屋以及各种发电站.