This document and the software it presents are outdated, and kept online for reference purposes only. You may nonetheless be interested in some more recent material the author has published about graph algorithms in Java.

Graph Algorithms

1. Welcome !
   • Background
   • Future Directions
2. Search algorithms
   • Breadth First Search
   • Depth First Search
   • Comments on Search algorithms
   • The Applet
3. Shortest Path algorithms
4. Spanning Trees algorithms
5. A good library implementing graph algorithms

You keep reading about the famous graph algorithms, BFS, DFS, Shortest Path First, etc. -- used from network routing to game theory -- without ever really understanding them ?
Now, with the help of the new HotJava browser, watch them run live on this web page !

I just loved the sorting algorithms demo found in the HotJava alpha 2 release: it is so intuitive, one is immediately convinced 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 fun to code in their new Java language. I could have implemented other sorting algorithms such as ShellSort and thus re-use James Gosling's framework, but this wouldn't have been any fun. After sorting algorithms, the next step had to be of course... graph algorithms.

So here they are, the well-known graph algorithms, implemented in the new object-oriented, multithreaded, distributed, secure, portable, ... Java language!!!

I would like to extend this page with other algorithms, such as Shortest Path Search (Dijkstra and Bellmann-Ford), Spanning Trees (Kruskal and Prim), etc., but of course I have time constraints... Maybe next week !

If you're interested in contributing to the creation of a Graph Algorithms Site, please mail me!

Search a graph (directed or not) in breadth first; this is done by using a queue where the vertices found 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.

You may want to have a look at the corresponding Java code.

The general idea is the same, but we now use 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)
    }

You may want to have a look at the corresponding Java code.

DFS seems cleaner than BFS: recursive, it doesn't make use of an external data structure (a queue), and is shorter too. But it is important to realize these two algorithms address very different needs. An example of BFS usage, instead of DFS, is to implement a Web robot; a Depth First Search performed on the World Wide Web (a neat graph, isn't it?) would quickly overload any given web server with an ever growing number of requests. Therefore a Breadth First Search is preferred, since it dispatches requests to many servers at a time.

You can download the whole package under the usual academic license -- no warranties of any kind, please give me credit, I'd like to hear about your modifications, and it is all copyright © Renaud Waldura 1995, etc.

Here is a little documentation about the applet attributes:

VERTICES="n"

n is the number of vertices in the graph; it must match the graph definition file described below.

DIRECTED="TRUE"|"FALSE"

Is the graph directed? When directed, the graph is drawn with pseudo "arrows" for edges instead of straight lines.

GRAPH="url"

The graph structure is stored in the file referenced by url. Its layout is quite strict, and follows these rules:

• the n vertices names first,
• next a boolean 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 is defined the graph displayed by the applets on this page.
Note that this representation is implicitely directed: to create a non-directed graph, you must ensure 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.

For the time being, the correct width and height of the applet (showing the whole graph with a nice border around it) have to be found by trial and error.

Of course, I welcome any question, remark, criticism, ...