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 E3
- A.
(A[i][j] && !A[j][i])
- B.
(!A[i][j] && A[j][i])
- C.
(!A[i][j] | | A[j][i])
- D.
(A[i][j] | | !A[j][i])
Attempted by 130 students.
Show answer & explanation
Correct answer: D
Answer: Use the expression (A[i][j] || !A[j][i]).
Reasoning:
Definition: A vertex i is a sink if for every other vertex j (j != i) there is no edge from i to j (A[i][j] == 0) and there is an edge from j to i (A[j][i] == 1).
The verification loop must detect any violation of these two required properties. A violation for a specific j occurs when either there is an outgoing edge from i to j (A[i][j] == 1) or there is no incoming edge from j to i (A[j][i] == 0).
So the violation condition is: A[i][j] == 1 OR A[j][i] == 0, which in boolean form is A[i][j] || !A[j][i].
Therefore, in the loop if ((j != i) && (A[i][j] || !A[j][i])) then flag = 0 correctly marks i as not a sink when any violation is found.
Why the other expressions are wrong:
Expression (A[i][j] && !A[j][i]) is true only when both an outgoing edge exists and an incoming edge is missing at the same time; it misses violations where only one of these holds.
Expression (!A[i][j] && A[j][i]) is true exactly for the desirable sink relation (no outgoing edge and an incoming edge), so it would incorrectly mark valid sink relations as violations.
Expression (!A[i][j] || A[j][i]) is true for many desirable sink cases (no outgoing or has incoming) rather than for violations, so it does not detect non-sink cases correctly.