Graphs (Part 2)

This lecture introduces directed graphs and explores how graph algorithms change when edge direction matters. We examine reachability, strong connectivity, strongly connected components and directed acyclic graphs (DAGs). We also look at one of the most useful algorithms in graph theory: topological ordering. Topics covered include: Directed graphs and real-world applications Directed reachability and shortest paths Strong connectivity Strongly connected components Testing strong connectivity with BFS Directed acyclic graphs (DAGs) Topological orderings Efficient topological sorting in O(m+n) time Along the way, we connect graph theory to real-world applications like web search, road networks, software dependencies, course prerequisites, citation networks and other systems where relationships have a natural direction.