Course section

Graphs & Applications

Model networks, routes, dependencies, and connectivity using traversal, shortest-path, MST, and disjoint-set algorithms.

10 topics

Graph Fundamentals

Graphs consist of vertices and edges and may be directed, undirected, weighted, cyclic, connected, or sparse.

Adjacency lists use O(V+E) space and suit sparse graphs; matrices use O(V²) space and give O(1) edge tests.

BFS explores vertices by increasing unweighted distance using a queue and produces shortest paths in edge count.

DFS follows one path deeply before backtracking and supports cycle detection, ordering, components, and structural analysis.

Dijkstra finalises minimum distances from one source by repeatedly extracting the closest unsettled vertex.

Floyd–Warshall computes all-pairs shortest paths by progressively allowing each vertex as an intermediate.

DSU maintains a changing partition of elements and answers whether two elements belong to the same component.

Prim grows one minimum spanning tree by repeatedly adding the cheapest edge crossing from the tree to an outside vertex.

Kruskal considers edges from lightest to heaviest and uses DSU to add only edges that connect different components.

Graph models support smart grids, recycling networks, transit planning, waste collection, and resilient infrastructure.