DFS:
graph cycle detection:
detect cycle in a directed graph
have a hash set for current visited nodes, in recursion stack
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
detect cycle in a undirected graph
as long as a node is found visited already and it's not the parent of the current node, then there's a cycle
----------------------------------------------------------
DAG, shortest path algorithms
#1
topological sort the graph, one pass to find the start node and update shortest path to each node
----------------------------------------
Bellmen-Ford
correctness: relax one edge into final stage at each outer iteration
No comments:
Post a Comment