Cost and performance Which is better, depth-first or breadth-first? Worst Worst Shortest Guaranteed to Path? find path? Depth-first 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 Q 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 Q Brian willams, Spring (37 Brian Williams, Spring 03 18 Cost and Performance Breadth-first 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 Which is better, depth-first or breadth-first? S D A B C G C G D C G C S B G A D Brian Williams, Spring 03 19 Cost and Performance Breadth-first b b*m No Yes for finite graph Depth-first m Guaranteed to find path? Shortest Path? Worst Space Worst Time Search Method S D A B C G C G D C G Worst case time is proportional to number of nodes visited Worst case space is proportional to maximal length of Q Which is better, depth-first or breadth-first? C S B G A D