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. Key Terms
• 9.25. Discussion Questions
• 9.26. Programming Exercises