Unit 6: Graphs

CSE205 — Data Structures And Algorithms 9 min read

I. Foundations of Graphs

A graph is a mathematical structure (G=(V,E)) that represents relationships between objects. The set (V) contains vertices, or nodes, while (E) contains edges connecting pairs of vertices. Graph algorithms organize traversal, reachability, and path-finding over these relationships.

Vertices and edges: For (V={A,B,C}), an edge ((A,B)\in E) connects vertices (A) and (B).
Directed graph: Each edge has a direction; ((u,v)) permits movement from (u) to (v), but not necessarily from (v) to (u).
Undirected graph: Each edge represents a two-way connection, so ({u,v}) can be traversed in either direction.
Weighted graph: Every edge ((u,v)) has a numerical weight (w(u,v)), such as distance, time, or cost.
Path: A sequence (v_0,v_1,\ldots,v_k) in which every consecutive pair is connected by an edge.
Path length: In an unweighted graph, it is the number of edges; in a weighted graph, it is (\sum_{i=0}^{k-1}w(vi,v{i+1})).
Cycle: A path that begins and ends at the same vertex.
Representations:
- Adjacency list: Stores each vertex’s neighbors; requires (O(V+E)) space and is effective for sparse graphs.
- Adjacency matrix: Stores edge information in a (V\times V) matrix; requires (O(V^2)) space but tests adjacency in (O(1)).

II. Graph Traversal — Systematic Vertex Exploration

A. Graph traversal

Graph traversal is the systematic process of visiting vertices reachable from one or more starting vertices.

Traversal state: A visited set or Boolean array prevents repeated processing and infinite movement around cycles.
General pattern: Select a start vertex, mark it visited, inspect its adjacent vertices, and continue until no reachable unvisited vertex remains.
Traversal forest: When a graph is disconnected, traversal must restart from each unvisited vertex; the resulting trees form a spanning forest.
Traversal order: The order depends on the algorithm and the ordering of adjacency lists, so multiple valid orders may exist.
Complexity: With adjacency lists, each vertex and edge is inspected a constant number of times, giving:
TEXT
```
Time:  O(V + E)
Space: O(V)
```
Here, (V) is the number of vertices and (E) is the number of edges.

B. Applications and limitations

Traversal provides the foundation for structural analysis but does not automatically optimize weighted path cost.

Applications: Traversal supports reachability testing, connected-component detection, cycle detection, topological sorting, and spanning-tree construction.
Directed reachability: Reaching (v) from (u) does not imply that (u) is reachable from (v).
Limitation: Ordinary traversal answers whether a path exists; specialized shortest-path algorithms determine which path has minimum cost.

III. Breadth-First Search — Level-by-Level Exploration

A. Breadth-first search

Breadth-first search (BFS) explores vertices in increasing order of their unweighted distance from a source and uses a first-in, first-out queue.

Core principle: All vertices at distance (k) edges are discovered before vertices at distance (k+1).
Queue operation: A discovered vertex is enqueued once and dequeued when its neighbors are examined.
Distance guarantee: In an unweighted graph, the first discovery of (v) gives the minimum edge count from source (s).
Parent array: Setting parent[v] = u when (v) is discovered through (u) constructs a BFS tree and permits path reconstruction.

Pseudocode:

TEXT

BFS(G, s):
    mark s visited
    distance[s] = 0
    enqueue s

    while queue is not empty:
        u = dequeue
        for each v adjacent to u:
            if v is unvisited:
                mark v visited
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue v

Here, (G) is the graph, (s) is the source, and (u,v) are vertices.

B. Applications and limitations

BFS is optimal for minimum-edge paths but does not minimize arbitrary weighted cost.

Applications: It finds shortest paths in unweighted graphs, levels in networks, connected components, and whether an undirected graph is bipartite.
Complexity: Adjacency-list BFS takes (O(V+E)) time and (O(V)) auxiliary space.
Limitation: If edges have unequal weights, fewer edges may still produce a larger total cost; Dijkstra or Bellman-Ford is then required.

