本文介绍了在无向图周期的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

给定一个无向图G =(V,E)有n个顶点(| V | = N),你如何找到它是否包含为O一周期(N)

Given an undirected graph G=(V,E) with n vertices ( |V| = n ), how do you find if it contains a cycle in O(n) ?

推荐答案

我觉得深度优先搜索解决它。如果未探测边缘导致访问过的节点,则该图包含一个周期。这种情况也使得它为O(n),因为你可以探索的最大n条边,而不将其设置为true或被留下没有未开发的边缘。

I think that depth first search solves it. If an unexplored edge leads to a node visited before, then the graph contains a cycle. This condition also makes it O(n), since you can explore maximum n edges without setting it to true or being left with no unexplored edges.

这篇关于在无向图周期的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-14 14:26