Unit 4: Graph Algorithms, Network Optimization, and Greedy Technique

I. Foundations of Graph Algorithms

A graph is a mathematical structure used to represent pairwise relationships among objects. Graph algorithms operate on vertices and edges to solve reachability, ordering, connectivity, routing, and network-optimization problems.

• Basic model: A graph is written as (G=(V,E)), where (V) is the set of vertices and (E) is the set of edges.
• Graph size: The number of vertices is (n=|V|), while the number of edges is (m=|E|).
• Core conventions:
  • A directed edge is an ordered pair ((u,v)).
  • An undirected edge is an unordered pair ({u,v}).
  • A weighted edge has a numerical cost (w(u,v)).
• Algorithmic objective: Efficient graph algorithms usually aim for polynomial or linear dependence on (n) and (m).

A. Introduction to Graphs

Graphs model systems such as road networks, communication links, task dependencies, and social relationships.

• Graph categories:
  • Directed graph: Edges have direction; ((u,v)) does not imply ((v,u)).
  • Undirected graph: Every edge may be traversed in both directions.
  • Weighted graph: Each edge (e) has weight (w(e)), such as distance or cost.
  • Simple graph: Contains neither self-loops nor parallel edges.
• Important terminology:
  • Path: A sequence (v_0,v_1,\ldots,v_k) with an edge between consecutive vertices.
  • Cycle: A path whose first and last vertices are identical.
  • Connected graph: Every pair of vertices in an undirected graph has a path between them.
  • Degree: The number of incident edges; directed graphs distinguish in-degree and out-degree.
• Representations:
  1. Adjacency matrix: An (n\times n) matrix; testing whether an edge exists takes (O(1)), but storage is (O(n^2)).
  2. Adjacency list: Stores each vertex’s neighbors; storage is (O(n+m)), making it preferable for sparse graphs.

II. Layer-by-Layer Graph Traversal

A. Breadth-First Search (BFS)

BFS explores a graph in increasing order of distance, measured by the number of edges from a source vertex.

• Principle: A first-in, first-out queue ensures that all vertices at distance (k) are processed before those at distance (k+1).
• Procedure:

BFS(G, s):
    mark s visited; distance[s] = 0
    enqueue(Q, s)
    while Q is not empty:
        u = dequeue(Q)
        for each v in Adj[u]:
            if v is unvisited:
                mark v visited
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(Q, v)

Here, (G) is the graph, (s) is the source, (Q) is a queue, and Adj[u] contains (u)'s neighbors.

• Complexity: With adjacency lists, each vertex and edge is examined a constant number of times, giving (O(n+m)) time and (O(n)) auxiliary space.
• Uses: BFS finds shortest paths in unweighted graphs, connected components, bipartite conflicts, and vertices reachable from (s).

III. Depth-Oriented Graph Traversal

A. Depth-First Search (DFS)

DFS follows one path as deeply as possible before backtracking to explore alternatives.

• Principle: DFS uses recursion or an explicit last-in, first-out stack.
• Procedure:

DFS-Visit(G, u):
    mark u visited
    for each v in Adj[u]:
        if v is unvisited:
            parent[v] = u
            DFS-Visit(G, v)
    mark u finished

Here, (u) is the current vertex and parent[v] records the DFS tree edge used to discover (v).

• DFS forest: Calling DFS-Visit from every still-unvisited vertex produces one tree per connected or reachable component.
• Timing information: Discovery and finishing times classify directed edges and support cycle detection and topological sorting.
• Complexity: Adjacency-list DFS requires (O(n+m)) time and (O(n)) space, including the recursion stack.
• Uses: DFS supports connected-component analysis, articulation-point detection, strongly connected components, and maze traversal.

IV. Ordering Directed Dependencies

A. Topological Sort

A topological ordering is a linear arrangement of the vertices of a directed acyclic graph (DAG) such that every edge ((u,v)) places (u) before (v).

• Existence condition: A topological order exists if and only if the directed graph contains no cycle.
• DFS method: Insert each vertex at the front of a list when DFS finishes it; reverse finishing-time order is topological.
• Kahn’s method:
  • Compute every vertex’s in-degree.
  • Repeatedly remove an in-degree-zero vertex.
  • Decrease the in-degree of each outgoing neighbor.
• Cycle test: If Kahn’s method outputs fewer than (n) vertices, the graph contains a directed cycle.
• Complexity: Both methods run in (O(n+m)) time with adjacency lists.
• Applications: Topological sorting orders courses with prerequisites, compilation stages, project tasks, and spreadsheet dependencies.

V. Local Choices in Algorithm Design

A. Introduction to Greedy Approach

A greedy algorithm constructs a solution incrementally by selecting the locally best feasible choice at each step.

• Choice rule: The selected option is irrevocable; earlier decisions are normally not reconsidered.
• Correctness requirements:
  • Greedy-choice property: Some optimal solution begins with the locally optimal choice.
  • Optimal substructure: After making that choice, the remaining problem has an optimal solution within the original optimum.
• Proof methods:
  • Exchange argument: Replace part of an optimal solution with the greedy choice without worsening its value.
  • Stays-ahead argument: Show that every greedy prefix is at least as good as any competing prefix.
• Advantages: Greedy methods are often simple, fast, and memory-efficient.
• Limitation: A locally optimal decision need not produce a global optimum; correctness must be established for each problem.

VI. Resource Allocation under Capacity Constraints

A. Knapsack Problem

The knapsack problem chooses items with weights (w_i) and profits (p_i) without exceeding capacity (W).

