Week 3: Graph Data Structures and Algorithms
Week 3
Nerds You Should Know
Graph Definitions
Graphs
Properties of Graphs
Graph Terminology
Graph Data Structures
Graph Representations
Array-of-edges Representation
Cost Analysis
Adjacency Matrix Representation
Adjacency List Representation
Comparison of Graph Representations
Graph Abstract Data Type
Graph ADT
Graph ADT (Array of Edges)
Graph ADT (Adjacency Matrix)
Graph ADT (Adjacency List)
Graph Traversal
Finding a Path
Depth-first Search
Breadth-first Search
Other DFS Examples
Computing Connected Components
Hamiltonian and Euler Paths
Hamiltonian Path and Circuit
Euler Path and Circuit
Graph Algorithms
Mid-term Test
Nerdy Things You Should Know
Directed Graphs
Directed Graphs (Digraphs)
Digraph Applications
Digraph Representation
Reachability
Transitive Closure
Digraph Traversal
Example: Web Crawling
Weighted Graphs
Weighted Graphs
Weighted Graph Representation
Minimum Spanning Trees
Minimum Spanning Trees
Kruskal's Algorithm
Prim's Algorithm
Sidetrack: Priority Queues
Other MST Algorithms
Shortest Path
Shortest Path
Single-source Shortest Path (SSSP)
Edge Relaxation
Dijkstra's Algorithm
All-pair Shortest Path (APSP)
Floyd's Algorithm
Network Flow
Flow Networks
Augmenting Paths
Residual Network
Edmonds-Karp Algorithm
Digraph Applications
PageRank
Summary
Produced: 20 Jan 2025
![[index]](icon/up.gif){kind=icon}