我需要的是一份包含广泛的图遍历算法列表，其中简短说明其目的，作为研究它们的起点。到目前为止，我知道以下算法：
- Dijkstra-单源最短路径
- Kruskal-找到最小生成树
3个回答
25
众所周知的是：
- 深度优先搜索 http://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
- 广度优先搜索 http://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
- 普里姆算法 http://zh.wikipedia.org/wiki/%E6%99%AE%E9%87%8C%E5%A7%86%E7%AE%97%E6%B3%95
- 克鲁斯卡尔算法 http://zh.wikipedia.org/wiki/%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95
- 贝尔曼-福德算法 http://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%9B%BC-%E7%A6%8F%E5%BE%B7%E7%AE%97%E6%B3%95
- 弗洛伊德-沃舍尔算法 http://zh.wikipedia.org/wiki/%E6%B5%8F%E8%A7%88%E6%9F%A5%E6%89%BE
- 反向删除算法 http://zh.wikipedia.org/wiki/%E5%8F%8D%E5%90%91%E5%88%A0%E9%99%A4%E7%AE%97%E6%B3%95
- 迪杰斯特拉算法 http://zh.wikipedia.org/wiki/%E8%BF%AA%E6%9D%B0%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95
网络流
- user467871
8
以下是我能想到的几个：
深度优先和广度优先遍历，实际上是两种不同的触及所有节点的方法。
Floyd-Warshall算法在（大O）(v^3)时间内查找任意一对点之间的最短路径。
Prim算法是MST的另一种选择，与Kruskal算法类似。
还有寻找完全连接组件的算法，这些组件是节点的分组，其中您可以从组件中的任何成员到达任何其他成员。 这仅适用于“有向图”，其中您只能沿着一条方向遍历边缘。
就我个人而言，我认为图论的最酷的扩展（与您的问题不完全相关，但如果您有兴趣学习有关图形的更多信息，则肯定值得）是“流网络”的概念：http://en.wikipedia.org/wiki/Flow_network。 它是一种计算方式，例如，可以在配有各种功率需求和要求以及各种发电站的房屋之间分配多少电力。
- agorenst
2
你的评论非常有用和深刻。感谢你抽出时间来回复，我已经接受了这个答案。 - dreadwail
“Fully connected components”的正确名称是强连通分量。 - J D
3
图算法
所有算法汇总
算法和数据结构词典:
- reuf
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接