Worst case time for Breadth-first Worst case time T is proportional to number of nodes visited Level 1 b Level d Level d+1 b+1-b Tbs=[b+l+ bd+.b+1-b]cbts Sian willams, Spring o3 Cost and performance Which is better, depth-first or breadth-first? (D G Method Time Space Path? find path? b"m Yes for finite graph Breadth-first Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q8 Brian Williams, Spring 03 20 Worst Case Time for Breadth-first Worst case time T is proportional to number of nodes visited Level 1 Level d Level 0 Tbfs = [bd+1 + bd + … b + 1 - b]*cbfs = O(bd+1) Level d+1 b bd+1- b . . . 1 bd Brian Williams, Spring 03 21 Cost and Performance b Breadth-first d+1 b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q S D A B C G C G D C G Which is better, depth-first or breadth-first? C S B G A D