CS303: Algorithms, Topic: Unit 6: Graph Theory and Graph Algorithms

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
  - University of California, San Diego: Edward A. Bender and S. G. Williamson's "Basic Concepts in Graph Theory" URL
    Read this chapter for an introduction to graph theory.
- 6.2: Paths in Graphs
  - University of California, Berkeley: S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's "Paths in Graphs" URL
    Read Chapter 4 from S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
- 6.3: Graph Data Structures
  - PatrickJMT: "Graph Theory - An Introduction" Page
    Watch this video to learn about data structures used in graph algorithms.
- 6.4: Graph Theory Algorithms - Part I
  - Massachusetts Institute of Technology: Dr. Charles E. Leiserson's "Greedy Algorithms, Minimum Spanning Trees" Page
    Watch this video to learn about graph theory concepts, greedy algorithms, and minimum spanning trees.
- 6.5: Graph Theory Algorithms - Part II
  - Massachusetts Institute of Technology: Dr. Charles E. Leiserson's "Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search" Page
    Watch this video to learn about shortest path problems.
  - Graph Theory and Graph Algorithms Assignment URL
    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.