sink detection algorithm

Hello to all.... I have an exercise that I want to do .... I am trying but I face some difficulties... I have found the algorithm..... I know the nature of the problem but I can't describe completely the work of the algorithm ...

A sink is a node without outcoming edges .... and I found an algorithm that it finds a sink. For example all are starting by a adjacency matrix for example

Code:

---

            V1    V2    V3    V4    V5
 V1      0        1        1      1      1

 V2      0        0        0      1      1

 V3      0          1        0      1      1

 V4      0          0        0        0      1

 V5      0          0        0      0      0

---

Wherever we have an '1' there is a connection in the graph for example V1 (Vertex1) does not connected with its self

V2 does not connected with V3 but with V4 and V5.

The sink here is the Vertex V5 , in order to determine the sink we should find the vertex that it has a row with only zeros and a column with only ones .....

The algorithm is :

Code:

---


UNIVERSAL_SINK(A)

let A be |V| X |V|  (|V| number of vertex)

i <- j <- 1

while i <= |V| and j<= |V|
do if aij =1
then i <- i+1
else j<- j+1

s<-0

if i > |V|
then return "there is no universal sink"

elseif IS_SINK (A,i) = FALSE

then return "there is no universal sink"

else return i "is a universal sink"

---

Code:

---

IS_SINK(A,k)
let A be |V| X |V|
for j<- 1 to |V|
do if akj =1  //Check for 1 in row k
then return FALSE

for i<-1 to |V|
do if aik =0 and i!=k  //Check for 0 in column k
then return FALSE

return TRUE

---

where i and j are incremented above???? Is there anyone who can trace this algorithm??? the complexity here is O(n^2) ?

Thank you in advance

Since this is a digraph couldn't you do a topological sort on it? The nodes without any incoming edges should appear in either end, depending on sort order afaik.

Do you want to give you the figure ????