BFS
Breadth First Search
Search Order
1
2 3
4 5 6 7
|
O( | V | + | E | ) = O(bd) |
|
|
O( | V | ) = O(bd) |
1. First node in Queue.
2. If Queue is empty, it will stop.
3. If Queue's first element is what we looking for, it will stop.
4. De queue in Queue and En queue all the children.
5.Go back to 2.
DFS
Depth First Search
Search Order
1
2 5
3 4 6 7
1. First node q into Queue.
2. If Queue is empty, return Fail.
3. If fist item in Queue is what we looking for, then stop here.
4. Dequeue in Queue, if it has children, We en queue that children to front.
5. Go back to 1
|
O( | V | + | E | ) for explicit graphs traversed without repetition, O(bd) for implicit graphs with branching factor b searched to depth d |
|
|
O( | V | ) if entire graph is traversed without repetition, O(longest path length searched) for implicit graphs without elimination of duplicate nodes |