edited by
7,368 views
38 votes
38 votes

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j \neq i$ to $i$ and there is no edge from $i$ to any other vertex. A directed graph $G$ with $n$ vertices is represented by its adjacency matrix $A$, where $A[i] [j] = 1$ if there is an edge directed from vertex $i$ to $j$ and $0$ otherwise. The following algorithm determines whether there is a sink in the graph $G$.

i = 0;
do {
    j = i + 1;
    while ((j < n) && E1) j++;
    if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");

Choose the correct expression for $E_3$

  1. $(A[i][j] \ \&\& \ !A[j][i])$
  2. $(!A[i][j] \ \&\& \ A[j][i])$
  3. $(!A[i][j] \ \left | \right | A[j][i])$
  4. $(A[i][j] \ \left | \right | \ !A[j][i])$
edited by

4 Answers

Best answer
55 votes
55 votes

If there is a sink in the graph, the adjacency matrix will contain all 1s (except diagonal) in one column and all 0s (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in $O(n)$ time complexity.

The first part of the code, is finding if there is any vertex which does not have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is $E_2$, which makes rows skip when there is no edge from i to it, making it impossible them to form a sink. This is done through

$E_1:  \ !A[i][j]$
and
$E_2: i = j$;

$E_1$ makes sure that there is no edge from $i$ to $j$ and $i$ is a potential sink till $A[i][j]$ becomes $1$. If $A[i][j]$ becomes $1$, $i$ can no longer be a sink, similarly all previous $j$ can also not be a sink (as there was no edge from $i$ to them and a sink requires an edge from all other vertices). Now, the next potential candidate for sink is $j$. So, in $E_2$, we must make $i = j$.

Now, the loop breaks when we found a potential sink- that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix. So, if the column in which this vertex comes is all 1s and the row is all 0s (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, $E_3$ is checking this condition. 

But in the code $\text{flag}$ is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.  So, the condition in $E_3$  must make flag = 0, if the found $i$ is not a sink. So, the condition should be: 

$A[i][j] \  \left | \right |\ !A[j][i]$

So, (D) is the answer.

edited by
12 votes
12 votes
Everything is well explained no need to add something new but at final answer for E3 is wrong somehow.

Lemme correct it with the concept of

"Logics"

A vertex would be sink iff there is an edge from every vertex to this vertex and there are not a single edge from this vertex to some other.

Now at E3 we have to tell condition for a non-sink vertex..

!(p and q) equals !p or !q

A vertex i would not be sink iff either there is an edge from it to some other vertex or there is atleast one vertex that dont have any edge to i.

So i mean answer is D.
10 votes
10 votes
If you have no idea of the algorithm, a better way to do this during GATE would be to assume a sink (say vertex 2) and see which of the given cases works.
7 votes
7 votes

According the definition given to sink

Now according to the definition we are checking the program. So, there must be incoming edge for the vertex of sink but those are not diagonal or not outgoing edges.

Now for i=0,j=1 , we check the condition if A[j][i] exists i.e !A[i][j] exists then take that vertex

like that i=0,j=2

            i=0,j=3

Now, if()  condition satisfies we make i=1 and j=2 (so here we are ignoring i=1 and j=1, means diagonal part)

Same thing happens while i=1,j=2

                                        i=1,j=3

and if() condition checking.(as scope of j is local inside while loop , so post increment not change j value of outside while loop) makes i=2

...............

like that we can say E1: !A[i][j] and E2 : i = j;

------------------------------------------------------------------------------------------------------------------------------------

Now, flag initially 1 , we got a upper triangular matrix from the above code.

But according to the definition we have to get a lower triangular matrix

So, to change upper triangular matrix to lower triangular matrix

E3 will be B)(A[i][j] && !A[j][i]) where flag=0

                                 

edited by
Answer:

Related questions

65 votes
65 votes
11 answers
2
Ishrat Jahan asked Nov 3, 2014
17,518 views
In a depth-first traversal of a graph $G$ with $n$ vertices, $k$ edges are marked as tree edges. The number of connected components in $G$ is$k$$k+1$$n-k-1$$n-k$
25 votes
25 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
8,917 views
What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...