[prev] 188 [next]

Summary

  • Graph terminology
    • vertices, edges, vertex degree, connected graph, tree
    • path, cycle, clique, spanning tree, spanning forest
  • Graph representations
    • array of edges
    • adjacency matrix
    • adjacency lists
  • Graph traversal
    • depth-first search (DFS)
    • breadth-first search (BFS)
    • cycle check, connected components
    • Hamiltonian paths/circuits, Euler paths/circuits
  • Digraphs, weighted graphs: representations, applications
  • Reachability
    • Warshall
  • Minimum Spanning Tree (MST)
    • Kruskal, Prim
  • Shortest path problems
    • Dijkstra (single source SPP)
    • Floyd (all-pair SPP)
  • Flow networks
    • Edmonds-Karp (maximum flow)

  • Suggested reading (Sedgewick):
    • graph representations … Ch. 17.1-17.5
    • Hamiltonian/Euler paths … Ch. 17.7
    • graph search … Ch. 18.1-18.3, 18.7
    • digraphs … Ch. 19.1-19.3
    • weighted graphs … Ch. 20-20.1
    • MST … Ch. 20.2-20.4
    • SSP … Ch. 21-21.3
    • network flows … Ch. 22.1-22.2