Unit 6: Graphs - Subjective Questions

A graph is a non-linear data structure represented as , where is a finite set of vertices and is a set of edges connecting pairs of vertices.

• Vertex: A fundamental node or point in the graph.
• Edge: A connection between two vertices. An edge may be directed or undirected.
• Degree: In an undirected graph, the degree of a vertex is the number of edges incident on it. In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.
• Path: A sequence of vertices in which each consecutive pair is connected by an edge.
• Cycle: A path that begins and ends at the same vertex without repeating intermediate vertices.
• Connected component: A maximal set of vertices such that a path exists between every pair of vertices in the set.

Graphs are used to model networks, routes, dependencies, social relationships, and many other real-world systems.

The two common representations of a graph are:

Adjacency matrix:

• Uses a matrix.
• Entry indicates whether an edge exists from vertex to vertex .
• Requires space.
• Checking whether a particular edge exists takes time.
• It is suitable for dense graphs.

Adjacency list:

• Stores a list of neighboring vertices for every vertex.
• Requires space.
• Checking a particular edge may take time.
• Iterating over the neighbors of a vertex is efficient.
• It is suitable for sparse graphs.

Therefore, an adjacency matrix provides fast edge lookup, while an adjacency list generally uses less memory and is more efficient for graph traversal.

Graph traversal is the systematic process of visiting the vertices of a graph. The two principal traversal methods are Breadth-First Search (BFS) and Depth-First Search (DFS).

A visited array or set is required because:

• A graph can contain cycles.
• A vertex may be reachable through multiple paths.
• Without marking vertices, an algorithm may process the same vertex repeatedly.
• In a cyclic graph, failure to track visited vertices can cause an infinite loop or infinite recursion.

Initially, every vertex is marked unvisited. When a vertex is discovered, it is marked visited before its neighbors are explored. For a disconnected graph, traversal must be initiated from every vertex that remains unvisited. This ensures that all connected components are covered.

With an adjacency-list representation, both BFS and DFS take time.

Breadth-First Search (BFS) visits vertices level by level from a chosen source vertex. It uses a queue.

Pseudocode:

1. Mark every vertex as unvisited.
2. Mark source as visited and enqueue it.
3. While the queue is not empty:
   • Dequeue a vertex .
   • Process .
   • For every neighbor of , if is unvisited, mark it visited and enqueue it.

Correctness idea: The queue processes vertices in nondecreasing order of their number of edges from the source. Therefore, vertices at distance are processed before vertices at distance .

Complexity:

• With an adjacency list, each vertex is enqueued once and each edge is inspected at most twice in an undirected graph. Time complexity is .
• The visited array, queue, and optional parent array require auxiliary space.
• With an adjacency matrix, the time complexity is .

In an unweighted graph, every edge has equal cost, normally treated as . BFS explores vertices in increasing order of the number of edges from the source.

Maintain the following arrays:

• for the source.
• for every other vertex.
• records the vertex from which was first discovered.

When BFS discovers an unvisited neighbor from , it assigns:

and

The first time is reached, BFS has found a path containing the minimum possible number of edges. To reconstruct the shortest path from to a target , repeatedly follow until is reached, then reverse the resulting sequence.

BFS does not directly solve weighted shortest-path problems unless all edges have the same weight.

Depth-First Search (DFS) explores one path as deeply as possible before backtracking.

Recursive approach:

1. Mark the current vertex as visited.
2. Process .
3. For each neighbor of , recursively call DFS on if it is unvisited.

The programming-language call stack performs the backtracking.

Iterative approach:

1. Push the source vertex onto an explicit stack.
2. Repeatedly pop a vertex.
3. If it has not been visited, mark and process it.
4. Push its unvisited neighbors onto the stack.

The exact visitation order may differ between recursive and iterative DFS depending on the order in which neighbors are pushed.

Complexity:

• With an adjacency list, the running time is .
• With an adjacency matrix, it is .
• The visited array and recursion or explicit stack require auxiliary space in the worst case.

BFS and DFS differ as follows:

