Skip to content
Tutorials Center
My learning

Topics

Lesson 120 of 225 ยท Graphs

Graphs

Understand graphs from scratch: vertices, edges, directed and undirected, weighted, degree, paths, cycles, DAGs and connectivity, with Python code you can run.

A graph is the most general way to describe things that are connected. Cities joined by roads, people joined by friendships, web pages joined by links, courses joined by prerequisites, tasks joined by "must happen before": every one of these is a graph. You have already met two special kinds. A linked list is a graph where every node points to at most one next node, and a tree is a graph with no cycles and exactly one route between any two nodes.

Graphs are the topic where many earlier ideas come together: queues, stacks, hashing and recursion all reappear. This lesson builds the vocabulary. The next lessons show how to store a graph and how to explore it with breadth-first and depth-first search.

Vertices and edges

A graph G = (V, E) has two parts:

  • Vertices (also called nodes): the things. V is the set of vertices.
  • Edges: the connections between pairs of vertices. E is the set of edges.
TEXT
    A ------- B
    |       / |
    |     /   |
    |   /     |
    C ------- D        E

V = {A, B, C, D, E}
E = {A-B, A-C, B-C, B-D, C-D}

Vertex E has no edges. That is allowed: a graph does not have to be in one piece. Two vertices joined by an edge are called neighbors or adjacent.

By convention, V or |V| also stands for the number of vertices and E or |E| for the number of edges. You will see these letters in complexity formulas such as O(V + E).

Directed and undirected graphs

In an undirected graph an edge is a two-way street: if A is connected to B, then B is connected to A. Friendship on a social network is undirected.

In a directed graph (a digraph) each edge has a direction, drawn as an arrow. An edge A -> B lets you go from A to B but says nothing about going back. Following someone on a platform, links between web pages and "course A must come before course B" are all directed.

TEXT
undirected          directed
A --- B             A --> B
|     |             ^     |
C --- D             |     v
                    C <-- D

Weighted graphs

Edges may carry a number called a weight, such as a distance, a price or a travel time. A graph with weights is a weighted graph. The "length" of a path is then the sum of its weights instead of the count of edges. Shortest-path algorithms like Dijkstra's work on weighted graphs.

Python A small graph as a dictionary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Degree

The degree of a vertex is the number of edges touching it. In the example above, B has degree 3 and E has degree 0.

For a directed graph we split it in two: the out-degree is the number of edges leaving a vertex, and the in-degree is the number of edges entering it.

There is a handy fact called the handshake lemma: in an undirected graph, the sum of all degrees equals twice the number of edges, because each edge adds one to the degree of both of its endpoints. It makes a good sanity check when you build a graph in code. In a directed graph the sum of out-degrees equals the sum of in-degrees, and both equal the number of edges.

Python Degrees, in-degrees and the handshake lemma

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Paths, cycles and connectivity

A path is a sequence of vertices where each consecutive pair is joined by an edge. Its length is the number of edges (or the sum of weights in a weighted graph). A simple path never repeats a vertex.

A cycle is a path that starts and ends at the same vertex, with no repeated edges or inner vertices. A -> B -> C -> A is a cycle of length 3 in the example graph. A graph with no cycles is acyclic.

  • An undirected graph is connected if there is a path between every pair of vertices. Otherwise it splits into several connected components. Our example has two: {A, B, C, D} and .
  • A directed graph is strongly connected if you can get from any vertex to any other following arrow directions. It is weakly connected if it would be connected after ignoring directions. See strongly connected components later.
  • A tree is a connected, acyclic, undirected graph. With n vertices it has exactly n - 1 edges.
  • A DAG is a directed acyclic graph. DAGs model dependencies (build steps, course prerequisites) and are ordered by topological sort.
TEXT
DAG (course prerequisites)

  Intro --> Data Structures --> Algorithms
    \                              ^
     \---> Discrete Math ----------/

A self-loop is an edge from a vertex to itself. Parallel edges (or multi-edges) are two edges between the same pair. A graph with neither is a simple graph, and most textbook algorithms assume simple graphs unless told otherwise.

Python Checking whether a path is valid and how long it is

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modelling real problems as graphs

Seeing the graph hiding in a problem is half the work. A few typical translations:

Problem Vertices Edges Kind
Road network intersections road segments with length undirected or directed, weighted
Social network people friendships undirected
Web pages hyperlinks directed
Course plan courses "must be taken before" DAG
Word ladder words words that differ in one letter undirected
Maze or board game cells or positions legal moves usually undirected
Network flow machines cables with capacity directed, weighted

Once the problem is a graph, standard algorithms apply: BFS finds fewest hops, Dijkstra finds cheapest routes, topological sort orders dependencies, and union-find tracks groups.

Python A word ladder is a graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that no one told us "this is a graph." We defined what a vertex is (a word) and what an edge is (one letter of difference), and the structure appeared. Finding the shortest ladder from cold to warm is then a shortest-path question, which breadth-first search answers.

Density: sparse versus dense

The maximum number of edges in a simple undirected graph is V * (V - 1) / 2, since every pair can be joined. For a simple directed graph it is V * (V - 1). A graph with E close to V is sparse; a graph with E close to Vยฒ is dense. Real-world graphs (roads, social networks) are almost always sparse, which is why the representation you pick matters (next lesson).

Python How many edges can a graph have?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Mixing up V and E in complexity. O(V + E) is not O(V). A dense graph has E near Vยฒ, so an algorithm that is "linear in the graph" is quadratic in V.
  • Forgetting both directions in an undirected graph. If you store the edge A-B, store it under A and under B.
  • Assuming the graph is connected. Many bugs come from looping over just one start vertex. Disconnected graphs need a loop over all vertices (see connected components).
  • Confusing a tree with a general graph. A tree has no cycles, so you can skip the "have I seen this?" check. A general graph needs one.
  • Counting path length in vertices instead of edges. A path with 4 vertices has length 3.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. An undirected graph has 6 vertices and its degrees are 2, 3, 3, 1, 2, 1. How many edges does it have?

    The degrees add up to 12, and by the handshake lemma the sum of degrees is twice the number of edges, so there are 6 edges.
  2. 2. What is a DAG?

    DAG stands for directed acyclic graph. It is the structure behind dependency ordering.
  3. 3. How many edges does a tree with 10 vertices have?

    A tree is connected and acyclic, which forces exactly V - 1 edges.
  4. 4. What is the length of the path A -> C -> B -> D in an unweighted graph?

    Length counts edges, and this path has 3 edges (A-C, C-B, B-D) connecting 4 vertices.
  5. 5. What is the maximum number of edges in a simple directed graph with 5 vertices?

    Each of the 5 vertices can point to the 4 others: 5 * 4 = 20. (Self-loops are not allowed in a simple graph.)

Summary

  • A graph is a set of vertices joined by edges; edges can be directed or undirected, weighted or unweighted.
  • The degree of a vertex counts its edges (in-degree and out-degree for directed graphs); in an undirected graph degrees sum to 2E.
  • A path walks along edges; a cycle returns to its start; a connected graph has a path between every pair of vertices.
  • Trees, DAGs and linked lists are special graphs.
  • Real-world graphs are usually sparse, so complexity is written in V and E.
  • Modelling a problem as a graph unlocks standard algorithms.

Next: Graph Representations