The Central Idea

A graph algorithm takes a graph as input and performs a systematic computation on its vertices and edges.

Typical questions include:

Different questions require different graph algorithms.

Graph Input

A graph is commonly written

\[ G=(V,E), \]

where \(V\) is the set of vertices and \(E\) is the set of edges.

An algorithm must also know whether the graph is:

These properties affect which procedures are valid.

Graph Representation

Algorithms operate on a representation of the graph.

Common representations include:

The representation influences how efficiently neighbors, edges, and weights can be accessed.

Adjacency Lists

An adjacency list stores the neighbors of each vertex.

If

\[ E=\{AB,AC,BD\}, \]

then an undirected adjacency-list description is:

\[ A:\ B,C \] \[ B:\ A,D \] \[ C:\ A \] \[ D:\ B. \]

This representation is especially useful for sparse graphs.

Adjacency Matrices

An adjacency matrix uses a table whose rows and columns correspond to vertices.

For an unweighted graph, an entry may be

\[ 1 \]

when an edge is present and

\[ 0 \]

otherwise.

Matrix representation makes edge lookup direct but can require storage proportional to the square of the number of vertices.

Traversal Is a Foundation

Many graph algorithms begin with a graph traversal.

The two fundamental traversal methods are:

These were introduced earlier as general search and traversal methods. Here they become building blocks for graph computations.

Breadth-First Search Review

BFS explores vertices in layers from a starting vertex.

It naturally uses a queue.

In an unweighted graph, BFS discovers vertices in increasing number of edges from the start.

This makes BFS useful for:

Depth-First Search Review

DFS follows one branch deeply before backtracking.

It naturally uses recursion or an explicit stack.

DFS is useful for:

Reachability

A vertex \(v\) is reachable from a vertex \(u\) if there is a path from \(u\) to \(v\).

To test reachability:

  1. start BFS or DFS at \(u\);
  2. mark every discovered vertex;
  3. check whether \(v\) is ever discovered.

If \(v\) is not discovered when the traversal ends, then \(v\) is not reachable from \(u\).

Example: Reachability

Suppose the edges are

\[ A\!-\!B,\quad B\!-\!C,\quad D\!-\!E. \]

Starting at \(A\), a traversal can reach

\[ A,\ B,\ C. \]

It cannot reach

\[ D,\ E. \]

Therefore,

\[ \boxed{E\text{ is not reachable from }A}. \]

Connected Components

In an undirected graph, a connected component is a maximal set of vertices that are mutually connected by paths.

One BFS or DFS from a starting vertex discovers exactly the component containing that vertex.

Finding All Connected Components

  1. Mark every vertex initially unvisited.
  2. Choose any unvisited vertex.
  3. Run BFS or DFS from it.
  4. All discovered vertices form one component.
  5. If an unvisited vertex remains, start another traversal.
  6. Repeat until every vertex is visited.

Example: Components

Suppose

\[ E=\{AB,BC,DE,FG,FH\}. \]

The connected components are

\[ \{A,B,C\}, \] \[ \{D,E\}, \]

and

\[ \boxed{\{F,G,H\}}. \]

Traversal Trees

During BFS or DFS, record the edge through which each new vertex is first discovered.

These discovery edges form a tree rooted at the starting vertex.

The traversal tree connects every discovered vertex without introducing a cycle.

Spanning Trees

A spanning tree of a connected undirected graph is a tree that contains every vertex of the graph.

A BFS or DFS traversal tree of a connected graph is therefore a spanning tree.

A spanning tree with \(n\) vertices has exactly

\[ \boxed{n-1} \]

edges.

Weighted Graphs

In a weighted graph, each edge has an associated numerical value.

The weight may represent:

Weighted problems require algorithms that use these values appropriately.

Minimum Spanning Trees

A minimum spanning tree, or MST, is a spanning tree of a connected weighted undirected graph whose total edge weight is as small as possible.

