Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 363-375 (Section 9.3)

(2nd) pages 558-570 (Section 12.3)

Additional material

Graph traversals in pseudocode: PostScript and PDF.

To make writing some of the graph algorithms in Java easier, the interface Vertex has been extended to DecorableVertex and the interface Edge has been extended to DecorableEdge. 

/**
 * Vertices which can be marked visited or unvisited.
 */
public interface DecorableVertex extends Vertex
{
    /**
     * Marks this vertex visited.
     */
    public void visit();

    /**
     * Marks this vertex unvisited.
     */
    public void unvisit();

    /**
     * Tests if this vertex is visited.
     *
     * @return true if this vertex is visited, false otherwise.
     */
    public boolean isVisited();
}

/**
 * Edges which can be marked visited or unvisited.
 */
public interface DecorableEdge extends Edge
{
    /**
     * Marks this edge visited.
     */
    public void visit();

    /**
     * Marks this edge unvisited.
     */
    public void unvisit();

    /**
     * Tests if this edge is visited.
     *
     * @return true if this edge is visited, false otherwise.
     */
    public boolean isVisited();
}

Question

Give an algorithm which computes the number of connected components of a simple undirected graph.