• Traversal strategy: BFS explores vertices level by level, whereas DFS follows a path deeply before backtracking.
• Primary data structure: BFS uses a queue, whereas DFS uses a stack or recursion.
• Shortest path: BFS finds a shortest path by number of edges in an unweighted graph. DFS does not guarantee a shortest path.
• Memory behavior: BFS may store an entire frontier and can require substantial memory in wide graphs. DFS mainly stores the current search path and pending branches.
• Applications of BFS: Unweighted shortest paths, level-order exploration, bipartite testing, and network broadcasting.
• Applications of DFS: Cycle detection, topological sorting, connected components, strongly connected components, and backtracking.
• Complexity: With adjacency lists, both require time and up to auxiliary space.

The appropriate traversal depends on whether level information, shortest unweighted paths, or deep structural exploration is required.

For an undirected graph, DFS records the parent of each vertex. While examining an edge :

• If is unvisited, DFS continues from with as its parent.
• If is already visited and is not the parent of , a cycle exists.

The parent check is necessary because the edge back to the parent is expected in an undirected graph.

For a directed graph, maintain three states:

• Unvisited: The vertex has not been discovered.
• Active: The vertex is currently in the DFS recursion stack.
• Finished: All outgoing edges of the vertex have been explored.

An edge from an active vertex to another active vertex is a back edge and proves that a directed cycle exists. Encountering a finished vertex does not imply a cycle.

Both methods run in time with an adjacency list and use auxiliary space.

A connected component is a maximal group of vertices in which every pair of vertices is joined by some path.

To identify all connected components:

1. Initialize every vertex as unvisited.
2. Examine the vertices one by one.
3. Whenever an unvisited vertex is found, start BFS or DFS from .
4. All vertices reached during that traversal belong to one connected component.
5. Increment the component count and continue scanning for another unvisited vertex.

A component identifier may be assigned to every discovered vertex so that later queries can determine whether two vertices belong to the same component.

Correctness: A traversal from reaches every vertex connected to and cannot cross into a different component because no connecting edge exists.

Using an adjacency list, the complete procedure takes time and auxiliary space.

The single-source shortest-path problem asks for the minimum path cost from a source vertex to every other vertex in a weighted graph .

The distance estimate is initialized as:

For an edge with weight , relaxation tests whether reaching through improves the current estimate:

The predecessor is also updated:

Relaxation progressively establishes tighter upper bounds on shortest-path distances. If no negative cycle is reachable from the source, shortest-path algorithms perform relaxation in an order or number sufficient to obtain the final distances. The parent links form a shortest-path tree and permit path reconstruction.

Dijkstra's algorithm computes single-source shortest paths in a weighted graph whose edge weights are nonnegative.

Algorithm:

1. Set and all other distances to .
2. Insert vertices into a min-priority queue keyed by distance.
3. Extract the vertex with minimum tentative distance.
4. For each edge , relax the edge.
5. If decreases, update the priority of .
6. Continue until the queue is empty.

Correctness condition: Since every edge weight is nonnegative, any later route to the extracted minimum vertex cannot make its distance smaller. Thus, when is extracted, is final.

Complexity:

• Binary heap with adjacency list: , commonly written as for a connected graph.
• Array with adjacency matrix: .
• Fibonacci heap: amortized.

The algorithm is not correct in general when negative-weight edges are present.

Initialize:

Iteration 1: extract

• Relax : , .
• Relax : , .

Iteration 2: extract with distance

• Relax : , so and .
• Relax : and .

Iteration 3: extract with distance

• Relax : , so and .

Iteration 4: extract with distance

• Relax : and .

The final results are:

• : path .
• : path .
• : path .
• : path .
• : path .

Dijkstra's algorithm assumes that once the unprocessed vertex with the smallest tentative distance is selected, its distance cannot later decrease. This assumption depends on all edge weights being nonnegative.

Consider these directed edges:

• has weight .
• has weight .
• has weight .

Initially, Dijkstra assigns and . It selects first and may finalize its distance as . However, after processing , the path

has cost

which is shorter than . Thus, the previously finalized distance is incorrect under the usual implementation that does not reopen finalized vertices.

A negative edge can therefore create a cheaper route through a vertex processed later. Bellman-Ford should be used when negative-weight edges may exist because it repeatedly relaxes every edge.

Bellman-Ford computes single-source shortest paths even when some edge weights are negative.

Algorithm:

1. Initialize and for every .
2. Repeat times:
   • For every edge , relax .