If a spanning tree \(T\) contains edges \(e\), its total weight is

\[ w(T)=\sum_{e\in T}w(e). \]

Kruskal's Algorithm

Kruskal's algorithm is a greedy method for constructing a minimum spanning tree.

  1. Sort the edges from smallest weight to largest weight.
  2. Begin with no selected edges.
  3. Consider edges in sorted order.
  4. Add an edge if doing so does not create a cycle.
  5. Stop after \(n-1\) edges have been selected.

Why Kruskal Must Avoid Cycles

Choosing the cheapest available edge is not enough by itself.

A tree cannot contain a cycle.

Therefore, each proposed edge must satisfy the feasibility condition:

Adding this edge must connect previously separate parts of the current forest.

Kruskal Example

Suppose the weighted edges are

\[ AB:1,\quad BC:2,\quad AC:4,\quad CD:3,\quad BD:5. \]

Process by increasing weight:

\[ AB,\ BC,\ CD,\ AC,\ BD. \]

Choose \(AB\), \(BC\), and \(CD\).

With four vertices, three edges are enough:

\[ \boxed{\{AB,BC,CD\}}. \]

Prim's Algorithm

Prim's algorithm is another greedy minimum-spanning-tree method.

It grows one connected tree.

  1. Start from any vertex.
  2. Among edges leaving the current tree, choose one of minimum weight.
  3. Add the new edge and its new vertex.
  4. Repeat until every vertex is included.

Kruskal and Prim Use Different Greedy Views

Kruskal grows a forest by selecting globally light safe edges.

Prim grows one connected tree by selecting a light edge crossing from the current tree to an outside vertex.

Both exploit structural properties that make their greedy choices safe.

Shortest Paths

A shortest-path problem asks for a path whose total cost is minimum.

The correct algorithm depends strongly on the edge weights.

Important cases include:

Shortest Paths in Unweighted Graphs

If every edge counts equally, path length is measured by number of edges.

BFS finds minimum-edge paths from one source to all reachable vertices.

This follows from BFS's level-by-level exploration.

BFS Distance Labels

Let

\[ d(s)=0 \]

for starting vertex \(s\).

When BFS discovers a new vertex \(v\) from \(u\), assign

\[ d(v)=d(u)+1. \]

The resulting value is the minimum number of edges from \(s\) to \(v\).

Dijkstra's Algorithm

Dijkstra's algorithm finds shortest paths from one source when all edge weights are nonnegative.

It repeatedly selects the unsettled vertex with the smallest known tentative distance and uses its outgoing edges to improve neighboring distance estimates.

Tentative Distances

Initialize the source \(s\) with

\[ d(s)=0. \]

Other vertices initially receive

\[ d(v)=\infty. \]

As paths are discovered, these tentative values are lowered.

Relaxation

Suppose an edge from \(u\) to \(v\) has weight \(w(u,v)\).

If

