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
|