Gain insights into key graph algorithms, including depth-first search, shortest paths, and flow networks. Explore their applications and foundational role in advanced computing disciplines.

This technology-agnostic course will teach you about many classical graph algorithms essential for a well-rounded software engineer. 

You will begin with an introduction to the running-time analysis of algorithms and the representation and structure of graphs. You’ll cover the depth-first search algorithm and its many applications, like detecting cycles, topological sorting, and identifying cut-vertices and strongly connected components. You will then cover algorithms for finding shortest paths and minimum spanning trees. You’ll also learn about the Ford-Fulkerson algorithm and its use in finding a maximum flow and minimum cut in networks. Moreover, you will adapt it to find maximum matchings and minimum vertex covers in bipartite graphs. Finally, you will learn about the Gale-Shapley algorithm for finding stable matchings.

The material in this course serves as a basis for other advanced algorithms, like parallel and distributed algorithms, and has many diverse applications in other computing disciplines.

Mastering Graph Algorithms

# What a waste!

An $n\times n$ matrix requires $n^2$ memory. Imagine a graph on a thousand vertices, with a handful of edges incident on each vertex. In the adjacency matrix, the row for each vertex would contain mostly zeroes except for a smattering of ones. 

That’s wasteful as far as memory is concerned because if we know the neighbors of a vertex, it is easy to infer which of the vertices are not its neighbors. We don’t really need to store a zero against each nonneighbor. 

For instance, the adjacency matrix for the shown graph has $64$ entries in all, but only $14$ are non-zero. 


Learn how to represent a graph using the adjacency lists representation.

Introduction

Review: Asymptotic Notation and Math Prerequisites

Working with Graphs

Depth-First Search and Applications

Prelude: Shortest Paths

Single-source Shortest Paths in Weighted Digraphs

All Pairs Shortest Paths

Minimum Spanning Tree

Flows

Matchings and Vertex Covers

Conclusion

Use Simulated Annealing for the Traveling Salesman Problem

Adjacency List

What a waste!