如何在O(n)时间内对邻接矩阵的列求和

Question

我有一个有向图的nxn邻接矩阵.我想搜索以查看是否有任何列总和为n.问题是我必须在O(n)时间内完成这项工作.有没有办法用O(n)时间来处理这个问题或者是不可能的(不需要代码)？

供参考,以下是我要解决的问题:

问题:

在学校的乐队选举期间,每个人对总统有一些偏好,并且一个人的偏好一直包括他/她自己."完美"的总统是每个人都喜欢的人,除了他/她自己不喜欢任何人.我们想要知道的是这样一个人是否存在.

• 定义与所述一组候选作为顶点和从顶点的有向边的有向图一到顶点b当且仅当b是在该组的偏好的一个.
• 有n个人
• 我们想要一种在O(n)时间内执行的算法
• 我们以nxn邻接矩阵的形式给出了上述图形

我想如果每个人都投票给"完美的总统",那么他/她将有n个传入节点,因此总结列应该给我们n.如果有更好的方法来解决这个问题而不是我正在做的事情,那么任何提示都会受到赞赏,以指导我朝着正确的方向前进.

Answer 1

让我重复规则并给出数字以便于参考:

1. 所有人都喜欢自己
2. 所有人都喜欢完美的总统(如果有的话)
3. 完美的总统(如果有的话)不喜欢任何其他人

让我们定义邻接矩阵,以便当人i具有对人j的偏好时,行i和列j中的值为1 .所有其他值均为0.

上述三条规则可以根据邻接矩阵重新制定如下:

1. 邻接矩阵的主对角线将全部为1.
2. 如果完美的总统是数字我,然后列我将有全1.
3. 如果完美的总统是第i,那么第i行将全部为0,除了第i列.

请注意,不能有两个或更多完美的总统,因为他们必须彼此偏好(规则2),这违反了规则3.

算法:Zig-Zag阶段

根据以下规则,通过从邻接矩阵的左上角(第0行,第0列)进行锯齿形,可以在线性时间内找到完美的总统(如果存在):

• 如果值为1,则向下移动到下一行(同一列)
• 如果值为0,则向右移动到下一列(同一行)
• 在保持矩阵边界的同时,不断重复前两步.
• 如果退出矩阵,则此阶段结束.让我们调用列,我们退出矩阵,列p.

观察:由于规则1,算法的这一部分永远不会进入主对角线上方的值:该对角线上的1值就像一个墙,当我们碰到它时,它会向下推动我们.因此,您将始终通过从最后一行向下移动来退出矩阵.在最极端的情况下,它将是在矩阵的右下角(在对角线上)的1处向下移动.

下面是一个邻接矩阵的简单示例,其中箭头表示算法如何规定从左上角到底行某处的1的路径:

 1   1   0   1   0
 ?
 1   1   0   1   0
 ?
 0 ? 1   1   1   0 
     ?
 0   0 ? 0 ? 1   0
             ?
 0   1   1   1   1
             ?
            =p

请注意,在这个例子中有一个完美的总统,但这当然不是一个要求:算法将给你一个值p,无论是否有一个完美的总统.

声明:完美的总统,如果有的话,必须是数字为p的人.

证明

给定是上述Zig-zag算法返回的p.

首先,我们通过矛盾证明:

一)完美的总统不能与一些人我小于p.

所以让我们假设相反:完美的总统是我和我<p:

由于我们在第0列开始之后的zig-zag阶段并最终在第p列中,并且由于我们在此过程中无法跳过列,因此有一段时间我们在第i列.由于我们没有留在那一列,它必须意味着列i的一行中有一个零,它叫我们向右移动.但是规则2要求如果我是一个完美的总统,第i列应该只有1值(规则2).矛盾!

其次,我们通过矛盾证明:

B)完美的总统不能与一些人我大于p.

所以让我们假设相反:完美的总统是我和我的人:

因为我们在第0行开始Z字形阶段并到达最后一行(参见观察),并且由于我们在此过程中不能跳过一行,所以有一刻我们在第i行.因为我们没有停留在那一行,而是在某个时刻向下移动(参见观察:我们向下移动矩阵向下移动),它必须意味着行i在其中一个列中有一个调用我们向下移动.这1不能是对角线上的1(在[i,i]处),因为我们没有到达列i:i大于p并且算法在列p中结束.所以它必须是第i行中的另一个,第二个.

但是规则3要求如果我是一个完美的总统,那么我应该只有一个1值,其他所有值都是零.矛盾!

这两个矛盾的证据让我们没有其他可能的数字,如果有一个完美的总统,而不是数字p.

算法:验证阶段

实际检查人p是否确实是一个完美的总统是微不足道的:我们可以检查列p是否包含全1,而行p只包含0,除了列i.

时间复杂性

所有这些都可以在线性时间内完成:至多2n-1个从矩阵中读出的锯齿形相位是必需的,以及2N-2个以上在最终验证阶段.因此,这是O(n).