Graphs: Represent, Traverse, Analyse

11.1Graph foundations

Where graphs appear

Directed, undirected, weighted, and unweighted

Sparse and dense graphs

Degree of a vertex

• In an undirected graph, deg(v) counts incident edge ends; a self-loop contributes two.
• In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.
• Total directed degree is in-degree plus out-degree.

Self-loop, path, and cycle

11.2Graph representations

A representation must preserve vertex relationships in memory. The two standard choices are an adjacency matrix and an adjacency list.

class GraphMatrix:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj = [[0] * vertices for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u][v] = 1

    def display(self):
        for row in self.adj:
            print(row)

g = GraphMatrix(5)
for u, v in [(0,1), (0,4), (1,2), (1,3),
             (1,4), (2,3), (3,4)]:
    g.add_edge(u, v)
g.display()

class GraphList:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj = {i: [] for i in range(vertices)}

    def add_edge(self, u, v):
        self.adj[u].append(v)

    def display(self):
        for vertex, neighbors in self.adj.items():
            print(vertex, ":", neighbors)

11.3Traversal: visit each reachable vertex

• Visited (discovered): the vertex has been seen.
• Explored: all adjacent vertices of that vertex have been considered.

Applications include pathfinding, web crawling, social-network analysis, and network routing.

11.4Breadth-first search (BFS)

BFS explores the nearest vertices first. A first-in, first-out queue holds discovered vertices whose neighbours still need to be examined.

1. Start: mark the source visited and put it in the queue.
2. Process: remove the front vertex. Mark and enqueue each of its unvisited neighbours.
3. Repeat: continue until the queue is empty.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return order

Why BFS gives shortest paths

The queue processes distance d before distance d + 1. When v is first discovered from u, set distance[v] = distance[u] + 1 and parent[v] = u. Mark v immediately when enqueuing it, so two incoming edges cannot enqueue it twice. Following parent pointers backwards reconstructs a shortest path; for example, 0 → 1 → 4 → 6 has three edges.

The traversal order depends on neighbour order, but shortest-path distances do not. In the animation, an undiscovered vertex has distance ∞; the source has distance 0 and no parent.

Analysis

Initializing visited takes O(V). Across the traversal, adjacency-list scanning examines all vertices and edges once, giving O(V + E).

11.5Depth-first search (DFS)

DFS follows one route as far as possible before trying another. Recursion remembers where to continue: returning from a call resumes the caller’s neighbour scan.

1. Discover: mark the current vertex visited and record it.
2. Explore: scan its outgoing neighbours in order. Recurse only on an unvisited neighbour.
3. Return: once every neighbour is checked, pop the call and resume its parent.

def dfs(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
    if order is None:
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, order)
    return order

How to read the call stack

Local to each call

u is the vertex being explored; v is the neighbour currently being checked. The frame also remembers which neighbour comes next.

Shared by all calls

The visited set and discovery order belong to the whole traversal. Returning from a call does not erase them.

Suspended versus active

Only the top frame executes. A parent waits at step 4 while its child runs, then resumes at step 2.

Discovery versus completion

A vertex enters the traversal order when first visited. Its frame is removed only after every outgoing neighbour has been checked.

Example: by the time DFS reaches 2, vertex 4 has already finished. The edge 2 → 4 is checked and skipped; it does not create another call.

Analysis and comparison

DFS uses O(V) space for visited plus up to O(V) recursive calls or explicit stack entries. Its time is O(V + E) with adjacency lists and O(V²) with an adjacency matrix.

11.6Topological sort and cycle detection

In a DFS implementation, insert each vertex at the front of the result when it finishes (equivalently, push it to a stack and reverse the finish stack).

Finish stack versus call stack: the call stack contains unfinished calls and shrinks on return. The finish stack records vertices only after all their outgoing neighbours are finished. Reversing that finish order places every prerequisite before the vertices that depend on it. For a disconnected DAG, start DFS from each still-unvisited vertex before reversing the complete finish order.

Clothing example and DFS times

Constraints include undershorts → pants, undershorts → shoes, pants → belt, pants → shoes, socks → shoes, shirt → belt, shirt → tie, belt → jacket, and tie → jacket. The watch is independent.

1/8 means discovery time 1 and finish time 8.

Cycle detection using DFS

For a directed graph, an edge to an already-visited vertex is not enough to prove a cycle. The important question is whether that vertex’s call is still active.

def has_cycle(graph):
    visited = set()
    def visit(u, parent):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                if visit(v, u): return True
            elif v != parent:
                return True
        return False
    return any(visit(u, None) for u in graph if u not in visited)

11.7Articulation points (cut vertices)

Let disc[u] be u’s discovery time and low[u] the smallest discovery time reachable from u’s DFS subtree using tree edges and at most one back edge.

How discovery and low values change

disc[u] records when u is first visited. low[u] records the earliest discovery time reachable from u’s subtree without using the edge back to its parent.

1. On entry: set disc[u] = low[u] to the next discovery time.
2. After a child v returns: set low[u] = min(low[u], low[v]).
3. At a visited non-parent neighbour v: set low[u] = min(low[u], disc[v]).
4. Test for separation: for a non-root u, low[v] ≥ disc[u] means that child’s subtree cannot reach an ancestor of u. For the root, count DFS-tree children: more than one makes it a cut vertex.

Second slide example

For the graph with edges G–C, C–B, C–D, B–A, A–D, D–F, F–E, and D–E, starting DFS at A gives discovery/low labels A 1/1, B 2/1, C 3/1, D 4/1, E 5/4, F 6/4, and G 7/7.

11.8Questions, applications, and shortest paths

Traversing a disconnected graph

Keep one visited set for the whole graph. Scan vertices in order; each unvisited vertex starts a new DFS tree and increases the component count. Returning from one DFS tree finishes only that component. An isolated vertex also forms a component.

Shortest paths: weighted versus unweighted graphs