2

我有一个有序图的邻接矩阵，我需要找到所有其他人都有边缘的顶点（在它的行中，除了对角线外，所有的都是 1）：

如果这是邻接矩阵：

0 0 0
0 0 0
1 1 0

该算法应产生顶点 3。

假设至少有一个这样的顶点。

O(N^2) 中的解决方案（N 是顶点数）是微不足道的，但是如何在 O(N) 中完成呢？

4

2 回答 2

2

前提条件：

  • 该图是有序图
  • 有一个顶点，所有其他顶点都有一条入边

由于边需要引起总排序，因此需要找到的顶点是“最小”顶点，它没有任何外边，因为这将是它已经连接到的其他边之一，并且会导致循环，这在有序图中是不允许的。

此外，图需要连接，因此所有路径都需要通向最小的顶点，这将我们带到了这个算法：

  1. 从所有行的集合作为可能的候选者开始
  2. 从集合中选择一个顶点并迭代可能的边缘到剩余的候选者。
    • 如果候选者有优势，则从列表中删除步骤 2 中的候选者，并在 2 处继续使用新候选者。
    • 如果该顶点没有边，则从候选集中删除目标候选并继续下一条可能的边。
    • 如果没有候选者，当前顶点就是你要找的那个

由于每个步骤都可以在 O(1) 中执行，并且在每个步骤中剩余候选者的集合都会减少，因此运行时间应该是 O(N)。

于 2013-06-20T06:57:13.067 回答
0

有序图是在其顶点上具有总顺序的图。没有其他要求，特别是它不限制边缘可以去哪里。所以这个问题的答案是，你有时不能做得比 O(N^2) 更好：考虑一个邻接矩阵，其中一行的所有非对角线条目都等于 1，而所有其他行的非对角线条目恰好为零。除非你非常幸运，否则你需要遍历几乎整个邻接矩阵来找出哪一行没有非对角零。

所以我假设你的意思是一个承认拓扑排序的有向图。也就是说，有向无环图（DAG）。在那种情况下，塞巴斯蒂安已经回答了它，但由于答案不被接受，让我试着更清楚地解释它。

如果 DAG 中的一个顶点有来自其他每个顶点的入边，那么它没有出边，因为这些将形成一个长度为 2 的循环。换句话说，它的对应列只有零。这样的顶点称为通用接收器，并且有一个众所周知的 O(N) 算法可以找到它。

通用算法：

  1. 候选人 := {0,1,...,N-1}
  2. 而|候选人| > 1 做：
    • 任意选择候选人 u 和 v
    • 如果 (u,v) 是一条边，则从候选者中删除 u，否则从候选者中删除 v
  3. 测试最后剩下的候选者是否是通用接收器

如果您知道您的图有一个通用接收器，那么最后一步是不必要的。

while 循环的迭代次数为 N-1，因为每次迭代都会从候选集中删除一个顶点。该算法是正确的，因为它只删除不能作为通用接收器的顶点 - 删除的顶点有一个出边，或者它没有来自某个顶点的入边。

在下面的代码中，您可以注意到我们没有明确保存候选人列表。for 循环步骤i中的候选者列表是{c​​andidate, i, i+1, ..., N-1}并且选择的候选者u和v是候选者和i。

// step 2
int candidate = 0;
for(int i=1; i<N; i++)
{
  if(edge[candidate][i] == 1)
      candidate = i;
}
// step 3
bool no_sink = false;
for(int i=0; i<N; i++)
{
  if(candidate  != i && (edge[candidate][i] == 1 || edge[i][candidate]==0))
      no_sink = true; 
}
if(no_sink)
    printf("No universal sink.");
else
    printf("The universal sink is %d.", candidate);
于 2013-09-05T08:36:53.503 回答