使用具有特定运行时间的算法在图中查找三角形
使用具有特定运行时间的算法在图中查找三角形
提问于 2019-06-13 02:54:59
我需要找到一个在无向图中找到三角圈的算法。算法的运行时间应该是n^2,81
我真的不知道如何才能做到这一点。如果有人能帮上忙那就太好了！
谢谢!
回答 1
Stack Overflow用户
发布于 2019-06-13 04:40:07
另一种方法是使用Breadth-first search算法的修改版本。试着想一想你能得到的简单的图形，一个三角形。从具有BFS的任何顶点开始，并存储谁是父节点以及与根的距离。每当你遇到一个已经访问过的(但没有完成的)顶点时，你可以简单地给它上色为灰色，你要检查与父对象的距离。
B Start BFS from A: node A has dist=0, parent=Null
/ \ node B has dist=1, parent=A
/ \ node C has dist=1, parent=A
A - - C这个算法的复杂度(BFS)是顶点数+边数：O(|V| + |E|)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56568690
复制相关文章
相似问题