9846

Graph Searching: Breadth First and Depth First

In a connected graph, you can always reach all nodes (or vertices) starting from any given node (called the root) by traversing edges. When traversing an edge from one node to another, the first is typically referred to as the "parent", and the second as the "child". Two commonly used graph traversal methods are called "breadth first" and "depth first".

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

The root node is the one that is initially green. As the search encounters new nodes, they become green as well. In a breadth-first traversal, you start at the root and visit all of its children in some order. Each child is marked as having been visited. Next, a child is selected and all of its children (that is, grandchildren of the root) are visited, except those, if any, that are marked. This is repeated for the other children of the root. When that is finished, a grandchild is selected, etc. The traversal terminates when all nodes have been marked.
A depth-first search is done by visiting a child node (and marking it), from there selecting a grandchild, visiting and marking it, etc. Each such branch of the search concludes when there is no unmarked child to search. At that stage, you return to the parent of the last child visited, select another unvisited child, traverse to that child, and repeat. If there is no such unvisited child, you continue back up the "parent chain" until one is found with an unvisited child, whereupon you recursively visit that child in depth-first fashion.
In practice, depth-first searches are often implemented with a stack data structure. This allows the program to keep a record of children yet to be visited, in LIFO (last in, first out) order. Breadth-first searches can be accomplished using a queue structure to enforce their FIFO (first in, first out) nature.
Note that once completed, a search gives a "spanning tree", that is, a tree emanating from the root node and hitting all other nodes.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+