Breadth-first Finds shortest path Nodes visited earlier cant include g evel 0 Level 1 Level d Level d+1 Assuming each edge is length 1 other paths to g must be at least as long as first found 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 1010 Brian Williams, Spring 03 24 Breadth-first Finds Shortest Path G Level 1 Level d Level 0 Level d+1 G First reached Nodes visited earlier can’t include G Assuming each edge is length 1, other paths to G must be at least as long as first found Brian Williams, Spring 03 25 Cost and Performance b Yes unit lngth d+1 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