Unit 6: Graph Theory and Graph Algorithms
In this unit, you will learn about graph theory and graph-based algorithms. Graphs are a pervasive data structure in computer science and algorithms working with them are fundamental to the subject. We will review basic concepts of graph and associated terminology. We will also see how we can represent graphs in computer algorithms and use these representations to solve some common problems, such as finding the shortest paths between any two places. You will also get an introduction to trees and a minimum weight spanning tree algorithm.
Completing this unit should take you approximately 10 hours.
Upon successful completion of this unit, you will be able to:
- Describe concepts in graph theory, graph-based algorithms, and their analysis.
- Describe tree-based algorithms and their analysis.
6.1: Introduction to Graph Theory
Read this chapter for an introduction to graph theory.
6.2: Paths in Graphs
Read Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
6.3: Graph Data Structures
Watch this video to learn about data structures used in graph algorithms.
6.4: Graph Theory Algorithms - Part I
Watch this video to learn about graph theory concepts, greedy algorithms, and minimum spanning trees.
6.5: Graph Theory Algorithms - Part II
Watch this video to learn about shortest path problems.
Complete all questions in this assignment. There is one question on the breadth-first search implementation and one on depth-first search implementation. You can check your answers against the Answer Key.