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
- Read more about graphs on Wikipedia
- Read more about Dijkstra’s algorithm on Wikipedia
- Read more about Prim’s algorithm on Wikipedia
- Read more about minimum spanning trees on Wikipedia