时间戳

首页 > 解决方案 > 二次时间顶点覆盖验证

algorithm - 二次时间顶点覆盖验证

问题描述

假设给定一个无向图G，其n顶点和m 边由n x n邻接矩阵表示A，并且还给您一个顶点子集S（由大小为 的数组表示m）。你如何检查是否S是G具有二次时间和空间复杂度的顶点覆盖？

根据顶点覆盖的定义，我知道我们要求每条边都必须与包含在S.

我可以很容易地想出一个三次算法：迭代邻接矩阵；每个1代表一条边(u, v)。检查u是否v在S. 如果没有，答案是否定的。如果我们到达邻接矩阵的末尾，答案是肯定的。

但我怎样才能O(n^2)及时做到这一点？我想到目前为止我所做的唯一真正的“观察”是，如果我们已经在S. 但是，这对我帮助不大。

有人可以帮助我（或指出我正确的方向）吗？

谢谢

标签： algorithmgraph-theory

解决方案

构造一个数组T，它是所有不在的元素的位置S。

进而：

for i in T:
    for j in T:
        if A[i][j] == 1:
            return False
return True

推荐阅读