7. Graphs and Graphing Algorithms¶
Graphs and Graphing Algorithms
- 7.1. Objectives
- 7.2. Vocabulary and Definitions
- 7.3. The Graph Abstract Data Type
- 7.4. An Adjacency Matrix
- 7.5. An Adjacency List
- 7.6. Implementation
- 7.7. The Word Ladder Problem
- 7.8. Building the Word Ladder Graph
- 7.9. Implementing Breadth-First Search
- 7.10. Breadth-First Search Analysis
- 7.11. The Knight’s Tour Problem
- 7.12. Building the Knight’s Tour Graph
- 7.13. Implementing Knight’s Tour
- 7.14. Knight’s Tour Analysis
- 7.15. General Depth-First Search
- 7.16. Depth-First Search Analysis
- 7.17. Topological Sorting
- 7.18. Strongly Connected Components
- 7.19. Shortest Path Problems
- 7.20. Dijkstra’s Algorithm
- 7.21. Analysis of Dijkstra’s Algorithm
- 7.22. Prim’s Spanning Tree Algorithm
- 7.23. Summary
- 7.24. Key Terms
- 7.25. Exercises