3. Perform one additional pass over all edges.
4. If any reachable edge can still be relaxed, report a reachable negative-weight cycle.

A simple shortest path in a graph with vertices contains at most edges. After the first full pass, shortest paths using at most one edge can be established; after the second, paths using at most two edges can be established. Therefore, passes are sufficient when no reachable negative cycle exists.

If a distance decreases during the extra pass, the path can be improved beyond edges. Such an improvement must involve a cycle, and the improving cycle has negative total weight.

The time complexity is and the auxiliary space complexity is .

Initialize the distances:

Assume the edges are processed in the order listed.

First pass:

• : .
• : .
• : , so .
• : .
• : , so .

At the end of the first pass:

Subsequent passes: No edge produces a smaller value, so the algorithm may terminate early.

The shortest paths are:

• To : , with cost .
• To : , with cost .
• To : , with cost .

An additional pass causes no update, so no reachable negative-weight cycle exists.

Dijkstra's algorithm:

• Requires all edge weights to be nonnegative.
• Greedily finalizes the vertex with the smallest tentative distance.
• Commonly uses a min-priority queue.
• Runs in with an adjacency list and binary heap.
• Does not generally detect negative-weight cycles.

Bellman-Ford algorithm:

• Supports negative-weight edges.
• Repeatedly relaxes every edge.
• Detects a negative-weight cycle reachable from the source.
• Runs in time.
• Can stop early if a complete pass performs no update.

Common features:

• Both solve the single-source shortest-path problem.
• Both use relaxation and can maintain parent pointers for path reconstruction.
• Both use auxiliary storage apart from the graph representation.

Dijkstra is preferred for efficiency when weights are nonnegative. Bellman-Ford is preferred when negative edges or negative-cycle detection must be supported.

Floyd-Warshall computes shortest-path distances between every pair of vertices in a weighted graph. It supports negative edges but requires that no relevant negative-weight cycle exist.

Let be the shortest distance from to whose intermediate vertices are selected only from .

For vertex , a shortest path from to either:

• Does not use as an intermediate vertex, giving ; or
• Uses , giving .

Therefore:

Initialization uses , direct edge weights for existing edges, and otherwise. The implementation updates the matrix in place using three nested loops, with as the outermost loop.

The time complexity is and the space complexity is .

The vertices are ordered as .

Initial direct distances are:

Using vertex as an intermediate vertex produces no improvement.

Using vertex :

• The path has cost , so .
• The path has cost , so .

The matrix becomes:

Using vertex produces no further improvement. Therefore, the final all-pairs shortest-path matrix is:

For example, the shortest path from vertex to vertex is with total cost , and the shortest path from vertex to vertex is with total cost .

Floyd-Warshall initializes every diagonal entry as . After completing the algorithm, inspect the diagonal entries.

If

for any vertex , the graph contains a negative-weight cycle reachable from and able to return to . The negative diagonal value means that traveling from through a cycle and back to costs less than zero.

A negative cycle makes certain shortest paths undefined. If a path from can reach the negative cycle and the cycle can reach , the cycle can be repeated arbitrarily many times before proceeding to . The path cost can then be reduced without bound:

Thus, Floyd-Warshall can detect negative cycles by checking its diagonal, but a basic distance matrix alone does not automatically mark every affected pair. Additional reachability checks are needed to identify all pairs whose distances are unbounded below.

BFS:

• Problem: Single-source shortest paths in an unweighted graph or a graph with equal edge weights.
• Negative weights: Not applicable.
• Complexity: .

Dijkstra:

• Problem: Single-source shortest paths in a weighted graph.
• Negative weights: Not supported.
• Complexity: with a binary heap.

Bellman-Ford:

• Problem: Single-source shortest paths with possible negative edges.
• Negative weights: Supported.
• Negative-cycle detection: Supported for cycles reachable from the source.
• Complexity: .

Floyd-Warshall:

• Problem: All-pairs shortest paths.
• Negative weights: Supported.
• Negative-cycle detection: Supported through negative diagonal entries.
• Complexity: and space .

Use BFS for unweighted graphs, Dijkstra for nonnegative weighted graphs, Bellman-Ford when negative edges may occur, and Floyd-Warshall when distances between all pairs are required and the graph size permits cubic running time.