Unit 4: Graph Algorithms, Network Optimization, and Greedy Technique - Subjective Questions

A graph is a mathematical structure represented as , where is a finite set of vertices and is a set of edges connecting pairs of vertices.

Major types of graphs:

• Undirected graph: Every edge has no direction; an edge is represented by .
• Directed graph: Every edge has a direction and is represented by an ordered pair .
• Weighted graph: Each edge has an associated weight or cost.
• Unweighted graph: All edges are treated as having equal weight.
• Connected graph: A path exists between every pair of vertices.
• Complete graph: Every pair of distinct vertices is connected by an edge.

Basic terminology:

• Degree: Number of edges incident on a vertex.
• Path: A sequence of vertices connected by edges.
• Cycle: A path whose first and last vertices are the same.
• Adjacent vertices: Vertices connected directly by an edge.

Representations:

• Adjacency matrix: A matrix. It requires space and supports constant-time edge lookup.
• Adjacency list: Each vertex stores a list of its neighbors. It requires space and is preferable for sparse graphs.

Breadth-First Search (BFS) traverses a graph level by level, starting from a source vertex. It first visits all vertices at distance one from the source, then those at distance two, and so on.

Data structure: BFS uses a FIFO queue.

Procedure:

1. Mark every vertex as unvisited.
2. Mark the source vertex as visited and insert it into the queue.
3. Remove a vertex from the front of the queue.
4. For every unvisited neighbor of :
   • Mark as visited.
   • Set its predecessor to .
   • Insert into the queue.
5. Continue until the queue becomes empty.

Complexity:

• With an adjacency list, each vertex and edge is processed a constant number of times, so the running time is .
• With an adjacency matrix, all possible neighbors are inspected, giving time.
• The auxiliary space is .

BFS is used for shortest paths in unweighted graphs, level-order exploration, connectivity testing, and bipartite graph checking.

In an unweighted graph, every edge has equal cost. BFS explores vertices in nondecreasing order of the number of edges from a source .

Algorithm:

• Initialize .
• For every other vertex , set .
• Insert into a queue.
• Whenever an unvisited vertex is discovered from , assign
  
  and set .

Correctness argument:

• The queue processes vertices level by level.
• Vertices directly adjacent to are assigned distance before vertices at distance are considered.
• More generally, all vertices with distance are processed before any vertex with distance .
• Therefore, when is first discovered through , the path to has edges.
• If a shorter path existed, BFS would have discovered at an earlier level, which is a contradiction.

Path reconstruction: Starting from a destination vertex, repeatedly follow the parent pointers until is reached. Reversing this sequence gives a shortest path.

The running time using adjacency lists is , and the parent and distance arrays require space.

Depth-First Search (DFS) explores a path as deeply as possible before backtracking to explore another path.

Recursive procedure:

1. Mark the current vertex as visited.
2. Record its discovery time.
3. Recursively visit every unvisited neighbor of .
4. After all neighbors have been processed, record the finishing time of .

A simplified recurrence-style procedure is:

• Set .
• For each adjacent to , call DFS on if it is unvisited.

Timestamps:

• The discovery time is recorded when is first reached.
• The finishing time is recorded after all descendants of have been processed.
• These times help classify edges and are used in topological sorting and strongly connected component algorithms.

Complexity:

• With adjacency lists: time.
• With an adjacency matrix: time.
• The visited array and recursion stack require up to space.

DFS is used for cycle detection, connected components, topological sorting, path finding, and articulation-point analysis.

BFS and DFS differ as follows:

• Traversal order: BFS explores the graph level by level, whereas DFS explores one branch deeply before backtracking.
• Primary data structure: BFS uses a FIFO queue; DFS uses a stack or recursion.
• Shortest paths: BFS guarantees shortest paths in an unweighted graph. DFS does not generally provide shortest paths.
• Memory behavior: BFS may store an entire frontier and can require substantial memory in wide graphs. DFS mainly stores the current path and recursion information.
• Typical applications: BFS is useful for shortest unweighted paths, broadcasting, and level computation. DFS is useful for cycle detection, topological sorting, connected components, and structural analysis.
• Time complexity: Both take time when adjacency lists are used.
• Space complexity: Both may require auxiliary space in the worst case.

