给定具有n个顶点（| V | = n）的无向图G =（V，E），您如何查找它是否包含O（n）的循环？
慕村225694
浏览 734回答 3
3回答
肥皂起泡泡
实际上，深度优先（或实际上广度优先）搜索还不够。您需要一个复杂得多的算法。例如，假设有一个图，它的节点为{a，b，c，d}，而边为{（a，b），（b，c），（b，d），（d，c）}的边为（x ，y）是从x到y的边。（看起来像这样，所有边缘都朝下。） (a) | | (b) / \ (d) | | | \ / (c)然后进行深度优先搜索可能会访问节点（a），然后访问（b），然后访问（c），然后回溯到（b），然后访问（d），最后再次访问（c），并得出一个循环-没有的时候。广度优先发生类似的事情。您需要做的是跟踪访问过程中的哪些节点。在上面的示例中，当算法到达（d）时，它已经完成了对（c）的访问，但没有完成对（a）或（b）的访问。因此，重新访问完成的节点很好，但是访问未完成的节点意味着您有一个周期。通常的做法是为每个节点上白色（尚未访问），灰色（正在访问后代）或黑色（完成访问）上色。这是一些伪代码！define visit(node n): if n.colour == grey: //if we're still visiting this node or its descendants throw exception("Cycle found") n.colour = grey //to indicate this node is being visited for node child in n.children(): if child.colour == white: //if the child is unexplored visit(child) n.colour = black //to show we're done visiting this node return那么只有当有一个循环（最初所有节点都应该为白色）时，运行visit（root_node）才会引发异常。