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 expression for E${}_3$

• A. (A[i] [j] && !A[j] [i])
• B. (!A[i] [j] $\mid \mid$ A[j] [i])
• C. (A[i] [j] && !A[j] [i])
• D. (A[i] [j] $\mid \mid$ !A[j] [i])

Answer 1

The correct option is D (A[i] [j] $\mid \mid$ !A[j] [i])

In this program initially flag is set to 1 i.e. assume sink is present in the graph.

And by using For loop if flag is reset to 0 then sink is not present otherwise sink is present.

For loop will set flag = 0 if the column entries are all 1 for sink (vertex) and the entries for row is all 0.

If we look at above diagram for vertex 'd', i =3 and j = 0.

So while ((j! = i) && (A[3] [0]$\parallel$!A[0][3])
True && (0$\parallel$!1))
True && false = false, so flag not set to 0.

Then while ((j! = j)&& (A[3][1]$\parallel$!A[1] [3])
True && false = false, so flag not set to 0.

Try for other vertex we will set flag = 0 i.e. not exist sink.

Like this for vertex d flag will not set to 0 i.e. sink exist.