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

Suppose that you're running BFS on the graph (left), and the breadth-first tree constructed thus far is shown on the right. What is the next vertex to be visited?
<center><img src="/udata/DE0l5OlnkWB/sh-question1-bfs-shortest.svg" width="60%"></img>
</center>

Suppose that you’re running BFS on the graph (left), and the breadth-first tree constructed thus far is shown on the right. What is the next vertex to be visited?
<center><img src="/udata/DE0l5OlnkWB/sh-question1-bfs-shortest.svg" width="60%"></img>
</center>

The shortest-paths tree rooted at which vertex has the smallest height?

<center>
<img src="/udata/GDv25yDDgy9/sh-question2-bfs-shortest.svg" width="45%"></img>
</center>

The shortest-paths tree rooted at which vertex has the smallest height?
<center>
<img src="/udata/GDv25yDDgy9/sh-question2-bfs-shortest.svg" width="45%"></img>
</center>

**(Select all that apply.)** BFS can be used for computing shortest paths in which graphs? 


(Select all that apply.) BFS can be used for computing shortest paths in which graphs?

Test your understanding of BFS and shortest paths in unweighted graphs.

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

Quiz: BFS and Shortest Paths

Multiple choice questions