Graph Algorithms (original) (raw)

(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 re-use 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 well-known graph algorithms, implemented in the object-oriented, 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:

dfs-visit (Graph G, Vertex u) {
    the vertex u is painted gray

    for all white successors v of u {
        dfs-visit(G, v)
    }

    u is painted black
}

dfs (Graph G) {
    all vertices of G are first painted white

    dfs-visit(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 packageunder 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. See the example definition file where the graph searched by the applets presented here is defined.
  Note that this kind of representation is implicitely directed: to create a non-directed 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.

The attributes 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.