(Note: This page and the applets it contains are largely the work of Renaud Waldura. I'm hosting them here because I think they're a neat way to demonstrate graph algorithms.)
You keep reading about the famous graph algorithms, BFS, DFS, Shortest Path First, etc.  used as well for network routing as for games theory  without ever really understanding them? Now watch them run live on this web page!
Background
I just loved the sorting algorithms demo applets shipped with the JDK: it is so intuitive, you really are immediately convinced that the QuickSort is in fact better than any other common sorting algorithm.
Having played a bit with Sun's wonderful browser, I was looking for something easy and funny to code in their new Java language. I could have implemented other sorting algorithms such as ShellSort and so reuse James Gosling's framework, but this wouldn't have been any fun. After the sorting algorithms, the next step had to be of course... the graph algorithms.
So here they are, the wellknown graph algorithms, implemented in the objectoriented, multithreaded, distributed, secure, portable, Java language.
Breadth First Search
Search a graph (directed or not) in breadth first; this is done by using a queue where the found vertices are stored.
Here is a brief description of the BFS algorithm:
bfs (Graph G) { all vertices of G are first painted white the graph root is painted gray and put in a queue while the queue is not empty { a vertex u is removed from the queue for all white successors v of u { v is painted gray v is added to the queue } u is painted black } }
And now watch it run  click the applet to start/stop the search.
Have a look at the Java code; it happens to be pretty clean ! :).
Depth First Search
Basically the idea is the same, but we are now using a stack instead of a queue. With recursion of course, so the stack management is all done by Java.
Here is a brief description of the DFS algorithm:
dfsvisit (Graph G, Vertex u) { the vertex u is painted gray for all white successors v of u { dfsvisit(G, v) } u is painted black } dfs (Graph G) { all vertices of G are first painted white dfsvisit(G, root of G) }Watch it run with this applet:
Have a look at the corresponding Java code; it happens to be pretty clean ! :)
Comments
DFS seems really cleaner than BFS: it doesn't make use of an external data structure (a queue) because it is recursive, and therefore is shorter too. But those two search algorithms really address different areas: good examples of using the BFS algorithm instead of DFS are the Web robots: a Depth First Search performed on the World Wide Web (a pretty graph, isn't it ?) would very quickly overload a given web server by the ever growing number of requests sent to it; a Breadth First Search is preferred, dispatching the requests on many servers at a time.
The Applet
You can download the whole package under the usual academic license and copyright (please do distribute unmodified, I do not make any warranty of any kind, it is all © Renaud Waldura 1995, etc, etc).
Here is a little documentation about the applet attributes:
DIRECTED="TRUE""FALSE"
 Is the graph directed ? When directed, the graph is drawn with pseudo "arrows" with edges instead of straight lines.
GRAPH="
url"

The graph structure is stored in the file referenced by url. Its
layout is quite strict, it has to follow these rules:
 the number of vertices first,
 then the n vertice names,
 then a "bit" matrix with exactly n rows and n
columns; a '
1
' character on row i and column j indicates an edge between vertex i and vertex j.
Note that this kind of representation is implicitely directed: to create a nondirected graph, you have to make sure that for all vertices, matrix[i][j] == '1' => matrix[j][i] == '1' (i.e. every edge from vertex i to j is also an edge from j to i).
ALGORITHM="DFS""BFS"
 The name of the algorithm used when searching; currently only BFS and DFS are implemented.
SPEED="
s"
 The searching speed; s > 10 is too fast to see anything.
VERTICES
, DIRECTED
,
and GRAPH
are mandatory, since they describe the graph
itself; an exception is thrown whenever any of these is not specified
(the applet displays the exception message). The ALGORITHM
attribute defaults to DFS
and SPEED
to 5.
For the time being, the correct width and height for the applet (showing the whole graph with a nice border around it) have to be found by testing various values.