• 8.2: Graphs

    • Graphs File

      In computer science, the term "graph" refers to a set of vertices (points or nodes) and of edges (lines) that connect the vertices. The creation and traversal of graphs is an important topic when learning to solve complex problems that involve numerous relationships. Read this chapter for an excellent discussion on graphs and graph traversal.

    • Graphs and Network Flows File

      Review these slides, which discuss different graph representations and the efficiency of various representations.

    • Finding Non-Cyclical Paths between Arbitrary Pairs of Nodes Page

      This article explains how to find all non-cyclical paths in a graph. Creating a traversal that visits nodes only once while still reaching the goal is a part of creating efficient solutions.

    • 8.2.1: Graph Searches

      • C Program for Depth-First Search in a Graph Page

        There are many ways to traverse a graph; this article focuses on depth-first. This approach seeks a solution by going to the nodes furthest from the starting point.

      • Breadth-First Search Page

        Another way to traverse a graph is to seek solutions starting at the closest nodes. This article explains how that is accomplished.

    • 8.2.2: Finding Lowest-Cost Paths

      • Dijkstra's Algorithm Page

        Getting from one node in a graph to another while expending the least cost is important in many domains. This article discusses Dijkstra's algorithm and its implementation.

      • Bellman's Algorithm Page

        An alternative approach to path finding is Bellman's algorithm. This page explains that approach and its implementation.

    • 8.2.3: Finding a Minimum Spanning Tree

      • Minimum Spanning Trees – Kruskal's Algorithm Page

        For a graph's vertices (nodes) and weighted edges connecting the vertices, a minimum spanning tree contains only the minimum number of edges connecting all vertices while having the minimum total weight when compared to all sets of edges that connect all vertices. Note that there may be more than one set of edges that has the minimum sum of weights. This article explains Kruskal's method of obtaining a minimum spanning tree.

      • Minimum Spanning Trees – Prim's Algorithm Page

        Prim created another popular approach to creating a minimum spanning tree. Since there is an infinity of potential application requirements and situations, there is never any one best approach in computer science, regardless of any academic snobbery you may encounter. Your ability to solve problems depends on your creativity, objectivity, and flexibility. Do not be trapped by an attempt to force-fit someone's favorite tool to all situations.