如何找到具有邻接矩阵表示的有向图的通用汇 [英] How to find the universal sink of a directed graph with an adjacency-matrix representation

问题描述

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

I'm working on an excercise (self-study): "Show how to determine whether a directed graph G contains a universal link - a vertex with in-degree (V-1) (V is the number of vertices) and out-degree 0 in time O(V), given an adjacency matrix for G. I have written the code here:

    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)，事实上我不确定它是否总是会计算出所需的结果

It takes a N-N matrix and returns the position of the universal sink (0 to N-1 if it exists and -1 if it doesn't) However I don't really know if it is O(V) or not, and in fact I'm not sure if it will always compute the desired result at all

(随意评论我的代码的任何其他方面，例如使用过多的中断)

(Feel free to comment on any other aspect of my code e.g. using too many breaks)

推荐答案

可以使用以下代码:

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 列将全部为1s(除了G[k][k] = 0).

If k is an universal sink, then the k-th row of the adjacency-matrix ( G ) will be all 0s, and the k-th column will be all 1s (except G[k][k] = 0).

OBS:我们可以得出结论，最多只有一个接收器.

OBS: We can conclude that there is at most one sink.

如果在 G 中存在一个通用接收器 k，那么最终，我们得到位置 (i = k, j) 或 (i, j = k).

If an univeral sink k exist in G, then eventually, we get to position (i = k, j) or (i, j = k).

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

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

If we reach column k (j=k) before row k (i=k), our algorithm excecutes the then block until (i = k, j = k), then it executes the else block until (i = k, j = V). In other case, if k-th row is reached first than k-th column, then the else block excecutes to the end of while loop until (i = k, j = V).

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

At the end we must check if i is an universal sink, because we know if a sink exist it is i, but we have not idea what our algorithm is going to do if an universal sink is not in G.

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

The running time is O(V), because in every step we increment i or j, so at most 2V such operations occurrs. The IsSink part is O(V).

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

There is a nice solution using Divide & Conquer:

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

In this solution we keep a set of candidates to universal sink and in every step we make pairs of vertexs and discard one of two vertexs, in order to analize one half of the initial candidates.

这篇关于如何找到具有邻接矩阵表示的有向图的通用汇的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！