14. Graph Problems

Turning Traversal into an Answer#

Recall 13. Graph Traversal: we can explore exactly the vertices reachable from a source. Many graph problems add one piece of state to that mechanism. To identify components, label each reached vertex. To detect an undirected cycle, remember the edge we came from. To try a Hamiltonian route, remember the current candidate path and undo it when a choice fails.

This note uses simple undirected graphs unless stated otherwise. Directed cycles need a different test, explained in 15. Directed Graph Algorithms and Shortest Paths. Let $V$ count vertices and $E$ count edges. C functions here share the matrix Graph, checkVertex and allocation helper from 12. Graphs and Representations. They belong inside that implementation file so the representation is accessible.

Checking for an Undirected Cycle#

Why “Visited Neighbour” Needs Qualification#

Suppose DFS follows $0-1$. At vertex 1 it sees neighbour 0, which is already visited. That is expected: undirected edges appear in both endpoint lists or matrix cells. Traversing back along the same edge does not establish a cycle.

Pass the parent, the vertex from which this call was reached. Ignore the edge back to that parent. Any other edge to an already visited vertex closes a cycle: the DFS discovery tree already contains a route joining those vertices, and the extra edge closes it.

A second issue is disconnectedness. Starting only at 0 may check an acyclic component while a different component contains a triangle.

In the image, DFS from 0 reaches only $\{0,1,4\}$. The cycle $2-5-6-2$ remains untouched. The complete solution restarts DFS from each unvisited vertex while retaining the same visited array.

static bool cycleRec(Graph g, int v, int parent, bool seen[]) {
    seen[v] = true;
    for (int w = 0; w < g->nV; w++) {
        if (!g->edges[v][w] || w == parent) continue;
        if (seen[w]) return true;
        if (cycleRec(g, w, v, seen)) return true;
    }
    return false;
}

bool hasCycle(Graph g) {
    bool *seen = checkedCalloc((size_t)g->nV, sizeof *seen);
    bool result = false;
    for (int v = 0; v < g->nV && !result; v++)
        if (!seen[v]) result = cycleRec(g, v, -1, seen);
    free(seen);
    return result;
}

The source has parent -1 because it has no incoming discovery edge. A successful recursive call returns true through its callers. If every component finishes without finding an extra visited-neighbour edge, the graph is a forest.

For adjacency lists, this adds constant work to ordinary DFS and costs $O(V+E)$ worst-case. The matrix code scans full rows and costs $O(V^2)$ worst-case. The visited array and recursion depth need $O(V)$ auxiliary space.

This parent-vertex test assumes no parallel edges: two distinct parallel edges could form a multigraph cycle, yet both point to the parent and would be skipped. Such graphs require remembering parent edge identity, but the course excludes multigraphs.

Practice. Trace the triangle $0-1$, $1-2$, $2-0$, starting at 0 with ascending neighbours. Which check establishes the cycle?

Connected Components and Cached Reachability#

A connected component is a maximally connected group of vertices. Number the components 0, 1, 2, … and store componentOf[v] for each vertex. Initialise it to -1, meaning “unassigned”. Starting a traversal from an unassigned vertex labels all vertices reachable from it with the current component number. Increase the number only after that traversal finishes.

Read the array by vertex index: componentOf[4]=0, while componentOf[5]=1. Labels are identifiers, not component sizes. The vertices need not appear contiguously: component 0 contains 0, 1 and 4.

static void labelRec(Graph g, int v, int label, int componentOf[]) {
    componentOf[v] = label;
    for (int w = 0; w < g->nV; w++)
        if (g->edges[v][w] && componentOf[w] == -1)
            labelRec(g, w, label, componentOf);
}

// Caller owns componentOf, with g->nV slots. Returns component count.
int components(Graph g, int componentOf[]) {
    for (int v = 0; v < g->nV; v++) componentOf[v] = -1;
    int count = 0;
    for (int v = 0; v < g->nV; v++) {
        if (componentOf[v] == -1) {
            labelRec(g, v, count, componentOf);
            count++;
        }
    }
    return count;
}

Each run labels one whole component, because DFS finds precisely the reachable vertices. Different runs cannot overlap, because previously labelled vertices are skipped. This proves both completeness and separation of the resulting groups. Cost is $O(V+E)$ for adjacency lists or $O(V^2)$ for this matrix implementation, with $O(V)$ result and recursion space.

Once labels are computed, undirected reachability can be answered in $O(1)$: a route from $v$ to $w$ exists exactly when componentOf[v] == componentOf[w]. Cache the count and labels inside the graph wrapper when queries are frequent.

The cache describes a particular graph state. Inserting an edge between different components merges them; removing a bridge, an edge with no alternative endpoint route, splits a component. Adding an edge within a component or removing an edge on a cycle does not change the component partition. A simple implementation invalidates the cache after an edge update and recomputes on the next query. A constant-time cached query does not make updates constant-time.

