8. Graphs and Graph Algorithms¶
Graphs and Graph Algorithms
- 8.1. Objectives
- 8.2. Vocabulary and Definitions
- 8.3. The Graph Abstract Data Type
- 8.4. An Adjacency Matrix
- 8.5. An Adjacency List
- 8.6. Implementation
- 8.7. The Word Ladder Problem
- 8.8. Building the Word Ladder Graph
- 8.9. Implementing Breadth First Search
- 8.10. Breadth First Search Analysis
- 8.11. The Knight’s Tour Problem
- 8.12. Building the Knight’s Tour Graph
- 8.13. Implementing Knight’s Tour
- 8.14. Knight’s Tour Analysis
- 8.15. General Depth First Search
- 8.16. Depth First Search Analysis
- 8.17. Topological Sorting
- 8.18. Strongly Connected Components
- 8.19. Shortest Path Problems
- 8.20. Dijkstra’s Algorithm
- 8.21. Analysis of Dijkstra’s Algorithm
- 8.22. Prim’s Spanning Tree Algorithm
- 8.23. Summary
- 8.24. Key Terms
- 8.25. Discussion Questions
- 8.26. Programming Exercises