<分区>
我有一个关于 DFS 的简单问题,我想了解如何使用它,而不是如何解决整个问题。我真的是在寻找一个解释,而不是我的家庭作业的解决方案。
我先把问题写下来
"Suppose you have an undirected graph G=(V,E) and let three of its vertices to be called v1, v2 and v3. Find an algorithm which determines if these three vertices are part of a clique (complete graph) (k>=3)"
现在我想使用 DFS 来解决它。据我所知,DFS 会让我知道 v1、v2 和 v3 是否在同一个强连接组件中。如果我是正确的,我还应该确定 G 是否也是一个团(完整图)。
我在网上看了看,我发现断言一个图是否是clique是NP问题,不容易解决。我对么?我错过了什么吗?是否有任何属性可以用来立即确定图形是否完整?