maintain an Adjacency matrix.
Matrix state: for each element(row), mark as 1 for a column, if row->
column is reachable.
when inserting, at (a,b) check
if (b,a) is '1', if yes.. then there is cycle. (don't insert, or report)
else add ==> mark (a,b) =1 and do the below step
for each col, (b,col_num) if its '1', then mark (a,col_num) to 1.
(it can be easier if it an undirected graph.)
start
========
1000
0100
0010
0001
A->B
1100
0100
0010
0001
C->D
1100
0100
0011
0001
D->B
1100
0100
0011
0101
C->A
1100
0100
1111
0101
when adding B->c, (C,A) is '1', don't insert
space is O(V^2) --> if bit vector is used.. its Log(V).
insertion time = O(V)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/dOhnXq9XGfAJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
