如何找到带有邻接矩阵表示的有向图的通用汇 [英] 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 Please help me, I spent an entire evening working on it (maybe I'm rather dumb). And feel free to comment on any other aspect of my code (for example I seem to be 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是否通用 接收器，因为我们知道接收器是否存在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屋！