A sink in a directed graph is a vertex i such that there is an edge from every…
2005
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");
Choose the correct expressions for E
1
and E
2
- A.
E1 : A[i][j] and E2 : i = j;
- B.
E1 : !A[i][j] and E2 : i = j + 1;
- C.
E1: !A[i][j] and E2 : i = j;
- D.
E1 : A[i][j] and E2 : i = j + 1;
Attempted by 126 students.
Show answer & explanation
Correct answer: C
Answer: E1 is !A[i][j] and E2 is i = j.
Reasoning:
Key idea: eliminate vertices that cannot be sinks by pairwise comparison. If the current candidate i has an outgoing edge to j (A[i][j] == 1), then i cannot be a sink, so j becomes the new candidate.
Inner loop behavior: set j = i + 1 and advance j while the current candidate i does not point to j (while !A[i][j]). This finds the first j for which A[i][j] == 1 (or reaches the end).
When the loop stops because A[i][j] == 1, assign i = j. The vertex j proved the previous i cannot be a sink, so j is the next candidate. Repeat until j reaches n.
Verification step: after the candidate is found, check for every other vertex k that k has an edge to the candidate and the candidate has no outgoing edge to k. In code terms, the final check should set flag = 0 if for any k != i either A[k][i] == 0 (someone does not point to i) or A[i][k] == 1 (i points out).
Complexity: candidate selection runs in O(n) and verification is O(n), so overall O(n).