[prev] 110 [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

  • 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