Module 6: Graphs

Welcome to Module 6

Trees are a hierarchical data structure in which connectivity is directed from parent to child nodes. A more general data structure is a graph in which any vertex (node) may have one or more connections to any other node. In a tree, edges (connections between vertices) may be directed (going only one way) or undirected (bidirectional). Because of flexible nature of graphs, which may contain cycles, additional algorithms are available for traversing graphs and computing using data associated with its vertices and edges. Sparse graphs (with relatively few connections) can easily be represented with adjacency matrices, though adjacency lists may be more efficient for highly-connected graphs. Due to the possible dense connectivity in a graph, some algorithm make locally optimal choices at each step.

Module Learning Outcomes

Upon successful completion of this module, you will be able to:

  1. Represent a graph using adjacency lists or adjacency matrix (CLO 5).
  2. Traverse a graph in various orders (CLO 5).
  3. Identify graph algorithms that are greedy (CLO 5).

(CLO = Course Learning Outcome)

To Do

Please read/watch all of the module learning materials (readings, presentations, videos, etc.) and complete all assignments/assessments listed below. If you have questions, please contact the course instructor or ask in the Questions About This Course forum.

Readings and Presentations:

  • Read Chapter 20: Graph Representations and Elementary Algorithms
  • Read Section 20.4: Topological Sort
  • Read Chapter 21: Minimum Spanning Trees
  • Read Chapter 22: Single-Source Shortest Path
  • Read Chapter 15: Greedy Algorithms

Assignments/Assessments:

  • Final Project Proposal
  • Final Project Code

Click the Next ▶ button to continue.