#Algorithms Gate 2005 Question Self Doubt.

Question

Source of the question - here

A sink in a directed graph is a vertex i such that there is an edge from every vertex $j ≠ 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");

 

Correct Answer is - E1: ! A[i][j] and E2: i=j;

Can someone explain how E2 = i=j. 

i=j means we are looking for diagonal elements. So, how do we look for them as a sink as all the diagonal elements in adjacency matrix is = 0. You can take a Graph with 4 vertices and make anyone of them as a sink.

Answer 1

 

Comments

Nice efforts and forced me to understand the whole otherwise i am going to left it...

---

 

I mean why not (A[i][j] && !A[j][i])??

@ srestha 

this is because we are assuming the flag=1 (means sink is exist) and we are checking this condition so adjacency matrix for that vertex who have sink maintains the all row elements 0 and all columns corresponding elements to 1. so each time it is fall for 0 || 0 for every other element except for daigonal . j!=i first one make diagonal check and make it false. 

and we are trying to avoid flag=0 if sink exists.

---

Nice.. Very Beautiful Explanation. @Arjun’s Sir “except diagonal element” phrase was not understood properly, you made it clear now, i have spent nearly 4 hours on this question.. thanks man