12 Graphs 2
ACM Body of Knowledge
AL/Fundamental Data Structures and Algorithms
Topics:
[Core-Tier1]
Graphs and graph algorithms
Depth- and breadth-first traversals
[Core-Tier2]
Graphs and graph algorithms
Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
Minimum spanning tree (Prim’s and Kruskal’s algorithms)
Learning Outcomes:
[Core-Tier1]
8. Solve problems using fundamental graph algorithms, including depth-first and breadth-first search. [Usage]
[Core-Tier2]
11. Solve problems using graph algorithms, including single-source and all-pairs shortest paths, and at least one minimum spanning tree algorithm. [Usage]
Lesson
Key Resources
Textbook
Chapter 8. Graphs and Their Applications.
When reading textbooks, use the SQ3R technique.
Topics
Depth- and breadth-first traversals
Graph Traversals - Breadth First and Depth First video (10:08)
Depth first uses a stack
Breadth first uses a queue
Shortest-path algorithms
Shortest path from one node to all nodes
Shortest path between all pairs of vertices, negative edges allowed
Shortest path from one node to all nodes, negative edges allowed
Minimum spanning tree