IV. Depth-First Search — Branch-Oriented Exploration

A. Depth-first search

Depth-first search (DFS) follows one branch as deeply as possible before backtracking to explore alternatives.

Core principle: DFS uses a last-in, first-out stack, implemented explicitly or through recursive function calls.
Recursive structure: A vertex is marked before recursive calls, ensuring that cycles do not cause infinite recursion.

Pseudocode:

TEXT

DFS(G, u):
    mark u visited
    for each v adjacent to u:
        if v is unvisited:
            parent[v] = u
            DFS(G, v)

Here, (G) is the graph, (u) is the current vertex, and (v) is a neighbor.

Discovery and finish times: DFS can assign a discovery time when entering (u) and a finish time after all neighbors have been processed.
DFS forest: Running DFS from every unvisited vertex identifies separate components or reachability trees.
Complexity: With adjacency lists, time is (O(V+E)), while the visited structure and recursion stack require (O(V)) space.

B. Applications and limitations

DFS exposes nesting and dependency structure, although it does not generally produce shortest paths.

Applications: DFS supports cycle detection, topological sorting, connected components, strongly connected components, and bridge or articulation-point detection.
Directed cycle test: An edge to a vertex still on the active recursion stack identifies a directed cycle.
Limitation: The first path found may be long or costly; recursion may also overflow the call stack on very deep graphs.

V. Shortest Path Algorithms — Minimum-Cost Routes

A. Shortest path algorithms

Shortest path algorithms calculate paths whose total edge weight is minimal under conditions determined by the graph and its weights.

Distance definition:
TEXT
```
δ(s, v) = minimum Σ w(vi, vi+1)
```
Here, (\delta(s,v)) is the true shortest distance from source (s) to (v), and (w(vi,v{i+1})) is an edge weight.

Relaxation: An edge ((u,v)) improves the current estimate when:

TEXT

if dist[u] + w(u, v) < dist[v]:
    dist[v] = dist[u] + w(u, v)
    parent[v] = u

Initialization: Set dist[s] = 0 and all other distances to (+\infty).
Path reconstruction: Follow parent links backward from the destination to the source, then reverse the sequence.
Negative cycle: A reachable cycle with total weight below zero makes shortest distance undefined because repeated traversal continually lowers the cost.

B. Algorithm selection

The graph’s edge weights and required source coverage determine the suitable algorithm.

Single-source methods: BFS handles unweighted graphs, Dijkstra handles non-negative weights, and Bellman-Ford permits negative weights.
All-pairs method: Floyd-Warshall computes distances between every ordered pair and is especially suitable for dense or moderately sized graphs.

VI. Dijkstra's Algorithm — Greedy Single-Source Paths

A. Dijkstra's algorithm

Dijkstra’s algorithm finds shortest paths from one source when every edge has a non-negative weight.

Greedy choice: Repeatedly finalize the unprocessed vertex (u) with the smallest tentative dist[u].
Correctness condition: Since (w(u,v)\ge 0), a later route cannot reduce the distance of a finalized vertex.
Priority queue: A min-priority queue efficiently retrieves the vertex with minimum tentative distance.

Procedure:

TEXT

Dijkstra(G, s):
    dist[s] = 0; all other dist values = infinity
    insert (0, s) into min-priority queue

    while queue is not empty:
        (d, u) = extract minimum
        if d != dist[u]: continue
        for each edge (u, v) with weight w:
            relax (u, v)
            insert updated (dist[v], v)

Here, (d) is the extracted distance estimate and (w) is the edge weight.

B. Applications and limitations

Dijkstra is efficient for non-negative transport, routing, and network-cost models.

