Summary.ptx

<section xml:id="graphs_summary">
        <title>Summary</title>
        <p>In this chapter we have looked at the graph abstract data type, and some
            implementations of a graph. A graph enables us to solve many problems
            provided we can transform the original problem into something that can
            be represented by a graph. In particular, we have seen that graphs are
            useful to solve problems in the following general areas.</p>
        <p><ul>
            <li>
                <p>Breadth first search for finding the unweighted shortest path.</p>
            </li>
            <li>
                <p>Dijkstra's algorithm for weighted shortest path.</p>
            </li>
            <li>
                <p>Depth first search for graph exploration.</p>
            </li>
            <li>
                <p>Strongly connected components for simplifying a graph.</p>
            </li>
            <li>
                <p>Topological sort for ordering tasks.</p>
            </li>
            <li>
                <p>Minimum weight spanning trees for broadcasting messages.</p>
            </li>
        </ul></p>
        <conclusion><p>
            <!-- extra space before the progress bar -->
        </p></conclusion>
    </section>