This applet demonstrates four graph algorithms: Any Path Does a depth first search from the selected start vertex to the selected end vertex. With each click on "Next," the algorithm selects the first unvisited vertex on the adjacency list of the last visited vertex. When there are no unvisited vertices, it backs up. It stops when it reaches the end vertex. Cheapest Path Follows Dijkstra's shortest path algorithm. It is a greedy algorithm. At each step, it looks for an unvisited vertex it can get to for less than (or equal to) the cost of all other unvisited vertices. Minimal Cost Spanning Tree - Fringe Method (Prim's Algorithm) Grows a tree T that starts as just the selected start vertex. At each step, it looks for a vertex in G but not in T which has the lowest weight edge connecting to a node in T. If it succeeds, it adds that vertex and edge to T. When it can find no more vertices to add, T will be a minimal spanning tree for the connected component of T. Minimal Cost Spanning Tree - Kruskal's Algorithm Finds a minimal spanning forest for the graph, i.e. a minimal spanning tree for each connected component of the graph. Starts with a forest where each vertex is a separate tree and the set S of all edges. At each step, it removes the minimal weight edge from S and if that edge connectes two trees in the forest, the two trees are combined via that edge. Otherwise the edge is discarded. The algorithm terminates when there are no edges left in S or there is only one tree in the forest. -- Harriet Fell source: graphit (not really fit for viewing) extends BufferedApplet (Ken Perlin)

Click once on the applet to activate it. Then click on: one of the six graphs at the bottom of the window to select it. an algorithm to select it. a vertex or vertices if asked to. the "Next" box to step through the algorithm