Practice. Two components are connected by a newly inserted edge. Why can the component count decrease by exactly one, rather than two?

Hamiltonian Paths and Circuits#

A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit also has an edge from its last vertex back to its first. In the circuit the start is repeated only to close the route; it is counted as one vertex visit.

The orange route is $0-2-1-3-4$: it includes all five vertices. The green circuit is $0-1-3-4-2-0$. Neither is required to use every edge. This is why vertex coverage, rather than just ordinary reachability, is the hard constraint.

Backtracking Through Candidate Paths#

Ordinary DFS permanently marks a vertex once its reachable region is explored. Hamiltonian search needs a different rule: onPath[v] means v is in the current candidate path. If that candidate fails, clear its mark so another route can use it.

At a call for vertex $v$, mark $v$ and decrease the number of vertices left. If none remain, a Hamiltonian path has been found. Otherwise try each adjacent vertex not currently on the path. If all choices fail, undo the mark and return false.

Consider edges $0-1$, $0-2$, $1-2$, $1-3$, $2-4$, $3-4$. Starting at 0, try $0-1-2-4-3$: it succeeds. But if the edge $3-4$ is absent, the branch $0-1-2-4$ stops early and must release 4, then 2, before trying $0-1-3$. Clearing marks is the operation that restores the caller's candidate state; it is not forgetting explored reachability.

Here is the lecture algorithm with explicit cleanup on both successful and unsuccessful returns. Cleanup makes repeated calls safe and lets a test inspect that the temporary array has been restored.

static bool hamRec(Graph g, int v, bool onPath[], int left,
                   int start, bool circuit) {
    onPath[v] = true;
    left--;
    if (left == 0) {
        bool ok = !circuit || g->edges[v][start];
        onPath[v] = false;
        return ok;
    }
    for (int w = 0; w < g->nV; w++) {
        if (g->edges[v][w] && !onPath[w] &&
            hamRec(g, w, onPath, left, start, circuit)) {
            onPath[v] = false;
            return true;
        }
    }
    onPath[v] = false;
    return false;
}

bool hasHamiltonianPath(Graph g) {
    bool *onPath = checkedCalloc((size_t)g->nV, sizeof *onPath);
    bool found = false;
    for (int start = 0; start < g->nV && !found; start++)
        found = hamRec(g, start, onPath, g->nV, start, false);
    free(onPath);
    return found;
}

bool hasHamiltonianCircuit(Graph g) {
    if (g->nV < 3) return false; // simple undirected cycle convention
    bool *onPath = checkedCalloc((size_t)g->nV, sizeof *onPath);
    bool found = hamRec(g, 0, onPath, g->nV, 0, true);
    free(onPath);
    return found;
}

For paths, we try each starting vertex because a valid route need not start at 0. For circuits, fixing start 0 loses nothing: any spanning circuit passes through 0 and can be described starting there. The base case checks the closing edge. Having included every vertex is not enough to establish a circuit.

Correctness follows from the candidate invariant: current marks identify a simple route from the chosen start to $v$. We extend it only along real edges to unused vertices. The successful base case covers exactly $V$ vertices; exhaustive alternatives ensure that a valid route, if one exists, is eventually tried. Undoing marks preserves the invariant when returning to try a different choice.

Why the Search Can Be Very Expensive#

There are $V!$ possible vertex orderings for a path. Prefixes branch into many alternatives: first $V$ choices, then $V-1$, then $V-2$, and so on. Edges prune illegal choices, and the search stops on a success, but graphs with no solution can force extensive exploration.

The slides describe the factorial search as $O(V!)$, counting possible candidate orderings. A literal implementation also checks neighbours and eligibility. A conservative bound for the matrix code above is $O(V\cdot V!)$: there are $O(V!)$ prefix calls and each can scan $V$ matrix cells. This polynomial factor does not change the central contrast with polynomial-time traversal. Auxiliary space is $O(V)$ for marks and recursion depth, excluding the graph: exponential work does not mean all candidates are stored simultaneously.

The Hamiltonian existence decision problem is NP-complete; in particular it is NP-hard, as the slides state. This does not prove that no polynomial-time algorithm could ever exist. It says none is known and a polynomial solution would solve a wider class of difficult decision problems. Brute force remains useful on small instances or heavily constrained graphs.

Practice. A star has centre 0 and leaves 1, 2, 3. Why does it have no Hamiltonian path, even though it is connected?

Eulerian Paths and Circuits#

An Eulerian path uses every edge exactly once. An Eulerian circuit also ends where it starts. Vertices may repeat. The lecture uses “path” here for what many graph-theory texts call an Eulerian trail, since edges are unique but vertices need not be.

The left route $4-2-0-1-3-0$ repeats vertex 0 but uses every edge once. Its endpoints are 4 and 0. On the right, $4-2-0-1-3-4$ closes into a circuit. Count edges, rather than applying the Hamiltonian no-repeated-vertex condition.

