algorithm - Time complexity of finding whether graph has a unique topological order -
i have algorithm finding whether directed graph has unique topological order
- initialise list l
- find vertex v sink in graph (sink = vertex not going ordered edges)
- from graph remove edges going v , vertex v
- add v l
- if there vertices left in graph go step number 2
at end have topological order of vertices in l. if can choose more 1 vertex in step number 2 topological order not unique. if got stuck in of steps before graph empty means graph has no topological order @ all.
i assumed time complexity of algorithm o(n), n number of vertices in graph apparently not right.
let m number of edges, , n number of vertices. naive implementation of algorithm o(nm). if implement step 2 iterating on set of edges o(m) iteration within loop executed n times.
however, can in time complexity o(n+m) follows. assume vertex stored integer , edge stored pair of integers tail , head.
step a
in addition l, initialise following
(a) array a 1 slot each vertex. array should store each vertex i list of vertices pointing towards i.
(b) stack s of vertices sinks (so can removed).
(c) array b, again 1 slot each vertex. array should store each vertex i number of edges point away i. when number drops zero, corresponding vertex must sink can added s.
step b
start iterating on set of edges. each edge e: -> j increment b[i] 1 , add e list a[j]. iteration o(m).
step c
iterate on array b , if b[i] == 0, add i stack s. o(m).
step d
step d while loop
while (s not empty) { remove first sink i s , add l. because have list a[i] know edges point i. each 1 of these edges e: j-> i remove edge subtracting 1 b[j]. if value of b[j] has dropped zero, add j s
}. at end of step d sinks have been removed. step d o(n+m) because each vertex removed @ once, , each edge read @ once.