Wednesday, January 14, 2015

Graphs

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