Geo*_*ous 2 algorithm graph-algorithm
我的问题是关于检测是否存在循环.我不关心循环发生在哪里,但只有在存在循环的情况下.特别是,我正在研究(最大)生成树算法的实现.我按降序对边缘进行了排序,然后我选择了一条边并将其放入图形边缘IFF的集合中,它不会导致循环.
我发现,对于无向图,只能检查是否no_of_edges> no_of_vertices - 1.这是正确的吗？我试图找到一个不真实的案例,但我不能.当然,这并不意味着这是正确的.
谢谢
Ant*_*ima 6
只需运行DFS搜索; 它会自动检测循环,因为这是DFS的停止条件 - 当你进入一个已经在堆栈中的节点时就会停止,那就是你找到一个循环的时候.
归档时间：
14 年 前
查看次数：
3669 次
最近记录：