This week's book giveaway is in the OO, Patterns, UML and Refactoring forum.
We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line!
See this thread for details.
The moose likes General Computing and the fly likes Graphs: Breadth First or Depth First? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

JavaRanch » Java Forums » Engineering » General Computing
Bookmark "Graphs: Breadth First or Depth First?" Watch "Graphs: Breadth First or Depth First?" New topic

Graphs: Breadth First or Depth First?

Clarice Doe

Joined: Dec 24, 2004
Posts: 21
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.

Eric Pascarello

Joined: Nov 08, 2001
Posts: 15385
Moving to Gen. Computing...

I’ve looked at a lot of different solutions, and in my humble opinion Aspose is the way to go. Here’s the link:
subject: Graphs: Breadth First or Depth First?
It's not a secret anymore!