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
Wherever we have an '1' there is a connection in the graph for example V1 (Vertex1) does not connected with its selfCode: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
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"where i and j are incremented above???? Is there anyone who can trace this algorithm??? the complexity here is O(n^2) ?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
Thank you in advance