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++

# Bipartite graphs

In this exercise, we'll take a look at a special kind of graph called **bipartite graphs**. An undirected graph $G$ is called bipartite if we can split its set of vertices up into two partitions (let's call them the "left" and the "right" vertices), such that all edges connect a left vertex to a right vertex. In other words, there are no edges between two left vertices or between two right vertices.

The following illustration shows an example of a bipartite graph. The left vertices are marked in red and the right vertices are marked in blue.

Apply graph traversal algorithms to check whether a graph is bipartite.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Challenge: Bipartite Graph Check

Bipartite graphs