9. Graphs and Graph Algorithms¶
Graphs and Graph Algorithms
- 9.1. Objectives
- 9.2. Vocabulary and Definitions
- 9.3. The Graph Abstract Data Type
- 9.4. An Adjacency Matrix
- 9.5. An Adjacency List
- 9.6. Implementation
- 9.7. The Word Ladder Problem
- 9.8. Building the Word Ladder Graph
- 9.9. Implementing Breadth First Search
- 9.10. Breadth First Search Analysis
- 9.11. The Knight’s Tour Problem
- 9.12. Building the Knight’s Tour Graph
- 9.13. Implementing Knight’s Tour
- 9.14. Knight’s Tour Analysis
- 9.15. General Depth First Search
- 9.16. Depth First Search Analysis
- 9.17. Topological Sorting
- 9.18. Strongly Connected Components
- 9.19. Shortest Path Problems
- 9.20. Dijkstra’s Algorithm
- 9.21. Analysis of Dijkstra’s Algorithm
- 9.22. Prim’s Spanning Tree Algorithm
- 9.23. Summary
- 9.24. Discussion Questions
- 9.25. Programming Exercises
- 9.26. Glossary
- 9.27. Matching