在无向图中查找循环的大 O 复杂度
我需要计算在由 50 个节点组成的无向图中查找所有循环的复杂度。此外，如果图变大，复杂性是否会发生变化？如果网络变得相当大，复杂度会发生什么变化。此外，如果我只找到几个循环，那么我如何找到在图中找到几个循环的复杂性。
感谢您的期待！
I need to find the complexity of finding all the cycles in a undirected graph consisting of 50 nodes. Moreover, if the graph grows large, will the complexity be changed and what will be it if the network grows considerably large. In addition, if I find only few cycles then how do I find the complexity of finding few cycles in a graph.
Thanking you in Anticipation!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
使用深度优先搜索和主动标记节点，您只需注意搜索中遇到标记节点即可找到循环。
我相信，这是一种
O(V+E)方法，其中V是顶点或节点的数量，E是顶点或节点的数量。边缘或连接。如果将特定分支中的节点放在堆栈上，也可以轻松确定循环路径。只要确保每次回溯时弹出一个节点即可。
Using depth-first search and proactive marking of nodes, you can find cycles simply by noticing any time that you run into a marked node in your search.
This is an
O(V+E)approach, I believe, whereVis the number of vertices or nodes andEis the number of edges or connections.If you put the nodes in a particular branch on a stack, you can also easily determine the cycle path. Just make sure to pop a node out each time you backtrack.
给定的图可以具有指数数量的循环（在图的大小中）。考虑一个二分图，其中 vi 连接到 wi+1 % n 并且 wi 连接到 vi+1 %n。
因此，除非您有特定类型的图，否则多项式时间解决方案是没有希望的。
以指数时间运行的解决方案非常容易构建。考虑顶点的所有排列，看看该排序是否会导致循环。
当然，实际上您可以想出比这快得多的解决方案。
A given graph can have exponential number of cycles (in the size of graph). Consider a bipartite graph where vi is connected to wi+1 % n and wi is connected to vi+1%n.
So unless you have specific kind of graphs, there is no hope for polynomial time solutions.
A solution that runs in exponential time is very easy to build. Consider all permutations of vertices, see if that ordering results in a cycle.
Of course, in practical terms you can come up with solutions that are much faster than that.