c - 如何找到具有邻接矩阵表示的有向图的通用汇

我正在做一个练习(自学):
“展示如何确定有向图 G 是否包含通用链接 - 给定邻接矩阵，在时间 O(V) 内具有入度 (V-1)(V 是顶点数)和出度为 0 的顶点对于 G。
我在这里写了代码:

    int UniversalSink(const int *a, int N)
{
    int i,j,i1,j1,q;
    i=0;


    i=0;
    q=YES;
    j=-1;
    do
    {
    j++;
    if (j==N)
        break;

    while ( (*(a+i*MAX+j)) ==0 )
    {
        j++;
        if (j==N)
        {

        break;
        }
    }
    if (j==N)
        break;
    q= YES;

    for (; i<j; i++)
        if ( (*(a+i*MAX+j)) ==0 )
        {
           i=j,j=i-1;
           q= NO;
           break;
        }
    if (q==NO)
        continue;
    q=YES;

    /*
    for (i=0; i<=j; i++ )
        if (a[j][i] ==1 )
        {
        i=j;
        q=NO;
        ok=NO;
        trai = NO;
        break;

        }
    if (q==NO)
        continue;
    */
    q=YES;

    for (i1= j+1; i1<N; i1++)
        if ((*(a + i1*MAX +j)) ==0 )
        {
        i=i1, j=i-1;
        q=NO;
        break;

        }
    if (q==NO)
        continue;
    }
    while (j<N);

    {
    i1=i;
    for (j1=0; j1<N;j1++)
        if ( (*(a + i1*MAX +j1 ))  ==1 )
        return -1;
    j1=i;
    for (i1=0; i1<N;i1++)
    {
        if (i1==j1)
        continue;
        if ( (*(a + i1*MAX +j1))==0)
        return -1;
    }
    return i;

    }

它需要一个 N-N 矩阵并返回通用接收器的位置(如果存在则为 0 到 N-1，如果不存在则为 -1)
但是我真的不知道它是否是 O(V)，事实上我不确定它是否总是会计算出所需的结果
(随意评论我的代码的任何其他方面，例如使用太多中断)

最佳答案

您可以使用以下代码:

int DetectSink(matrix G, int V) {
    int i = 0;
    int j = 0;
    while (i < V && j < V)
        if (G[i][j])
             i = i + 1;
        else j = j + 1;
    if (i < V && IsSink(G, i)) return i;
    return -1;
}

如果 k 是一个通用汇，那么第 k 个
邻接矩阵( G )的行将是
全部为 0，第 k 列将全部为
1 秒(除了 G[k][k] = 0 )。

OBS:我们可以得出结论，最多只有一个汇。

如果 k 中存在通用接收器 G ，那么最终，
我们可以定位 (i = k, j) 或 (i, j = k) 。

            k
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
k | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+
  |   |   | 1 |   |   |
  +---+---+---+---+---+

如果我们在行 k (j=k) 之前到达列 k (i=k) ，
我们的算法执行 然后 块，直到(i = k, j = k) ，然后它执行 else 块
直到 (i = k, j = V) 。
在其他情况下，如果首先到达第 k 行，则
第 k 列，然后 else 块执行到
while 循环结束，直到 (i = k, j = V) 。

最后我们必须检查 i 是否是通用的
sink，因为我们知道是否存在 sink 是 i ，
但我们不知道我们的算法在做什么
如果通用接收器不在 G 中。

运行时间是 O(V) ，因为在每一步
我们增加 i 或 j ，所以最多 2V 这样
操作发生。 IsSink 部分是 O(V) 。

使用 Divide & Conquer 有一个很好的解决方案:

在这个解决方案中，我们保留了一组候选人
到普遍的水槽，在每一步我们都成对
顶点并丢弃两个顶点之一，按顺序
分析一半的初始候选人。

关于c - 如何找到具有邻接矩阵表示的有向图的通用汇，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29259365/