Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Graphs: Breadth First or Depth First?

 
Clarice Doe
Greenhorn
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For traversing a graph, which is the better way - Breadth First / Depth First? Or is it something related to the problem we are trying to solve?
Can someone give few example scenarios where these different strategies are suitable?

Apart from some general scenario, I have a specific example.

Assume there is a graph representing an airline network (where vertices represents the airports and the edges represents the flight paths). If I'm interested to do the following tasks on that graph, which is better - Depth First or Breadth First?

a) To find different possible routes between a pair of cities
b) To find the distance of route between some cities.
c) To find the shortest path between a pair of cities.

Thanks
 
Eric Pascarello
author
Rancher
Posts: 15385
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moving to Gen. Computing...

Eric
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic