edited by
9,221 views
40 votes
40 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$;
edited by

1 Answer

Best answer
57 votes
57 votes

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
Answer:

Related questions

65 votes
65 votes
11 answers
2
Ishrat Jahan asked Nov 3, 2014
17,519 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/...