• Mathematical objective:

maximize   Σ p_i x_i
subject to Σ w_i x_i ≤ W

Here, (x_i) indicates the amount of item (i) selected.

1. Fractional knapsack:
   • Condition: Fractions are allowed, so (0\leq x_i\leq1).
   • Greedy rule: Sort by decreasing ratio (p_i/w_i), then take as much as possible.
   • Complexity: Sorting dominates, giving (O(n\log n)) time.
2. 0/1 knapsack:
   • Condition: Each (x_i\in{0,1}); items cannot be divided.
   • Greedy failure: The largest profit-to-weight ratio may block a more valuable combination.
   • Dynamic programming: Let (K[i,c]) be the maximum profit using the first (i) items and capacity (c):

K[i,c] = max(K[i-1,c], p_i + K[i-1,c-w_i])

• Complexity distinction: The dynamic program takes (O(nW)) time, which is pseudo-polynomial because it depends on numeric capacity (W).

VII. Minimum-Cost Network Connectivity

A. Minimum Spanning Trees

A minimum spanning tree (MST) of a connected, undirected, weighted graph is a spanning tree having minimum total edge weight.

• Tree properties: A spanning tree connects all (n) vertices, contains exactly (n-1) edges, and has no cycle.
• Objective:

minimize Σ w(e), for all edges e selected in T

Here, (T) is a spanning tree and (w(e)) is edge (e)'s weight.

• Cut property: A minimum-weight edge crossing any cut is safe for an MST, subject to ties.
• Cycle property: A uniquely heaviest edge on a cycle cannot belong to an MST.
• Uniqueness: Distinct edge weights guarantee a unique MST; equal weights may permit several MSTs with the same cost.
• Applications: MSTs minimize cable, pipeline, road, or communication-network construction costs.

VIII. Vertex-Growing MST Construction

A. Prim's Algorithm

Prim’s algorithm grows one tree by repeatedly adding the cheapest edge connecting the current tree to an outside vertex.

• State: key[v] is the least known weight connecting (v) to the tree, and parent[v] identifies that edge.
• Procedure:

set key[s] = 0; all other keys = ∞
place all vertices in a min-priority queue
while the queue is not empty:
    u = extract-min()
    for each edge (u,v) with v still in the queue:
        if w(u,v) < key[v]:
            key[v] = w(u,v)
            parent[v] = u

Here, (s) is an arbitrary starting vertex.

• Correctness: Each extracted edge is a light edge crossing the cut between selected and unselected vertices.
• Complexity: A binary heap with adjacency lists gives (O(m\log n)); an adjacency matrix gives (O(n^2)), useful for dense graphs.
• Limitation: A disconnected graph produces a minimum spanning forest rather than one spanning tree.

IX. Edge-Growing MST Construction

A. Kruskal's Algorithm

Kruskal’s algorithm builds an MST by considering edges globally in nondecreasing order of weight.

• Procedure:

sort edges by nondecreasing weight
make a separate set for every vertex
for each edge (u,v) in sorted order:
    if Find(u) ≠ Find(v):
        add (u,v) to T
        Union(u,v)

Here, (T) is the selected edge set; Find identifies components and Union merges them.

• Cycle prevention: Disjoint-set union with path compression and union by rank efficiently rejects edges whose endpoints are already connected.
• Correctness: The next accepted edge is a safe minimum-weight edge crossing a cut between two current components.
• Complexity: Sorting requires (O(m\log m)), equivalent to (O(m\log n)) for simple graphs; disjoint-set operations are nearly constant amortized time.
• Comparison with Prim: Prim grows one connected tree, whereas Kruskal grows and merges several components.

X. Shortest Routes from One Source

A. Single-Source Shortest Paths

The single-source shortest-path problem computes minimum path distances (\delta(s,v)) from source (s) to every reachable vertex (v).

• Relaxation: For edge ((u,v)), update the current estimate when a shorter route is found:

if d[v] > d[u] + w(u,v):
    d[v] = d[u] + w(u,v)
    parent[v] = u

Here, (d[v]) is the estimated distance and (w(u,v)) is the edge weight.

1. Dijkstra’s algorithm:
   • Requires all edge weights to be nonnegative.
   • Repeatedly finalizes the vertex with minimum tentative distance.
   • Runs in (O((n+m)\log n)) with a binary heap.
2. Bellman–Ford algorithm:
   • Permits negative edge weights.
   • Relaxes every edge (n-1) times, giving (O(nm)) time.
   • A further successful relaxation reveals a reachable negative-weight cycle.
   • Special case: For unweighted graphs, BFS computes shortest distances in (O(n+m)).

XI. Shortest Routes between Every Pair

A. All-Pairs Shortest Paths

The all-pairs shortest-path problem determines the minimum distance between every ordered pair of vertices.

• Floyd–Warshall principle: Dynamic programming gradually permits vertices (1,\ldots,k) as intermediate points.
• Recurrence:

D[i,j] = min(D[i,j], D[i,k] + D[k,j])

Here, (D[i,j]) is the best known distance from (i) to (j), and (k) is 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.
• Complexity: Three nested vertex loops require (O(n^3)) time and the distance matrix requires (O(n^2)) space.
• Negative weights: Negative edges are allowed, but negative cycles invalidate finite shortest paths; after execution, (D[i,i]<0) indicates such a cycle.
• Alternative strategy: Repeating Dijkstra’s algorithm is often faster on sparse graphs with nonnegative weights, while Floyd–Warshall is simple and effective for dense graphs.