Module 10: Graphs

CMPS 260: Data Structures

Introduction

Graphs are related to trees but are more general as they allow for loops. This means that there can be multiple paths between two nodes. Many problems can be represented with graphs, for example, finding the shortest route between two locations on a map. Graphs can be implemented in multiple ways that result in different trade-offs, and we will see what they are. Just like with trees, we will look how to traverse graphs with both breadth first and depth first search. Finally, we will look at Dijkstra’s algorithm that finds the shortest path between two points and Prim’s algorithm that finds a minimum spanning tree. A minimum spanning tree connects all the nodes in a graph in the most efficient way.

Module Objectives

  • Define graph terminology
  • Describe a graph
  • Implement creating and using the graphs
  • Implement graph traversals
  • Implement shortest path algorithms
  • Describe minimum spanning trees
  • Implement minimum spanning trees

Learning Resources

  • Module 10 Readings: Chapter 9 (skip ECMAScript and Floyd-Warshall’s and Kruskal’s algorithm sections)
  • Module 10 Slides: Chapter 9

Learning Activities

  • Module 10 Assignment

For Further Study

Leave a Reply

Your email address will not be published. Required fields are marked *