In the depth first formulation, the algorithm looks at each step through all of the neighbors of the current node and for those that have not been assigned to a component yet, assigns them to this component and recurces on them.
In breath first formulation, instead of recursing on new nodes, they are added to a queue.
In breath first scanning formulation, every node has two values : component and visited.
The depth first fomulation is the easiest to code and debug but it can require a large stack. The breath first fomulation is a bit better in memory as the queue is more efficient then the stack. The breath first scanning formulation is much better in memory however it is much slower : Time Complexity of N*N+M, where N is the number of vertices in the graph.
A Small Problem (taken from a book) to Warm Up :
Street Race
Given a directed graph, and a start point and an end point. Find all points p that any path from the start point to the end must travel through p.
M <= 100 and N <= 50
No comments:
Post a Comment