Module 8 · Interactive topic

Directed & Undirected Graphs

Vertices joined by edges — with or without arrows

A graph is a set of vertices joined by edges — roads between cities, friendships, links between web pages. If the edges work both ways the graph is undirected; if every edge is a one-way arrow it is directed. Type some edges, flip the switch, and watch the degrees being counted. The panel below tells you what kind of graph you have made.

  • Vertexa point (a city, a person, a web page)
  • Undirected edgeworks both ways: A – B
  • Directed edgea one-way arrow: A → B
  • Degreethe edges touching a vertex
Graph Ready
vertices 0
edges 0
separate parts 0
  • Current
  • Looking at
  • Done
  • Neighbour

Ready

Comparisons 0 Shifts 0
Ready

Edges are written A-B (letters A–J), a single letter adds a vertex with no edges · Keyboard: ← → step · Space play / pause · R reset

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

A graph is vertices and edges

A graph G = (V, E) is a set of VERTICES (the points) and a set of EDGES (the connections). In an UNDIRECTED graph an edge {u, v} works both ways, like a friendship. In a DIRECTED graph an edge (u, v) is an arrow from u to v, like "u follows v". Edges can also carry a number, a WEIGHT — a distance, a cost or a time.

// An edge joins two vertices
struct Edge {
    int u, v;       // undirected: the order does not matter
                    // directed:   the arrow goes u -> v
    int w;          // weight (only in weighted graphs)
};

int V;                       // number of vertices
struct Edge edges[E];        // the edge list

// {A, B} undirected    A --- B
// (A, B) directed      A ---> B

Graph words

  1. Vertex (node) and edge (connection).
  2. Adjacent: two vertices joined by an edge are neighbours.
  3. Path: a walk along edges; a cycle returns to where it started.
  4. Weighted: every edge has a number (cost, distance, time).

Undirected graphs

  1. An edge {u, v} has no direction: u–v is the same as v–u.
  2. Degree of a vertex = the number of edges that touch it.
  3. The degrees add up to 2 × E (each edge counts at both ends).
  4. At most V(V − 1) / 2 edges, when everyone is joined to everyone.

Directed graphs (digraphs)

  1. An edge (u, v) is an arrow from u to v — only one way.
  2. Out-degree = arrows leaving a vertex, in-degree = arrows arriving.
  3. Σ out-degrees = Σ in-degrees = E.
  4. At most V(V − 1) edges, because u → v and v → u are different.

Connected?

  1. Undirected: connected when every vertex can reach every other.
  2. A graph that is not connected falls into separate COMPONENTS.
  3. Directed: strongly connected when every vertex can reach every other FOLLOWING the arrows.
  4. Weakly connected: connected once the arrows are ignored.

Special graphs

  1. Tree: connected, no cycle, exactly V − 1 edges.
  2. Complete graph: every pair of vertices is joined.
  3. DAG: a directed graph with no directed cycle (task order, prerequisites).
  4. Sparse: few edges; dense: close to the maximum.

Where each is used

  1. Undirected: roads, friendships, networks of cables.
  2. Directed: web links, "follows", one-way streets, dependencies.
  3. Weighted: map distances, flight prices, network speeds.
  4. Many of these have a cycle — which is why searches mark vertices.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 DEGREES(edges)
2 for every vertex v: deg[v] ← 0
3 for each edge {u, v}
4 deg[u] ← deg[u] + 1
5 deg[v] ← deg[v] + 1
6 // the sum of all degrees = 2 × E
Complexity

How fast is each operation?

V = number of vertices, E = number of edges. These work on the plain edge list; later pages show faster ways to store a graph.

Operation Best Average Worst Speed
Count all degrees O(V + E) O(V + E) O(V + E) Grows with n
Neighbours of one vertex (edge list) O(E) O(E) O(E) Grows with n
Is the graph connected? O(V + E) O(V + E) O(V + E) Grows with n
Is there a cycle? O(V + E) O(V + E) O(V + E) Grows with n

Undirected vs directed

Undirected Directed
An edge {u, v} — works both ways (u, v) — an arrow from u to v
Drawn as A line An arrow
Degree One number per vertex In-degree and out-degree
Sum of degrees 2 × E Σ out = Σ in = E
Most edges possible V(V − 1) / 2 V(V − 1)
Connected means Every vertex can reach every other Strongly: following the arrows. Weakly: ignoring them
Typical uses Roads, friendships, cables Web links, "follows", task order, one-way streets

Kinds of graph

Kind Rule Example
Tree Connected, no cycle, V − 1 edges A family tree, a folder structure
Complete graph Every pair of vertices is joined A group where everyone knows everyone
DAG Directed, no directed cycle Course prerequisites, build steps
Cycle graph One closed loop through all vertices A ring road
Sparse / dense Few edges / close to the maximum Road map (sparse) / small clique (dense)

Try them: the page above tells you instantly whether the graph you typed is connected, has a cycle, is a tree or complete.

Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 8 correct
Question 1

An undirected graph has 5 vertices and 7 edges. What is the sum of all the degrees?

Question 2

A directed graph has 6 edges. What is the sum of all the in-degrees?

Question 3

What is the greatest number of edges a simple undirected graph with 6 vertices can have?

Question 4

What is the greatest number of edges a simple DIRECTED graph with 6 vertices can have?

Question 5

Which of these is a tree?

Question 6

In a directed graph, what is the out-degree of a vertex?

Question 7

An undirected graph has 8 vertices, 6 edges and 3 separate parts (components). Does it contain a cycle?

Question 8

What is a DAG?

Assessment

Graphs quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Heaps Next topic → Graph Representations