\[ d(u)+w(u,v) then improve the estimate by setting

\[ \boxed{d(v)=d(u)+w(u,v)}. \]

This update is called relaxation.

Dijkstra Example

Suppose

\[ AB:2,\quad AC:5,\quad BC:1,\quad BD:4,\quad CD:2. \]

Starting at \(A\):

\[ d(A)=0,\qquad d(B)=2,\qquad d(C)=5. \]

Settling \(B\) improves \(C\):

\[ 2+1=3<5. \]

Thus

\[ d(C)=3. \]

Continuing Dijkstra

From \(C\), the route to \(D\) has cost

\[ d(C)+2=3+2=5. \]

The route through \(B\) alone would cost

\[ 2+4=6. \]

Therefore, a shortest route from \(A\) to \(D\) is

\[ \boxed{A\to B\to C\to D} \]

with total weight

\[ \boxed{5}. \]

Why Nonnegative Weights Matter

Dijkstra's algorithm permanently settles a vertex once its smallest tentative distance is selected.

This reasoning depends on the fact that extending a path by another edge cannot make its total cost smaller when edge weights are nonnegative.

Negative weights can invalidate this greedy guarantee.

Negative Edge Weights

If negative edge weights are possible, another shortest-path algorithm may be required.

For example, Bellman-Ford repeatedly relaxes edges and can handle negative weights as long as no reachable negative cycle makes a finite shortest path impossible.

The important lesson is:

Algorithm assumptions are part of algorithm correctness.

Negative Cycles

A negative cycle is a cycle whose total weight is negative.

If such a cycle is reachable and can be used on a route to the target, then repeatedly traversing the cycle can reduce total path weight without bound.

In that situation, an ordinary finite shortest path may not exist.

Parent Pointers for Path Reconstruction

Distance values tell us the cost of a shortest path, but not necessarily the path itself.

When a relaxation improves \(d(v)\) through \(u\), record

\[ \operatorname{parent}(v)=u. \]

Following parent links backward reconstructs the route.

Directed Acyclic Graphs

A directed acyclic graph, or DAG, is a directed graph with no directed cycle.

DAGs often model:

Topological Ordering

A topological ordering of a DAG is a linear ordering of the vertices such that every directed edge

\[ u\to v \]

places \(u\) before \(v\).

The ordering respects all directed dependencies.

Example: Topological Order

Suppose

\[ A\to C,\qquad B\to C,\qquad C\to D. \]

Both \(A\) and \(B\) must appear before \(C\), and \(C\) must appear before \(D\).

One valid ordering is

\[ \boxed{A,\ B,\ C,\ D}. \]

Another is

\[ \boxed{B,\ A,\ C,\ D}. \]

Topological Order Is Not Always Unique

When two vertices have no dependency forcing one before the other, either order may be valid.

Therefore, a DAG can have several topological orderings.

The algorithm may need a tie-breaking rule when reproducible output is required.

Kahn's Topological-Sort Idea

One topological-sorting method repeatedly selects a vertex with indegree \(0\).

  1. Find a vertex with no incoming edges.
  2. Output it.
  3. Remove it and its outgoing edges conceptually.
  4. Repeat.

If all vertices are output, a topological ordering has been found.

Cycles Prevent Topological Ordering

Suppose a directed cycle contains

\[ A\to B,\quad B\to C,\quad C\to A. \]

Then \(A\) must appear before \(B\), \(B\) before \(C\), and \(C\) before \(A\).

These requirements cannot all be satisfied.

Therefore, a directed graph has a topological ordering only if it is acyclic.

Cycle Detection

Cycle detection is another important graph-algorithm problem.

DFS can help detect cycles by tracking traversal state.

In a directed graph, encountering an edge back to a vertex still active on the current DFS recursion path signals a directed cycle.

Bipartite Testing

A graph is bipartite if its vertices can be divided into two groups so every edge joins vertices in different groups.

BFS or DFS can test bipartiteness by assigning alternating labels or colors across edges.

If an edge ever joins two vertices with the same assigned color, the graph is not bipartite.

Two-Coloring Procedure

  1. Choose an uncolored vertex and assign one of two colors.
  2. Give every uncolored neighbor the opposite color.
  3. Continue using BFS or DFS.
  4. If adjacent vertices receive the same color, report failure.
  5. Repeat from another uncolored vertex if the graph is disconnected.

Graph Algorithms Often Reuse Earlier Methods

Graph algorithms are not isolated techniques.

They reuse general algorithmic ideas:

Graph algorithms bring these methods into a network setting.

Choosing an Algorithm by Problem Type

Before selecting an algorithm, identify the exact problem.

Shortest Path Is Not the Same as Minimum Spanning Tree

These are different optimization problems.

A shortest-path problem minimizes the cost of a route between selected vertices.

A minimum spanning tree minimizes the total weight needed to connect all vertices.

An MST does not necessarily contain a shortest path between every pair of vertices.

Traversal Tree Is Not Necessarily Minimum Weight

BFS and DFS can produce spanning trees.

But in a weighted graph, those trees are not generally minimum spanning trees.

Traversal order does not automatically minimize total edge weight.

Correctness Depends on Invariants

Graph-algorithm proofs often identify properties that remain true throughout execution.

Examples include:

Termination

Graph algorithms on finite graphs terminate when each step permanently processes a vertex, edge, or candidate and no processed object is reintroduced indefinitely.

A visited set, settled set, selected-edge set, or indegree update often provides the bookkeeping needed to guarantee progress.

Basic Traversal Efficiency

With adjacency lists, BFS and DFS can process a graph in time proportional to

\[ V+E, \]

where \(V\) is the number of vertices and \(E\) is the number of edges.

This reflects examining each vertex and edge only a bounded number of times.

Data Structures Affect Efficiency

Algorithm performance often depends on supporting structures.

Algorithm design and data-structure choice work together.

Common Error: Ignoring Direction

In a directed graph, an edge

\[ A\to B \]

does not imply

\[ B\to A. \]

A traversal or path algorithm must follow the permitted edge directions.

Common Error: Ignoring Edge Weights

BFS minimizes the number of edges, not arbitrary total weight.

In a weighted graph, a path with more edges may have smaller total cost.

Therefore, ordinary BFS should not be used as a general weighted shortest-path algorithm.

Common Error: Using Dijkstra with Negative Weights

Dijkstra's greedy settling rule assumes nonnegative edge weights.

Negative edges can create a cheaper path to a vertex after that vertex was thought to be final.

The algorithm's assumptions must be checked before use.

Common Error: Confusing a Spanning Tree with Any Connected Subgraph

A spanning tree must:

A connected subgraph containing extra cycle edges is not a tree.

Common Error: Assuming a Topological Order Exists

A directed graph containing a directed cycle cannot have a topological ordering.

A correct topological-sort algorithm should detect this failure rather than returning an invalid order.

Common Error: Forgetting Disconnected Components

A traversal from one start vertex visits only its reachable region.

Algorithms intended to process the entire graph must restart from unvisited vertices when disconnected components are possible.

A Reliable Procedure for Graph-Algorithm Problems

  1. Identify whether the graph is directed or undirected.
  2. Identify whether it is weighted or unweighted.
  3. State exactly what output is required.
  4. Choose a suitable representation.
  5. Select an algorithm whose assumptions match the graph.
  6. Define the bookkeeping structures: visited set, queue, stack, priority queue, parents, or components.
  7. State the stopping condition.
  8. Trace a small example.
  9. Check correctness assumptions.
  10. Estimate time and space requirements.

Example: Connected Components

Suppose the graph has vertices

\[ \{A,B,C,D,E,F\} \]

and edges

\[ AB,\ AC,\ DE. \]

A traversal from \(A\) discovers

\[ \{A,B,C\}. \]

A new traversal from \(D\) discovers

\[ \{D,E\}. \]

Vertex \(F\) forms a component by itself.

Therefore, there are

\[ \boxed{3\text{ connected components}}. \]

Example: Unweighted Shortest Path

Suppose the edges are

\[ A\!-\!B,\quad A\!-\!C,\quad B\!-\!D,\quad C\!-\!E,\quad E\!-\!D. \]

BFS from \(A\) discovers:

\[ \text{level }0:\ A, \] \[ \text{level }1:\ B,C, \] \[ \text{level }2:\ D,E. \]

Therefore, the minimum number of edges from \(A\) to \(D\) is

\[ \boxed{2}. \]

Example: Topological Ordering

Suppose the dependencies are

\[ A\to D,\quad B\to D,\quad B\to E,\quad C\to E. \]

The vertices \(A,B,C\) initially have indegree \(0\).

One valid topological ordering is

\[ \boxed{A,\ B,\ C,\ D,\ E}. \]

Other valid orders may also exist.

Practice 1: Reachability

A graph has edges

\[ A\!-\!B,\quad B\!-\!C,\quad D\!-\!E. \]

Is \(C\) reachable from \(A\)? Is \(E\) reachable from \(A\)?

Practice 2: Connected Components

For the graph with edges

\[ AB,\ BC,\ DE,\ FG, \]

how many connected components are present among vertices

\[ A,B,C,D,E,F,G? \]

Practice 3: Spanning Tree Edge Count

How many edges must a spanning tree on \(9\) vertices contain?

Practice 4: Kruskal's Algorithm

Suppose weighted edges are

\[ AB:1,\quad AC:3,\quad BC:2,\quad BD:4,\quad CD:5. \]

Which edges are selected by Kruskal's algorithm for a minimum spanning tree?

Practice 5: Unweighted Shortest Path

Which fundamental traversal should be used to find a path with the fewest edges in an unweighted graph?

Practice 6: Relaxation

Suppose

\[ d(u)=7,\qquad w(u,v)=3,\qquad d(v)=12. \]

Should relaxation improve \(d(v)\)?

Practice 7: Dijkstra Assumption

What important edge-weight assumption is required by the standard Dijkstra algorithm?

Practice 8: Topological Ordering

Given

\[ A\to B,\quad A\to C,\quad B\to D,\quad C\to D, \]

give one valid topological ordering.

Practice 9: Directed Cycle

Can the directed graph

\[ A\to B,\quad B\to C,\quad C\to A \]

have a topological ordering?

Practice 10: Distinguish the Problems

Explain the difference between a shortest-path problem and a minimum-spanning-tree problem.

Practice Answers

Practice 1

\(C\) is reachable from \(A\) through

\[ A\to B\to C. \]

\(E\) is not reachable from \(A\), because \(D\) and \(E\) belong to a different component.

Practice 2

The components are

\[ \{A,B,C\},\qquad\{D,E\},\qquad\{F,G\}. \]

Therefore, there are

\[ \boxed{3}. \]

Practice 3

A tree on \(n\) vertices has \(n-1\) edges:

\[ 9-1=\boxed{8}. \]

Practice 4

Process edges by weight:

\[ AB:1,\quad BC:2,\quad AC:3,\quad BD:4,\quad CD:5. \]

Choose \(AB\) and \(BC\).

Edge \(AC\) would create a cycle, so skip it.

Choose \(BD\).

Thus the MST edges are

\[ \boxed{AB,\ BC,\ BD}. \]

Practice 5

\[ \boxed{\text{breadth-first search}}. \]

Practice 6

The route through \(u\) has cost

\[ 7+3=10. \]

Since

\[ 10<12, \]

update

\[ \boxed{d(v)=10}. \]

Practice 7

Standard Dijkstra requires

\[ \boxed{\text{nonnegative edge weights}}. \]

Practice 8

One valid ordering is

\[ \boxed{A,\ B,\ C,\ D}. \]

Another valid ordering is

\[ A,\ C,\ B,\ D. \]

Practice 9

No. The directed cycle creates mutually inconsistent precedence requirements.

Therefore,

\[ \boxed{\text{no topological ordering exists}}. \]

Practice 10

A shortest-path problem minimizes the cost of a route between selected vertices.

A minimum-spanning-tree problem minimizes the total edge weight needed to connect all vertices in a connected weighted undirected graph.

What to Remember

The most important habit is to ask: What kind of graph do I have, and exactly what network property am I trying to compute?

Where We Go Next

Graph algorithms show how a computational procedure can produce an answer from a discrete structure. But producing an answer is not enough: we must also know why the algorithm is guaranteed to produce the correct answer.

The next lesson, Algorithm Correctness, develops specifications, preconditions, postconditions, invariants, inductive reasoning, partial correctness, and the logic used to justify algorithms.