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

# Introducing weighted graphs

**Weighted graphs** are a slight generalization of graphs that are useful for modeling more complex problems using graph theory. In an (edge)-weighted graph, each edge is assigned a **weight**, which is usually a number that represents a property of the edge.

For example, consider this undirected graph of subway stations, where each edge represents a train connection. The weight of an edge is a real number representing the distance between the two nodes it connects.

graph g {
    bgcolor="transparent"
    rankdir="LR"
    splines=false
    a [label="Piccadilly Circus"]
    b [label="Liverpool Street"]
    c [label="King's Cross", group=1]
    d [label="Holborn"]
    e [label="Embankment"]
    f [label="Baker Street", group=1]
    {rank=same; e, f}
    {rank=same; c, d}
    size="9,9!"
    a:ne -- e:w [label=0.7]
    a -- f [label=1.6]
    a:se -- d:w [taillabel=1, labeldistance=8, labelangle=5]
    f -- c [label=1.7]
    d:e -- b:sw [label=1.8]
    e:e -- b:nw [headlabel=2, labeldistance=9, labelangle=355]
    c -- d [label=1.3]
    c -- b [label=2.4]
    
}

Formally, a weighted graph $G = (V, E, w)$ is a graph with nodes $V$, edges $E$ and an additional **edge weight function** $w$. In the most cases, the weights are numeric:
- if the weights are integers, then $w$ is a function $w : E \to \mathbb{N}$
- if the weights are real numbers, then $w$ is a function $w : E \to \mathbb{R}$

Other weight functions are also possible (for example, each edge could be labeled with a text) but these are less common. In this course, most weighted graphs will have integer weights.

If the graph is undirected, we need to deal with a slight technicality. For each "half-edge" $(u, v)$, also its opposite $(v, u)$ is in $E$. But since these two "half-edges" together form a single undirected edge, they must both have the same weight. In other words, the following symmetry condition holds in weighted, *undirected* graphs:
$$w(u, v) = w(v, u) \quad \forall (u,v) \in E.$$

# Paths in weighted graphs

In the previous lesson, we saw that for unweighted graphs, the length of a path is simply the number of edges on the path. For weighted graphs, we’ll adapt our definition of the length of a path to make use of the weights.

For a path in a weighted graph, its length is defined as the sum of the weights of the edges along the path. We can think of the weight of an edge as representing the distance between the nodes it connects.

For example, consider the path from Picadilly Circus to Holborn marked in blue below.

Introduction

Graph Representations

Graph Traversal

Shortest Paths

Spanning Trees

Flow Problems

Conclusion

Appendix

Weighted Graphs

Introducing weighted graphs