Thus, BFS is preferred when minimum edge distance is important, while DFS is preferred for exploring graph structure and dependency relations.

Finding connected components:

• Mark every vertex as unvisited.
• Select an unvisited vertex and perform DFS from it.
• All vertices reached by that DFS belong to one connected component.
• Repeat from another unvisited vertex.
• The number of DFS initiations equals the number of connected components.

Cycle detection in an undirected graph:

• During DFS, store the parent of each vertex.
• If an edge leads to a previously visited vertex and is not the parent of , the graph contains a cycle.
• The parent check is necessary because the edge back to the parent is expected in an undirected graph.

Cycle detection in a directed graph:

• Maintain three states: unvisited, active, and finished.
• Mark a vertex active when its DFS begins.
• If DFS encounters an edge from an active vertex to another active vertex, it has found a back edge and hence a directed cycle.
• Mark a vertex finished after all outgoing edges are processed.

Each method runs in time with adjacency lists and uses auxiliary space.

A topological ordering of a directed graph is a linear arrangement of its vertices such that for every directed edge , vertex appears before . Such an ordering exists only for a directed acyclic graph (DAG).

DFS-based method:

1. Perform DFS on every unvisited vertex.
2. After all outgoing neighbors of a vertex are processed, push the vertex onto a stack.
3. Pop all vertices from the stack to obtain the topological order.
4. A back edge detected during DFS indicates a cycle, so no topological order exists.

Kahn's algorithm:

1. Compute the in-degree of every vertex.
2. Insert all vertices with in-degree zero into a queue.
3. Remove a vertex , add it to the ordering, and delete its outgoing edges conceptually.
4. Decrease the in-degree of each neighbor.
5. Insert a neighbor when its in-degree becomes zero.
6. If fewer than vertices are processed, the graph contains a cycle.

Both algorithms run in time and require auxiliary space when adjacency lists are used.

A topological ordering exists if and only if the graph is a directed acyclic graph (DAG).

Reason:

• If the graph contains a directed cycle, every vertex on the cycle would have to appear before itself through the dependency chain, which is impossible.
• If the graph is acyclic, either DFS finishing times or repeated removal of zero-in-degree vertices produces a valid ordering.

Uniqueness condition using Kahn's algorithm:

• At every step, there must be exactly one vertex with in-degree zero.
• If two or more zero-in-degree vertices are available at some step, different choices can produce different valid topological orders.

An equivalent condition is that every pair of consecutive vertices in the produced order must be connected by a directed edge in the required direction. If this condition holds throughout, the order is unique.

Topological sorting is commonly used in task scheduling, course prerequisite planning, build systems, and dependency resolution.

The greedy approach constructs a solution incrementally by making the locally optimal feasible choice at each step. Once a choice is made, it is usually not reconsidered.

A problem is suitable for a greedy algorithm when it has:

• Greedy-choice property: A globally optimal solution can be obtained by making a locally optimal first choice.
• Optimal substructure: After making a choice, the remaining problem has an optimal solution that forms part of the overall optimum.

General design steps:

1. Identify the set of candidate elements.
2. Define a selection function to choose the best candidate.
3. Test whether adding that candidate keeps the partial solution feasible.
4. Add the candidate if it is feasible.
5. Repeat until a complete solution is obtained.

Greedy algorithms are often efficient because they avoid examining all combinations. Examples include fractional knapsack, Prim's algorithm, Kruskal's algorithm, and Dijkstra's algorithm for nonnegative edge weights. However, a greedy rule must be proved correct because a locally optimal choice does not always produce a global optimum.

Exchange argument:

• Begin with an arbitrary optimal solution .
• Compare its first choice with the choice made by the greedy algorithm.
• Show that the element chosen by can be replaced by without reducing solution quality or violating feasibility.
• The modified optimal solution now begins with the greedy choice.
• Repeat the exchange for later choices until the optimal solution is transformed into the greedy solution.
• Therefore, the greedy solution is also optimal.

