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

The following code snippet contains an implementation of a **Disjoint Set Union** data structure as it’s used in the [Implementation of Kruskal's algorithm](https://www.educative.io/courses/graph-algorithms-coding-interviews-c-plus-plus/kruskals-algorithm). 

#include <vector>
#include <numeric>
using namespace std;

class DisjointSetUnion {
private:
    vector<int> parents;
    vector<int> ranks;
public:
    DisjointSetUnion(int numberOfSets) {
        this->parents = vector<int>(numberOfSets);
        this->ranks = vector<int>(numberOfSets);
        // every elements starts as its own parent -- and representative
        iota(this->parents.begin(), this->parents.end(), 0);
    }

    int find(int u) {
        // find the root
        int root = u;
        while (this->parents[root] != root) { root = this->parents[root]; }
        // compress paths
        while (this->parents[u] != root) {
            int tmp = this->parents[u];
            this->parents[u] = root;
            u = tmp;
        }
        return root;
    }

    void unite(int u, int v) {
        u = this->find(u);
        v = this->find(v);
        // u and v are already in the same set
        if (u == v) { return; }

        // union by rank -> the root with greater rank becomes the new root
        if (this->ranks[u] == this->ranks[v]) {
            this->parents[u] = v;
            this->ranks[v]++;
        } else if (this->ranks[u] < this->ranks[v]) {
            this->parents[u] = v;
        } else if (this->ranks[u] > this->ranks[v]){
            this->parents[v] = u;
        }
    }
};

The sets are represented as trees where the root of each tree is the **representative** of the set, returned by find. To ensure $\mathcal{O}(1)$ amortized runtime, the optimizations of **path compression** (in `find`) and **union by rank** (in `unite`) are applied.

In truth, the amortized runtime is $\mathcal{O}(\alpha(n))$, where $n$ is the number of elements and $\alpha$ is the inverse Ackermann function. Since the Ackermann function is famous for growing quickly, its inverse is a small constant ($\leq 4$) for all practical values of $n$. Hence, the amortized runtime can be considered constant time.

Study the implementation of a DSU data structure.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Disjoint Set Union Data Structure