The Gateway to Computer Science Excellence

+22 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 expression for $E_3$

- $(A[i][j] \ \&\& \ !A[j][i])$
- $(!A[i][j] \ \&\& \ A[j][i])$
- $(!A[i][j] \ \left | \right | A[j][i])$
- $(A[i][j] \ \left | \right | \ !A[j][i])$

+41 votes

Best answer

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

Now, the loop breaks when we found a potential sink- that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix. So, if the column in which this vertex comes is all 1s and the row is all 0s (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, $E_3$ is checking this condition.

But in the code $\text{flag}$ is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present. So, the condition in $E_3$ must make flag = 0, if the found $i$ is not a sink. So, the condition should be:

$A[i][j] \ \left | \right |\ !A[j][i]$

So, **(D) is the answer**.

+9 votes

Everything is well explained no need to add something new but at final answer for E3 is wrong somehow.

Lemme correct it with the concept of

"Logics"

A vertex would be sink iff there is an edge from every vertex to this vertex and there are not a single edge from this vertex to some other.

Now at E3 we have to tell condition for a non-sink vertex..

!(p and q) equals !p or !q

A vertex i would not be sink iff either there is an edge from it to some other vertex or there is atleast one vertex that dont have any edge to i.

So i mean answer is D.

Lemme correct it with the concept of

"Logics"

A vertex would be sink iff there is an edge from every vertex to this vertex and there are not a single edge from this vertex to some other.

Now at E3 we have to tell condition for a non-sink vertex..

!(p and q) equals !p or !q

A vertex i would not be sink iff either there is an edge from it to some other vertex or there is atleast one vertex that dont have any edge to i.

So i mean answer is D.

+6 votes

If you have no idea of the algorithm, a better way to do this during GATE would be to assume a sink (say vertex 2) and see which of the given cases works.

+3 votes

According the definition given to sink

Now according to the definition we are checking the program. So, there must be incoming edge for the vertex of sink but those are not diagonal or not outgoing edges.

Now for i=0,j=1 , we check the condition if A[j][i] exists i.e !A[i][j] exists then take that vertex

like that i=0,j=2

i=0,j=3

Now, if() condition satisfies we make i=1 and j=2 (so here we are ignoring i=1 and j=1, means diagonal part)

Same thing happens while i=1,j=2

i=1,j=3

and if() condition checking.(as scope of j is local inside while loop , so post increment not change j value of outside while loop) makes i=2

...............

like that we can say **E1: !A[i][j] and E2 : i = j;**

------------------------------------------------------------------------------------------------------------------------------------

Now, flag initially 1 , we got a upper triangular matrix from the above code.

But according to the definition we have to get a lower triangular matrix

So, to change upper triangular matrix to lower triangular matrix

E3 will be B)**(A[i][j] && !A[j][i]) **where flag=0

0

I really could not understand what are you trying to do?

i=0;j=1,2,3...

then from where i=1;j=1,2,3..

It would be great if you could explain :)

i=0;j=1,2,3...

then from where i=1;j=1,2,3..

It would be great if you could explain :)

0

@srestha

in ur matrix rep ....A[4][4] should be 0 right ?

i = 0; do { j = i + 1; while ((j < n) && E1) j++; if (j < n) E2; } while (j < n); flag = 1;

lets take a 3 * 3 matrix representation

so i varies from 0 to 2

and j varies from 0 to 2

i=0 j =1 then incrementing j until less than n so at last i=0 and j=2

now if(j<n) E2;

E2 => i= j

now j is 2 which is assigned to i

again eneters do while and j =i+1 which is 2+1 =3

there is no index as 3 right?

i am suddenly getting confused because of E2 statement

whats wrong in my analysis

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,169 answers

193,878 comments

94,301 users