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

# Cycles

A **cycle** is similar to a path, except that its first and last nodes are identical. In other words, a cycle is like a path that loops back into itself.

The following example graph shows the cycle $a \to c \to d \to a$ marked in blue.

digraph g {
    bgcolor="transparent"
    graph[nodesep=0.5]
    rankdir=LR
    splines=false
    a -> c [color=blue]
    c -> d [color=blue]
    d -> a [color=blue]
    a -> b
    d -> b
}

In an undirected graph, a single edge between nodes $u$ and $v$ consists of the two "half-edges" $(u, v)$ and $(v, u)$. However, the walk $u \to v \to u$, forward and backward along the edge is not considered a cycle. 

In general, in an undirected cycle, each undirected edge may only be traversed once. This also means that an undirected cycle needs to be at least of length three, while a directed cycle can be of length two. 

digraph g {
    bgcolor="transparent"
    subgraph L {
        a -> b [color=green]
        b -> a [color=green]
    }
    subgraph R {
        u -> v [arrowhead=none, color=red]
    }
}


A graph that contains at least one cycle is called **cyclic**, and a graph that does not contain any cycle is called **acyclic**.

# Reachability

If there is a path from node $u$ to node $v$, then $v$ is called **reachable** from node $u$. 

An undirected graph is called **connected** if every node is reachable from every other node. If it is not reachable, it is called **disconnected**.

For example, the graph below is disconnected, because the node $c$ is not reachable from node $d$. If we add an edge $(c, d)$, the graph becomes connected.

Study further graph theory concepts, such as cycles and connectivity.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Graph Terminology II

Cycles