Question

A sink in a directed graph is a vertex i such that there is an edge from every vertex j$\ne$i to i and there is no edge form 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) && E${}_1$)
j++;
if (j <n) E${}_2$;
}
while (i < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E${}_3$)
flag = 0;
if (flag)
printf(“Sink exists”);
else
printf (“Sink does not exist”);

Choose the correct expressions for E${}_1$ and E${}_2$

• A. E${}_1$ : !A[i] [j] and E ${}_2$ : i = j + 1 ;
• B. E${}_1$ : !A[i] [j] and E ${}_2$ : i = j + 1 ;
• C. E${}_1$ : A[i] [j] and E ${}_2$ : i = j ;
• D. E${}_1$ : A[i] [j] and E ${}_2$ : i = j ;

Answer 1

The correct option is C E${}_1$ : A[i] [j] and E ${}_2$ : i = j ;

A sink in a directed graph is a vertex such that there is an edge from every other vertex j $\ne$ i to i and there is no edge from i to any other vertex.


In above image 'd' is sink i.e. there is no outgoing edge by checking row of all vertex if we find any row with all zero then we find a potential vertex for sink.

While ((j < n) && !A[i] [j]) will check every entry row is 0 or not and until it find 1 in row, increment j.

If it find 1 in row skip a row by which it does not have any incoming edge by doing i = j.