A sink in a directed graph is a vertex i such that there is an edge from every…

GATE · 2005 · IT

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 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 E1 and E2.

  1. A.

    E1 : A[i][j] and E2 : i = j;

  2. B.

    E1 : !A[i][j] and E2 : i = j + 1;

  3. C.

    E1: !A[i][j] and E2 : i = j;

  4. D.

    E1 : A[i][j] and E2 : i = j + 1;

Attempted by 267 students.

Show answer

Correct answer: C

The worked solution is available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…