In the bridge model each land area becomes a vertex and each bridge an edge. Several bridges connect the same land areas, so the historical example is a multigraph even though the course's implementations mainly use simple graphs. The degree argument still explains the obstruction.

The Degree Test and Its Reason#

Whenever a route enters an internal vertex along one unused edge, it must leave along another. Those edges pair up. In a circuit, every visit pairs an arrival with a departure, so every degree must be even. In an open Eulerian route, the start has one unpaired departure and the end one unpaired arrival; exactly those two vertices have odd degree.

The precise undirected tests are:

• An Eulerian path exists iff there are zero or two odd-degree vertices, and all vertices of non-zero degree lie in one connected component.
• An Eulerian circuit exists iff every degree is even, and all vertices of non-zero degree lie in one connected component.

These conditions are also sufficient. Starting at an odd vertex when there are two, or any non-isolated vertex otherwise, unused edges can form a trail without stranding it at an inappropriate internal vertex: the parity pairs arrivals and departures. If unused edges remain, connectivity supplies a vertex on the current trail from which another closed trail can be made and spliced in. Repeating uses all edges. This is the idea behind an efficient constructive Euler traversal; the slides require the existence test rather than its full construction.

Why Isolated Vertices Do Not Matter#

Vertex 4 has no edges to cover. Excluding it from the connectivity requirement allows the remaining component's Eulerian route. But two disconnected triangles do not have a single Eulerian route: every degree is even, yet no route can jump between their edge-containing components.

For a graph with no edges, the lecture's existence test returns true for both conditions: there is nothing to traverse. This uses the empty-edge-route convention. If an application demands a nonempty route, state that extra requirement explicitly.

static void reachRec(Graph g, int v, bool seen[]) {
    seen[v] = true;
    for (int w = 0; w < g->nV; w++)
        if (g->edges[v][w] && !seen[w]) reachRec(g, w, seen);
}

// circuit=false checks existence of an Eulerian path;
// circuit=true checks existence of an Eulerian circuit.
bool hasEulerian(Graph g, bool circuit) {
    int *degree = checkedCalloc((size_t)g->nV, sizeof *degree);
    bool *seen = checkedCalloc((size_t)g->nV, sizeof *seen);
    int odd = 0, start = -1;
    for (int v = 0; v < g->nV; v++) {
        for (int w = 0; w < g->nV; w++)
            degree[v] += g->edges[v][w] ? 1 : 0;
        if (degree[v] % 2 != 0) odd++;
        if (degree[v] > 0 && start == -1) start = v;
    }
    if (start != -1) reachRec(g, start, seen);
    bool connected = true;
    for (int v = 0; v < g->nV; v++)
        if (degree[v] > 0 && !seen[v]) connected = false;
    bool parity = circuit ? odd == 0 : (odd == 0 || odd == 2);
    free(seen); free(degree);
    return connected && parity;
}

Degree calculation over lists examines $2E$ entries. Connectivity is one DFS; checking its result is $O(V)$. Thus the adjacency-list algorithm costs $O(V+E)$ time and $O(V)$ auxiliary space. The matrix code costs $O(V^2)$ because both degree calculation and DFS scan rows. Testing existence is much cheaper than Hamiltonian exhaustive search.

Practice. Do two disjoint cycles pass the degree test? Do they have an Eulerian circuit? What changes if one component is just an isolated vertex?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. An undirected graph has exactly two odd-degree vertices and all non-isolated vertices connected. Does it have an Eulerian trail, an Eulerian circuit, both or neither?

Question 2. A DFS cycle checker sees an already visited neighbour in an undirected graph. Why must it compare that neighbour with the current vertex’s parent?

Question 3. A graph has 10 vertices but only 3 reachable from s. Compare the result of a connected-components query with a reachability query from s.

Tractable and Intractable Problems#

A polynomial-time algorithm has a bound such as $V^2$, $VE$, or $(V+E)^3$, with a fixed exponent. The lecture calls a problem tractable when a polynomial-time solution is known, and intractable when no efficient polynomial-time solution is known in the general case. Large polynomial costs can still be impractical; this distinction concerns scaling rather than actual stopwatch speed.

Small changes to a question can radically change its difficulty:

For two-colouring, give the start one colour and every newly discovered neighbour the opposite colour. If an edge joins equal colours, no consistent two-colouring exists in that component; an odd cycle is the obstruction. Repeat across components. This is another example of a small amount of extra state turning traversal into a decision algorithm.

Graph isomorphism asks whether two graphs become identical after renaming their vertices. Equal vertex and edge counts and matching degree patterns are necessary but not sufficient. The lecture presents it as a bonus problem, rather than assigning a standard traversal solution. Avoid assuming that changing labels changes the underlying structure.

Practice. Why does “does the graph contain a clique?” need a size convention?