无向非加权图中的最长路径 [英] Longest Path in an undirected unweighted graph

问题描述

我遇到了一个问题，我必须找出给定图中的最长路径.我有一条边列表(例如{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!

这篇关于无向非加权图中的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！