Stays-ahead argument:

• Compare the greedy partial solution with any competing solution after each decision.
• Prove that the greedy solution is at least as good at the first step.
• Use induction to show that it remains at least as good after every subsequent step.
• Consequently, the final greedy solution is no worse than any alternative.

The exchange argument is common in activity selection and spanning-tree proofs, while the stays-ahead method is useful when solutions can be compared through cumulative progress.

In the fractional knapsack problem, any fraction of an item may be selected. For each item , compute its profit-to-weight ratio:

Then sort the items in nonincreasing order of and take as much as possible from each item.

Ratios for the given items:

• Item 1:
• Item 2:
• Item 3:

The order is Item 1, Item 2, Item 3.

Selection:

• Take all of Item 1: weight , profit .
• Take all of Item 2: weight , profit .
• Remaining capacity is .
• Take of Item 3, giving profit
  

Therefore, the maximum profit is

Sorting takes time, and scanning the sorted items takes time. The greedy method is optimal because replacing lower-ratio weight with higher-ratio weight can never decrease profit.

Fractional knapsack:

• Fractions of items may be selected.
• The ratio-based greedy algorithm is optimal.
• It can be solved in time through sorting.

knapsack:

• Each item must be either selected completely or rejected.
• Fractions are not allowed.
• A profit-to-weight greedy rule is not always optimal.
• Dynamic programming is commonly used, with pseudopolynomial complexity for integer capacity .

Counterexample: Consider capacity and items .

The ratios are , , and . Ratio-based greedy selection takes the first two items, using weight and earning profit . The third item cannot fit in the remaining capacity .

However, selecting the second and third items uses weight

and gives profit

Thus, the greedy result is less than the optimal result . The failure occurs because an indivisible high-ratio item can prevent a better combination of lower-ratio items.

For a connected, undirected, weighted graph , a spanning tree connects all vertices, contains no cycle, and has exactly edges. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight.

Cut property:

• A cut partitions into two nonempty sets and .
• An edge crosses the cut if its endpoints lie in different sets.
• A minimum-weight edge crossing a cut is safe for some MST, provided the cut respects the edges already selected.
• Prim's and Kruskal's algorithms rely mainly on this property.

Cycle property:

• In any cycle, an edge whose weight is strictly greater than all other edges in that cycle cannot belong to an MST.
• Removing the heaviest edge keeps the vertices connected and reduces the total weight.

If edge weights are all distinct, the MST is unique. With repeated weights, multiple MSTs may exist, but all have the same minimum total weight.

Prim's algorithm grows one tree from an arbitrary starting vertex.

Algorithm:

1. Select any source vertex .
2. Set and for every other vertex.
3. Store all vertices in a min-priority queue ordered by key value.
4. Extract the vertex with minimum key.
5. For every adjacent vertex still outside the tree, if :
   • Set .
   • Set .
6. Continue until every vertex has been extracted.
7. The edges form the MST.

Correctness: At each step, the vertices already selected and those not yet selected define a cut. Prim's algorithm chooses a minimum-weight edge crossing that cut. By the cut property, this edge is safe for an MST.

Complexity:

• Adjacency matrix and linear search: .
• Adjacency list with binary heap: .
• Fibonacci heap: .

Prim's algorithm requires a connected graph to produce one MST; otherwise, it can be restarted to generate a minimum spanning forest.

Kruskal's algorithm builds a minimum spanning tree by considering edges globally in increasing order of weight.

Algorithm:

1. Sort all edges in nondecreasing order of weight.
2. Initially place each vertex in a separate set.
3. Process edges one by one in sorted order.
4. For an edge , add it if and belong to different components.
5. Merge the two components after accepting the edge.
6. Stop after selecting edges.

Disjoint-set operations:

• Make-Set(v) creates a separate set for vertex .
• Find(v) identifies the representative of the component containing .
• Union(u,v) merges two different components.

Path compression in Find and union by rank or size make these operations nearly constant in amortized time.

