CS201: Elementary Data Structures

8.2: Graphs

• Virginia Tech: Clifford Shaffer's "Data Structures and Algorithm Analysis: 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.
  

• Lehigh University: Ted Ralphs' "Graphs and Network Flows" File

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

• CodeProject: "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

  • The Daily Programmer: "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.
    

  • The Daily Programmer: "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

  • The Daily Programmer: "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.
    

  • The Daily Programmer: "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

  • York College of Pennsylvania: David S. Babcock's "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.
    

  • York College of Pennsylvania: David S. Babcock's "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.