我遇到了一个问题,我必须找出给定图中的最长路径.我有一条边列表(例如{AB,BC}),它指出在顶点/节点(A,B,C)之间有一条边.现在,我想找出可能的最长路径(不重复顶点),使其涵盖从任何顶点/节点开始的最大节点.
I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to figure out the longest path possible (not repeating the vertex) such that it covers maximum nodes starting from any vertex/node.
解决这个问题的最佳方法是什么? 我必须将其作为程序来实现.
What can be the best way to solve this? I have to implement this as a program.
我在Google上查找了 最小生成树,Dijkstra的Alogorithms等.但无法找出最适合此问题的方法.
I looked up google for Minimum Spanning Tree, Dijkstra's Alogorithms , and many more. but can't figure out what would suit best for this problem.
任何帮助或阅读参考文献将不胜感激.
Any help or reading references would be much appreciated.
推荐答案由于您的问题不会说图形是循环的,还是没有,所以您有两个选择:
Since your question doesn't speak whether the Graph is Cyclic or Not you have two options:
选项1 :图形为DAG
您很幸运,您可以在图形上使用拓扑排序并获得最长的路径!
You are Lucky, you can use topological sort on the graph and get the longest path!
选项2 :图形不是DAG:
使用评论中提到的哈密顿算法!
Use the Hamiltonian Algorithm as mentioned in the Comments!
更多推荐
无向非加权图中的最长路径
发布评论