The goal of graph search is to find every node that is reachable from a starting node. We don't want to explore anything twice so that we can get O(m+n) running time, linear in the number of edges and vertices.
The generic algorithm for this would be as follows:
Given (graph G, vertex s)
-initially explore s, all other vertices unexplored
-while possible:
-choose an edge (u, v) with u explored and v unexplored
-mark v explored
-halt
At the end, if a node v is explored, then G has a path from s to v.
What gives rise to multiple algorithms of this general sort is in the ambiguity in choosing the next edge.
In Breadth First Search (BFS), we explore the graph in layers. The starting node is in layer x0. Its neighbors are in layer x1. For any node in layer xi, it will take i edges to connecting the starting node to it. BFS is good for computing shortest paths and connected components of an undirected graph. This can be implemented in a First In First Out data structure, such as a Queue.
Depth First Search (DFS), on the other hand, explores aggressively and backtracks only when necessary. It can be used to compute a topological ordering of a directed acyclic graph as well as the connect components in a directed graph. This can be implemented with a Last In First Out data structure such as a Stack.
No comments:
Post a Comment