Explore the basics of graph theory, learn to represent graphs in C++, and master essential algorithms like DFS and Dijkstra to solve complex optimization problems, including matching and network flow.

Graph algorithms are the core of many real-world applications of computer science,  such as automotive navigation or routing in computer networks. They’re also a common subject in coding interviews at top-tier tech companies.
 
In this course, we’ll learn about the basic concepts of graph theory and how to represent graphs as data structures in code. We’ll study essential graph algorithms such as depth-first search or Dijkstra's algorithm to traverse graphs and find shortest paths. Finally, we’ll learn to solve more complex optimization problems on graphs, such as matching and network flow problems.

Learn Graph Algorithms in C++

DFS is used to compute paths in the residual network.

BFS is used to compute paths in the residual network.

The adjacency matrix representation is used for the flow network.

The adjacency list representation is used for the flow network.

What is the key ingredient of the Edmonds-Karp variant of the Ford-Fulkerson method?

What is the key ingredient of the Edmonds-Karp variant of the Ford-Fulkerson method?

The value of $f^*$ is at most the highest capacity of an edge in the network.

There is no other flow $f'$ with $v(f') = v(f^*)$.

The value $v(f^*)$ is at most the sum of the capacity of all incoming edges of $t$.

The value $v(f^*)$ is at most the sum of the capacity of all outgoing edges of $s$.

Let $f^*$ be a maximum flow from $s$ to $t$. Which of the following statements are true? Select all that apply.

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>f</mi><mo>∗</mo></msup></mrow><annotation encoding="application/x-tex">f^*</annotation></semantics></math>f∗ be a maximum flow from <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math>s to <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t. Which of the following statements are true? Select all that apply.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Quiz: Flow Problems