好的。我的问题是，如果问题中没有说明，我不知道何时使用不同的图论算法。我怎么知道我什么时候会使用 Prim's/Kruskal's 而不是 Floyd/Dijkstra？问题中的哪些具体线索会为我需要解决什么提供线索？对不起，如果这看起来像一个愚蠢的问题，但我知道这些算法（但我还没有实现很多，但我正在尝试，就像现在一样！哈哈），但我似乎不知道如何使用他们比理论更实际。
请给提示！（如果您需要示例问题或其他问题，我可能会链接我在 onlinejudge 中找到的内容）
问问题
209 次
2 回答
1
让你的基础知识正确。了解 MST 和最短路径之间的区别。知道什么是连接等。知道何时将哪种算法应用于未明确提及的问题的下一部分是通过实践来实现的。
请参阅这些教程，http://community.topcoder.com/tc ?module=Static&d1=tutorials&d2=alg_index 尤其是图形及其数据结构简介中的那些。
然后在codechef和topcoder上练习一些问题。在一天结束时，您需要练习，练习，然后再练习。
于 2012-05-18T13:00:37.300 回答
0
如果您遇到的问题已简化为图论问题，您还应该知道您想用它做什么。
如果您需要找到两点之间的最短路径，那么您需要使用许多最短路径算法之一。
如果您需要找到一种将任务与工作人员匹配的方法，那么您可能会将其简化为最大流量问题并使用最大流量算法来解决它。
我不确定我能否帮助您区分最短路径问题和最大流量问题，但如果您只需要知道使用哪种算法，那么这很简单：没关系。只要您选择一种最小生成树算法来解决最小生成树问题，您就会得到最小生成树。
从图论的角度看问题要求你找到什么，想想你将如何从逻辑上解决它，并选择一个与该过程和结果相匹配的算法。
于 2012-05-18T14:58:37.753 回答