Overview

Graphs can be used to represent many problems in computer science, so this section is long, like trees and sorting were.

• Notes:

  • There are 4 basic ways to represent a graph in memory:
    • objects and pointers
    • adjacency matrix
    • adjacency list
    • adjacency map
  • Familiarize yourself with each representation and its pros & cons
  • BFS and DFS - know their computational complexity, their trade offs, and how to implement them in real code
  • When asked a question, look for a graph-based solution first, then move on if none

• Lecture 10 - Graph Data Structures - CSE373 Skiena (video)

• Lecture 11 - Graph Traversal - CSE373 Skiena (video)

• Lecture 12 - Depth First Search - CSE373 Skiena (video)

• Lecture 13 - Minimum Spanning Trees - CSE373 Skiena (video)

• Lecture 14 - Minimum Spanning Trees (con't) - CSE373 Skiena (video)

• Lecture 15 - Graph Algorithms (con't 2) - CSE373 Skiena (video)

• Full Coursera Course:

  • Algorithms on Graphs (video)

• Implement:

  • DFS with adjacency list (recursive)
  • DFS with adjacency list (iterative with stack)
  • DFS with adjacency matrix (recursive)
  • DFS with adjacency matrix (iterative with stack)
  • BFS with adjacency list
  • BFS with adjacency matrix
  • single-source shortest path (Dijkstra)
  • minimum spanning tree
  • DFS-based algorithms (see Aduni videos above):
    • check for cycle (needed for topological sort, since we'll check for cycle before starting)
    • topological sort
    • count connected components in a graph
    • list strongly connected components
    • check for bipartite graph

• Weighted graphs - UC Berkeley CS 61B (video)

• Greedy Algorithms: Minimum Spanning Tree - MIT 6.046 (video)

• Strongly Connected Components Kosaraju's Algorithm Graph Algorithm - Youtube (video)