Correctness: The selected edge is the lightest edge connecting two current components. It is safe by the cut property. Rejecting edges whose endpoints are already connected prevents cycles.

Sorting dominates the running time, so the overall complexity is , which is equivalent to for ordinary simple graphs.

Prim's algorithm:

• Grows a single tree from a selected starting vertex.
• Chooses the lightest edge connecting the current tree to an outside vertex.
• Commonly uses a priority queue.
• With a binary heap, its complexity is .
• It is often effective for dense graphs, especially with an adjacency-matrix implementation taking time.

Kruskal's algorithm:

• Starts with a forest of individual vertices.
• Chooses the globally lightest edge that does not form a cycle.
• Uses edge sorting and a disjoint-set structure.
• Its complexity is .
• It is often convenient for sparse graphs or when the graph is already represented as an edge list.

Similarities:

• Both are greedy algorithms.
• Both use the cut property to establish correctness.
• Both produce an MST for a connected, undirected, weighted graph.
• If the graph is disconnected, suitable implementations produce a minimum spanning forest.

Dijkstra's algorithm computes shortest-path distances from a source in a weighted graph whose edge weights are nonnegative.

Algorithm:

1. Set and for all .
2. Insert vertices into a min-priority queue according to their tentative distances.
3. Extract the vertex with minimum tentative distance.
4. For each outgoing edge with weight , perform relaxation:
   
5. Record as the predecessor of whenever relaxation succeeds.
6. Continue until the queue is empty.

Correctness idea: With nonnegative weights, once has the smallest tentative distance, no later path through an unprocessed vertex can reduce . Hence, its distance may be finalized safely.

Why negative weights are invalid: A vertex finalized earlier may later be reached through a negative-weight edge with a smaller distance, contradicting the greedy decision.

Complexity:

• Array or matrix implementation: .
• Binary heap with adjacency lists: , commonly written for connected graphs.

The Bellman-Ford algorithm computes single-source shortest paths even when some edges have negative weights, provided no reachable negative-weight cycle exists.

Algorithm:

1. Initialize and for every .
2. Repeat the following process times:
   • For every edge of weight , relax it using
     
3. Perform one additional pass over all edges.
4. If any distance can still be reduced, a negative-weight cycle is reachable from the source.

Why passes are sufficient: Any simple shortest path contains at most edges. After the -th pass, shortest paths using at most edges have been correctly considered.

Negative-cycle detection: A further improvement after passes implies that a beneficial walk uses at least edges and therefore repeats a vertex. The repeated section is a negative-weight cycle.

The running time is and the auxiliary space is . Early termination is possible if an entire pass performs no relaxation.

Floyd-Warshall computes shortest-path distances between every pair of vertices. It supports negative edge weights but assumes there is no negative-weight cycle.

Let denote the shortest distance from to when only vertices may be used as intermediate vertices.

The shortest path either does not use vertex , or it passes through . Therefore,

Initialization:

• .
• if edge exists.
• Otherwise, .

Iteration: For to , update every pair using

Complexity:

• Time: .
• Space: .

A negative-weight cycle exists if some diagonal entry becomes negative, that is, . A predecessor or next matrix may also be maintained to reconstruct actual shortest paths.

BFS:

• Used for unweighted graphs or graphs in which every edge has the same cost.
• Computes single-source distances in time.

Dijkstra's algorithm:

• Used for weighted graphs with no negative edge weights.
• With a binary heap, it takes time.
• Running it from every vertex gives an all-pairs solution suitable for sparse nonnegative graphs.

Bellman-Ford algorithm:

• Handles negative edge weights.
• Detects reachable negative-weight cycles.
• Takes time for one source.

Floyd-Warshall algorithm:

• Directly computes all-pairs shortest paths.
• Supports negative edges but not negative-weight cycles.
• Takes time and space.
• It is simple and effective for dense graphs or moderate values of .

Selection guideline:

• Use BFS for unweighted graphs.
• Use Dijkstra for nonnegative sparse weighted graphs.
• Use Bellman-Ford when negative edges or cycle detection are important.
• Use Floyd-Warshall when all-pairs distances are required and cubic time is acceptable.