in Algorithms edited by
7,149 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 expressions for $E_1$ and $E_2$

  1. $E_1 : A[i][j]$ and $E_2 : i = j$;
  2. $E_1 :\ !A[i][j]$ and $E_2  : i = j + 1$;
  3. $E_1:\ !A[i][j]$ and $E_2 : i = j$;
  4. $E_1 : A[i][j]$ and $E_2 : i = j + 1$;
in Algorithms edited by
7.1k views

2 Comments

can anybody elaborate this with the helpof diagram?????????????????/
1
1

vertex i is the sink in this graph

0
0

1 Answer

53 votes
53 votes
Best answer

If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (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 doesn't 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 for 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$. 

So, answer is (C)

For $E_3$,  https://gateoverflow.in/3857/gate2005-it_84b

edited by
by

4 Comments

yes that's a typo.https://gateoverflow.in/3857/gate2005-it-84b

anyone please correct it.

0
0
5
5

@Arjun sir .. Please change E1:A[i][j] to  E1: !A[i][jin your answer.

 

1
1
Answer:

Related questions