Complexity: With adjacency lists and a binary heap, time is (O((V+E)\log V)), commonly written (O(E\log V)) for connected graphs.
Applications: It supports road navigation, network routing, and minimum-cost transitions where costs cannot be negative.
Limitation: A negative edge can invalidate the greedy finalization step even when the graph has no negative cycle.

VII. Bellman-Ford Algorithm — Repeated Edge Relaxation

A. Bellman-Ford algorithm

Bellman-Ford computes single-source shortest paths with negative edges and detects reachable negative-weight cycles.

Main principle: Relax every edge repeatedly so improvements propagate through paths of increasing length.
Iteration bound: A simple shortest path contains at most (V-1) edges; therefore, (V-1) complete relaxation passes are sufficient.

Procedure:

TEXT

BellmanFord(G, s):
    dist[s] = 0; all other dist values = infinity
    repeat V - 1 times:
        for each edge (u, v) with weight w:
            relax (u, v)

    for each edge (u, v) with weight w:
        if dist[u] + w < dist[v]:
            report reachable negative cycle

Early termination: If a complete pass makes no update, the algorithm may stop because all reachable distances are stable.
Cycle detection: An improvement on the (V)th pass proves that some reachable negative cycle exists.

B. Applications and limitations

Bellman-Ford trades efficiency for broader support and explicit negative-cycle detection.

Complexity: Time is (O(VE)), and distance and parent arrays require (O(V)) space.
Applications: It is appropriate for graphs containing negative adjustments and underlies distance-vector routing concepts.
Limitation: It is substantially slower than Dijkstra on large graphs with non-negative weights.

VIII. Floyd-Warshall Algorithm — All-Pairs Dynamic Programming

A. Floyd-Warshall algorithm

Floyd-Warshall computes shortest-path distances between every pair of vertices using dynamic programming and permits negative edges but not meaningful shortest paths through negative cycles.

State meaning: (D^{(k)}[i][j]) is the shortest distance from (i) to (j) using only vertices (1,\ldots,k) as intermediates.
Recurrence:
TEXT
```
D(k)[i][j] = min(
    D(k-1)[i][j],
    D(k-1)[i][k] + D(k-1)[k][j]
)
```
Here, (i) is the source, (j) the destination, and (k) the newly allowed intermediate vertex.
Initialization: Set (D[i][i]=0), (D[i][j]=w(i,j)) for an edge, and (D[i][j]=+\infty) when no direct edge exists.

In-place procedure:

TEXT

for k = 1 to V:
    for i = 1 to V:
        for j = 1 to V:
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Negative-cycle test: After completion, (D[i][i]<0) indicates a negative cycle involving or reachable through vertex (i).

B. Applications and limitations

Floyd-Warshall is compact and reliable when all-pairs distances are required and the (V\times V) matrix is affordable.

Complexity: The three nested loops take (O(V^3)) time, while the distance matrix requires (O(V^2)) space.
Applications: It supports network-wide route tables, transitive closure, and distance analysis among all locations.
Limitation: Its cubic running time and quadratic storage make it unsuitable for very large sparse graphs.

Unit 6: Graphs

Table of Contents

I. Foundations of Graphs

II. Graph Traversal — Systematic Vertex Exploration

A. Graph traversal

B. Applications and limitations

III. Breadth-First Search — Level-by-Level Exploration

A. Breadth-first search

B. Applications and limitations

IV. Depth-First Search — Branch-Oriented Exploration

A. Depth-first search

B. Applications and limitations

V. Shortest Path Algorithms — Minimum-Cost Routes

A. Shortest path algorithms

B. Algorithm selection

VI. Dijkstra's Algorithm — Greedy Single-Source Paths

A. Dijkstra's algorithm

B. Applications and limitations

VII. Bellman-Ford Algorithm — Repeated Edge Relaxation

A. Bellman-Ford algorithm

B. Applications and limitations

VIII. Floyd-Warshall Algorithm — All-Pairs Dynamic Programming

A. Floyd-Warshall algorithm

B. Applications and limitations

Did this save you a night before the exam?