开发者

Finding all cycles in an undirected graph

开发者 https://www.devze.com 2023-02-12 04:10 出处:网络
If I have an undirected graph, how can I get a list of all cycles? For example, from the following graph, I would want the cycles:

If I have an undirected graph, how can I get a list of all cycles?

For example, from the following graph, I would want the cycles:

(a,b开发者_开发问答,d,e,c)
(a,b,c)
(b,d,e)

Finding all cycles in an undirected graph


this is not possible in polynomial time as if possible then we could use this to find all cycles and hence cycle of largest length which implies we can solve hamiltonian cycle problem completely in polynomial time.


You presumably want only simple cycles (those that don't repeat a vertex), or there's an infinite number of them. Even then, there can be an exponential number of cycles. Perhaps this isn't the problem you really want to solve?

0

精彩评论

暂无评论...
验证码 换一张
取 消