[Intermediate] — walk, trail, path, cycle: four words that are not synonyms, and the four different things “connected” can mean.
Before you start
- You know vertices, edges, degree and the four dimensions — what a graph is.
- You can trace a queue and a stack — stacks and queues.
After this lesson you will be able to:
- Distinguish walk, trail, path and simple path, and the same four for closed routes ending in cycle.
- Find connected components of an undirected graph.
- Distinguish strongly from weakly connected in a directed graph, and compute strongly connected components.
- Detect whether a directed graph is a DAG, and say why that matters.
Study route: read the terms first, attempt the prediction just before the lab, then run it. Block 4 is the one that shows why direction changes everything.
Why this exists
“Is there a route from A to B?” sounds like one question. It is at least four, because route is ambiguous — may it revisit a junction? may it reuse a road? — and because in a directed graph “A reaches B” does not imply “B reaches A”.
Every graph algorithm you will meet is stated in this vocabulary. Dijkstra finds a shortest path. Cycle detection looks for a cycle. Topological sort requires a DAG. Getting the terms loose makes the algorithms’ preconditions invisible, which is how you end up running one on input it cannot handle.
Terms used for routes through a graph
A route is any sequence of vertices where each one is joined to the next by an edge. There are four words for different kinds of route, and they are not synonyms. People use them loosely in conversation and precisely in textbooks, which is exactly why they cause trouble.
-
Walk: This is the most general kind of route. You start at a vertex and keep stepping along edges to neighbouring vertices. You are allowed to revisit any vertex you like, and you are allowed to reuse any edge you like. Every route is a walk.
-
Trail: This is a walk with one restriction — you may not reuse an edge. You may still revisit a vertex, as long as you arrive by a road you have not driven before.
-
Path: This is a walk with a stronger restriction — you may not revisit a vertex. Since you never return to a vertex, you can never reuse an edge either, so every path is also a trail.
-
Simple path: This means exactly the same thing as a path. The word “simple” is added for emphasis, because some books use “path” loosely to mean any walk.
So each one is a stricter version of the one before it: every path is a trail, and every trail is a walk. Going the other way is not true — a walk is usually not a path.
WARNING
Books disagree about the word “path”. Some authors use path to mean what this lesson calls a walk, and then say simple path when they mean no repeated vertices. This course uses path to mean no repeated vertices, which is what algorithms literature almost always means. Whenever a source says “path”, check which one it means. The one word that is never ambiguous is walk.
Terms used for routes that come back to the start
A route is closed when it ends at the vertex it started from. The same three levels of strictness apply, with different names.
-
Closed walk: This is a walk that ends where it started. Nothing else is restricted, so you may reuse vertices and edges freely.
-
Circuit: This is also called a closed trail. It is a closed walk that does not reuse an edge. You may pass through the same vertex more than once, as long as you never drive the same road twice.
-
Cycle: This is also called a simple cycle. It is a closed route that does not revisit any vertex, apart from the starting vertex, which is also the finishing vertex.
In a simple graph a cycle needs at least three vertices. With only two you would have to drive back along the single edge joining them, which makes it a walk rather than a cycle. A self-loop is a cycle of length 1, and a pair of parallel edges makes one of length 2 — which is one more reason algorithms usually ask for a simple graph.
Directed versions. In a directed graph, a directed path must follow every edge in the direction it points, and a directed cycle is the same idea for a closed route. A directed graph can easily contain a cycle when you ignore the arrows and no directed cycle at all — the lab below shows exactly that.
Length is counted in edges, not vertices. A route through four vertices has length 3. Off-by-one mistakes here are extremely common.
Terms used for connectivity
Undirected graphs. A graph is connected if you can get from any vertex to any other vertex by some path. If you cannot, the graph falls apart into pieces.
- Connected component: This is a maximal group of vertices that can all reach each other. “Maximal” means you cannot add another vertex to the group without breaking that property. Every vertex belongs to exactly one component, so the components split the graph up completely with nothing left over and nothing counted twice.
Finding the components is one BFS or DFS started from each vertex you have not visited yet, which costs altogether.
Directed graphs. Once edges have arrows, “connected” splits into two different ideas, and the difference matters in practice.
-
Strongly connected: This means that for every pair of vertices and , there is a directed path from to and a directed path back from to . Everywhere can reach everywhere else, following the arrows.
-
Weakly connected: This means the graph is connected once you rub out all the arrows and treat every edge as two-way. It is a much weaker promise.
-
SCC (strongly connected component): This is a maximal group of vertices that can all reach each other following the arrows. It is the directed version of a connected component.
Strong always implies weak. The reverse fails constantly. A one-way street system can look perfectly joined up on a map — weakly connected — while some junction cannot actually be left once you drive into it, which is a strong-connectivity failure and a real problem for anyone using it.
Condensing a directed graph means collapsing each SCC down to a single point. Doing that always produces a DAG. That is a genuinely useful fact: any tangle of circular dependencies becomes acyclic once each mutually-dependent group is treated as one unit, which is how a build tool reports “these five packages form a cycle” instead of looping forever.
DAGs
- DAG (directed acyclic graph): The letters stand for those three words. It is a directed graph with no directed cycle anywhere in it — you can follow the arrows for as long as you like and you will never arrive back where you started.
DAGs are the shape of dependency: build targets, task schedules, spreadsheet formulas, course prerequisites, git commits. They matter because a DAG — and only a DAG — can be put in a topological order, which is a straight line arrangement where every edge points forwards. A directed cycle makes that impossible, because each vertex on the cycle would have to come before itself.
TIP
Predict before running the lab. Take a triangle and reverse just one edge, giving , , . Is the result still strongly connected? Is it weakly connected? Is it a DAG? Decide all three before opening the answers.
Worked example — runnable
Runnable example: save as connectivity.py in any empty directory and run python3 connectivity.py. Standard library only; writes no files.
"""Walks, trails, paths, cycles, components and SCCs."""
from collections import defaultdict, deque
def build(edges, directed=False):
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
if not directed:
adj[v].append(u)
else:
adj.setdefault(v, [])
return adj
def classify_route(adj, seq, directed=False):
"""Is this vertex sequence a walk, and if so is it a trail / a path?"""
for a, b in zip(seq, seq[1:]):
if b not in adj[a]:
return "not even a walk (consecutive vertices are not adjacent)"
used_edges = [(a, b) if directed else tuple(sorted((a, b)))
for a, b in zip(seq, seq[1:])]
repeats_edge = len(set(used_edges)) < len(used_edges)
interior = seq[:-1] if seq[0] == seq[-1] and len(seq) > 1 else seq
repeats_vertex = len(set(interior)) < len(interior)
closed = seq[0] == seq[-1] and len(seq) > 1
if closed:
if not repeats_edge and not repeats_vertex:
return "cycle (simple cycle)"
return "circuit (closed trail)" if not repeats_edge else "closed walk"
if not repeats_vertex:
return "path (simple path)"
return "trail" if not repeats_edge else "walk"
def components(adj):
"""Connected components of an undirected graph, by BFS."""
seen, out = set(), []
for start in sorted(adj):
if start in seen:
continue
comp, q = [], deque([start])
seen.add(start)
while q:
v = q.popleft()
comp.append(v)
for w in adj[v]:
if w not in seen:
seen.add(w)
q.append(w)
out.append(sorted(comp))
return out
def reachable(adj, start):
seen, q = {start}, deque([start])
while q:
v = q.popleft()
for w in adj[v]:
if w not in seen:
seen.add(w)
q.append(w)
return seen
def sccs(adj):
"""Kosaraju: finish order on G, then components on the transpose."""
order, seen = [], set()
def visit(v):
stack = [(v, iter(adj[v]))]
seen.add(v)
while stack:
node, it = stack[-1]
found = next((w for w in it if w not in seen), None)
if found is None:
order.append(node)
stack.pop()
else:
seen.add(found)
stack.append((found, iter(adj[found])))
for v in sorted(adj):
if v not in seen:
visit(v)
rev = defaultdict(list)
for u in adj:
rev.setdefault(u, [])
for v in adj[u]:
rev[v].append(u)
seen2, out = set(), []
for v in reversed(order):
if v in seen2:
continue
comp, q = [], deque([v])
seen2.add(v)
while q:
x = q.popleft()
comp.append(x)
for w in rev[x]:
if w not in seen2:
seen2.add(w)
q.append(w)
out.append(sorted(comp))
return sorted(out)
def is_dag(adj):
colour = {v: 0 for v in adj} # 0 unvisited, 1 in progress, 2 done
def dfs(v):
colour[v] = 1
for w in adj[v]:
if colour[w] == 1:
return False # a back edge: a directed cycle
if colour[w] == 0 and not dfs(w):
return False
colour[v] = 2
return True
return all(colour[v] != 0 or dfs(v) for v in sorted(adj))
if __name__ == "__main__":
print("Block 1 - four words that are not synonyms")
# a "bowtie": two triangles sharing the vertex C
und = build([("A", "B"), ("B", "C"), ("C", "A"),
("C", "D"), ("D", "E"), ("E", "C")])
routes = [
["A", "B", "C"], # path
["A", "B", "C", "A"], # cycle
["A", "B", "C", "D", "E"], # path across both triangles
["A", "B", "C", "D", "E", "C", "A"], # circuit: revisits C, no edge twice
["A", "B", "A", "B"], # walk: reuses the edge A-B
["A", "B", "C", "D", "E", "C"], # trail: open, revisits C, no edge twice
["A", "D"], # not adjacent at all
]
for seq in routes:
print(f" {'-'.join(seq):22} -> {classify_route(und, seq)}")
assert classify_route(und, ["A", "B", "C"]) == "path (simple path)"
assert classify_route(und, ["A", "B", "C", "A"]) == "cycle (simple cycle)"
assert classify_route(und, ["A", "B", "C", "D", "E", "C", "A"]) == "circuit (closed trail)"
assert classify_route(und, ["A", "B", "C", "D", "E", "C"]) == "trail"
assert classify_route(und, ["A", "B", "A", "B"]) == "walk"
print(" length is counted in EDGES: A-B-C has length 2, not 3")
print()
print("Block 2 - connected components partition the vertices")
split = build([("A", "B"), ("B", "C"), ("D", "E"), ("F", "F")])
comps = components(split)
print(f" graph with edges A-B, B-C, D-E, F-F")
for i, c in enumerate(comps, 1):
print(f" component {i}: {c}")
assert comps == [["A", "B", "C"], ["D", "E"], ["F"]]
assert sum(len(c) for c in comps) == len(split)
print(" every vertex is in exactly one component - they partition V")
print()
print("Block 3 - in a digraph, reachability is one-way")
d = build([("A", "B"), ("B", "C"), ("C", "A"), ("C", "D")], directed=True)
for v in sorted(d):
print(f" from {v} you can reach {sorted(reachable(d, v))}")
assert "A" in reachable(d, "D") or True
assert reachable(d, "D") == {"D"}
print(" D reaches nothing but itself, though everything reaches D")
print()
print("Block 4 - strongly vs weakly connected")
cases = {
"cycle A->B->C->A": [("A", "B"), ("B", "C"), ("C", "A")],
"one edge reversed": [("A", "B"), ("C", "B"), ("A", "C")],
"cycle plus a dead end": [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D")],
}
for name, edges in cases.items():
dg = build(edges, directed=True)
ug = build(edges, directed=False)
strong = sccs(dg)
weak = components(ug)
print(f" {name}")
print(f" strongly connected: {str(len(strong) == 1):5} SCCs {strong}")
print(f" weakly connected: {str(len(weak) == 1):5}")
print(f" is a DAG: {is_dag(dg)}")
assert len(sccs(build(cases["cycle A->B->C->A"], directed=True))) == 1
assert is_dag(build(cases["one edge reversed"], directed=True))
assert not is_dag(build(cases["cycle A->B->C->A"], directed=True))
print(" the reversed-edge graph is weakly connected but NOT strongly connected,")
print(" and having no directed cycle is exactly what makes it a DAG")
print()
print("Block 5 - condensing the SCCs of a digraph always yields a DAG")
messy = build([("a", "b"), ("b", "c"), ("c", "a"), # one 3-cycle
("c", "d"), ("d", "e"), ("e", "d"), # a 2-cycle
("e", "f")], directed=True)
comp_of = {}
groups = sccs(messy)
for i, grp in enumerate(groups):
for v in grp:
comp_of[v] = i
print(f" SCCs: {groups}")
cond = defaultdict(list)
for u in messy:
cond.setdefault(comp_of[u], [])
for v in messy[u]:
if comp_of[u] != comp_of[v]:
cond[comp_of[u]].append(comp_of[v])
print(f" condensed graph edges: "
f"{sorted((a, b) for a, bs in cond.items() for b in set(bs))}")
print(f" is the condensation a DAG? {is_dag(cond)}")
assert is_dag(cond)
assert not is_dag(messy)
print(" the original has cycles; collapsing each mutually-reachable group removes them")
print()
print("connectivity: passed")Expected output:
Block 1 - four words that are not synonyms
A-B-C -> path (simple path)
A-B-C-A -> cycle (simple cycle)
A-B-C-D-E -> path (simple path)
A-B-C-D-E-C-A -> circuit (closed trail)
A-B-A-B -> walk
A-B-C-D-E-C -> trail
A-D -> not even a walk (consecutive vertices are not adjacent)
length is counted in EDGES: A-B-C has length 2, not 3
Block 2 - connected components partition the vertices
graph with edges A-B, B-C, D-E, F-F
component 1: ['A', 'B', 'C']
component 2: ['D', 'E']
component 3: ['F']
every vertex is in exactly one component - they partition V
Block 3 - in a digraph, reachability is one-way
from A you can reach ['A', 'B', 'C', 'D']
from B you can reach ['A', 'B', 'C', 'D']
from C you can reach ['A', 'B', 'C', 'D']
from D you can reach ['D']
D reaches nothing but itself, though everything reaches D
Block 4 - strongly vs weakly connected
cycle A->B->C->A
strongly connected: True SCCs [['A', 'B', 'C']]
weakly connected: True
is a DAG: False
one edge reversed
strongly connected: False SCCs [['A'], ['B'], ['C']]
weakly connected: True
is a DAG: True
cycle plus a dead end
strongly connected: False SCCs [['A', 'B', 'C'], ['D']]
weakly connected: True
is a DAG: False
the reversed-edge graph is weakly connected but NOT strongly connected,
and having no directed cycle is exactly what makes it a DAG
Block 5 - condensing the SCCs of a digraph always yields a DAG
SCCs: [['a', 'b', 'c'], ['d', 'e'], ['f']]
condensed graph edges: [(0, 1), (1, 2)]
is the condensation a DAG? True
the original has cycles; collapsing each mutually-reachable group removes them
connectivity: passed
Block 5 is the structural result worth carrying: any directed graph, however tangled, becomes a DAG once each strongly connected component is collapsed to a point. That is how a build tool reports “these five packages form a dependency cycle” instead of looping forever.
Common pitfalls and traps
- Using “path” without checking the convention. In this course it means no repeated vertices. Some textbooks use it for any walk. Walk is the unambiguous word.
- Counting length in vertices. Length is edges. A route through vertices has length .
- Assuming weakly connected implies strongly connected. It does not, and the gap is exactly the one-way-street problem.
- Running topological sort on a graph with cycles. It requires a DAG. Detect first, or your sort silently omits vertices.
- Forgetting that self-loops and parallel edges are cycles. In a multigraph the shortest cycle can have length 1 or 2, which breaks algorithms assuming 3.
- Recursing on a large graph. Python’s default recursion limit is around 1000; a long path overflows it. The lab’s DFS is iterative for this reason.
Check your understanding
- Classify in a graph containing all those edges.
- What is the length of a cycle through 5 distinct vertices?
- Give a digraph that is weakly but not strongly connected.
- Why does collapsing SCCs always give a DAG?
- A graph has 10 vertices and 3 connected components. What is the fewest edges it can have?
Answers — open only after an attempt
- It repeats vertex but no edge, so it is a trail — and not closed, since it ends at .
- 5. A cycle through distinct vertices has edges, because the last edge returns to the start.
- , : ignoring directions it is connected, but nothing reaches , so it is not strongly connected.
- Because if the condensation had a cycle, every component on that cycle would be mutually reachable with every other — so they would all have been a single SCC in the first place. Their being separate SCCs contradicts the cycle’s existence.
- Each component with vertices needs at least edges (a tree). With 10 vertices in 3 components the total is edges.
And the prediction from the connectivity section: with , , — it is not strongly connected (nothing leaves , so reaches nothing), it is weakly connected (ignore directions and it is a triangle), and it is a DAG (no directed cycle: the only routes are , ).
Practice — independent task
Implement bridges(graph) and articulation_points(graph) — the edges and vertices whose removal disconnects a graph.
- A bridge is an edge whose removal increases the number of connected components. An articulation point is a vertex whose removal does.
- Implement the naive version first: remove each edge (then each vertex) in turn, recount components, compare. .
- Then implement Tarjan’s linear-time algorithm using DFS discovery times and low-link values. Assert it agrees with the naive version on at least twenty random graphs.
- Explain in a comment what the low-link value means — you should be able to state it as a sentence about which ancestors a subtree can reach.
- Apply it to something real: model a small network where bridges are single points of failure, and report which links have no redundancy.
Edge cases: a disconnected input; a single vertex; a graph that is one long path (every edge is a bridge — check this); a cycle (no bridges at all — check this too).
Done when: Tarjan agrees with the naive version on every random graph tested, your path and cycle cases behave as predicted, and your low-link explanation is in your own words.
Before moving on
You can state all four route words precisely, find components, tell strong from weak connectivity, and detect a DAG.
Recap: walk (anything) ⊃ trail (no repeated edge) ⊃ path (no repeated vertex); closed versions are closed walk ⊃ circuit ⊃ cycle; length counts edges; components partition ; strongly connected means mutual directed reachability, weakly means connected ignoring direction; a DAG has no directed cycle and is exactly what admits a topological order; condensing SCCs always yields a DAG.
Next: Subgraphs, Trees and Forests — the pieces of a graph, and where trees come from.
Related
- DFS · BFS — the traversals every result here is computed with
- Topological Sort — what a DAG buys you
- Union-Find — components maintained incrementally
Software engineering
Infrastructure & security
Computer science
Hardware & engineering