7. Graph and Network Algorithms

Introduction and Context

Many computational problems are naturally expressed not as sequences of isolated operations but as relationships among objects. A road system connects locations, a communication network links devices, a social platform relates users, and a software project contains dependencies among tasks. Graphs provide a general mathematical language for representing such relationships. Graph algorithms then offer systematic procedures for exploring structure, discovering reachability, optimizing routes, constructing efficient networks, scheduling dependent activities, and allocating scarce capacity.

For artificial intelligence and machine learning professionals, graphs are especially important. Knowledge graphs represent entities and relations; recommendation systems model users and items as interacting networks; fraud detection examines suspicious transaction structures; neural architectures increasingly operate on graph-structured data; and logistics platforms use shortest-path, matching, and flow algorithms. The quality of an intelligent system often depends not only on its predictive model but also on how accurately its underlying graph is represented and analyzed.

This chapter develops the principal graph and network algorithms used in algorithm design. It begins with graph representations and traversal, then examines connectivity and topological ordering, shortest paths, minimum spanning trees, matching, and maximum flow. Alongside algorithmic procedures, attention is given to correctness, complexity, implementation choices, modeling assumptions, and professional applications.

Learning Objectives

After studying this chapter, a student should be able to:

1. Define directed and undirected graphs, weighted graphs, paths, cycles, connectivity, and related concepts.

2. Select suitable adjacency-list or adjacency-matrix representations according to graph density and operation requirements.

3. Apply breadth-first search and depth-first search to traversal, reachability, cycle detection, and component analysis.

4. Explain and use topological sorting in dependency systems.

5. Select appropriate shortest-path algorithms, including breadth-first search, Dijkstra’s algorithm, Bellman–Ford, and Floyd–Warshall.

6. Construct minimum spanning trees using Kruskal’s and Prim’s algorithms.

7. Explain the foundations of bipartite matching and maximum-flow algorithms.

8. Analyze time and space complexity and recognize assumptions that affect algorithmic validity.

9. Relate graph algorithms to logistics, recommendation, infrastructure, scheduling, and AI systems.

10. Evaluate practical, ethical, and governance issues in network-based decision systems.

1. Graphs as Models of Relationships

A graph is a pair G = (V, E), where V is a set of vertices, or nodes, and E is a set of edges connecting pairs of vertices. In an undirected graph, an edge {u, v} has no direction: the relationship between u and v is symmetric. In a directed graph, an edge (u, v) has an orientation from u to v. Edges may also have weights representing distance, cost, time, risk, capacity, similarity, or another quantitative attribute.

The degree of a vertex in an undirected graph is the number of incident edges. In a directed graph, indegree counts incoming edges and outdegree counts outgoing edges. A walk is a sequence of vertices connected by edges. A path is usually understood as a walk without repeated vertices, although some algorithmic contexts use path more generally. A cycle is a closed path whose first and last vertices coincide. A graph with no cycles is acyclic; a directed acyclic graph is commonly abbreviated DAG.

Two vertices are connected if a path exists between them. An undirected graph is connected when every pair of vertices is connected. A directed graph is strongly connected if every vertex can reach every other vertex following edge directions. It is weakly connected if connectivity exists after directions are ignored. A connected component is a maximal connected subgraph.

A graph is sparse when the number of edges is close to the number of vertices; it is dense when the number of edges approaches the maximum possible. For a simple undirected graph with n vertices, at most n(n−1)/2 edges are possible. This distinction strongly influences representation and algorithm performance.

Representing a Graph

An adjacency matrix is an n × n array. The entry A[u][v] records whether an edge exists or stores its weight. It requires Θ(n²) space and permits constant-time edge lookup. It is useful for dense graphs or algorithms that repeatedly inspect every pair of vertices. For a graph with millions of vertices and relatively few edges, however, most matrix entries are empty and memory use becomes impractical.

An adjacency list stores, for every vertex, a list of its neighboring vertices and, where applicable, edge weights. It requires Θ(|V| + |E|) space and supports efficient iteration over existing edges. Most traversal and sparse-network algorithms use adjacency lists. An edge list simply stores the edges as records such as (u, v, w). It is particularly convenient for sorting edges, as in Kruskal’s minimum-spanning-tree algorithm.

Representation is not a merely programming-level choice. It encodes assumptions about the data and determines the cost of basic operations. A route planner requiring frequent neighbor exploration generally favors adjacency lists, whereas an application repeatedly asking whether arbitrary pairs are directly connected may favor a matrix or a specialized indexing structure.

2. Traversal: Discovering the Structure of a Network

Graph traversal systematically visits vertices and edges. The two foundational methods are breadth-first search (BFS) and depth-first search (DFS). Both run in Θ(|V| + |E|) time with adjacency lists when each vertex and edge is processed a constant number of times.

Breadth-First Search

BFS explores a graph in layers according to distance from a starting vertex. It uses a queue. Initially, the source is marked discovered and placed in the queue. The algorithm repeatedly removes the front vertex, examines its undiscovered neighbors, marks them discovered, records their predecessor, and appends them to the queue.

Because all vertices at distance k are processed before vertices at distance k + 1, BFS computes shortest paths measured by the number of edges in an unweighted graph. A predecessor array can reconstruct a shortest route by following parent pointers backward from the destination. BFS can also determine reachability, identify connected components, test bipartiteness through two-coloring, and calculate minimum hop counts in communication or social networks.

The correctness of BFS rests on its queue order. When a vertex is first discovered, all paths from the source to undiscovered vertices through that vertex must have at least one more edge than the path used to reach the vertex. Since vertices are processed in nondecreasing distance order, the first recorded distance is optimal.

Depth-First Search

DFS explores one branch as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack. A typical DFS records discovery and finishing times. The discovery time is assigned when a vertex is first visited; the finishing time is assigned after all outgoing or incident edges have been examined.

DFS supports cycle detection, connected-component analysis, topological sorting, articulation-point and bridge algorithms, and strongly connected-component computation. In a directed graph, an edge leading to a currently active ancestor indicates a back edge and therefore a directed cycle. In an undirected graph, a visited neighbor that is not the current vertex’s parent can indicate a cycle.

Recursive DFS is concise, but deep graphs can exceed the call-stack limit. An iterative implementation may be safer in production systems. For both BFS and DFS, a common mistake is to mark a vertex only when it is removed from the queue or stack. Marking on insertion prevents the same vertex from being inserted repeatedly and preserves the intended complexity.

Connectivity and Components

To find all connected components of an undirected graph, run BFS or DFS from every vertex that has not yet been visited. Each new search identifies one component. The total complexity remains Θ(|V| + |E|), because each vertex and edge is processed only as part of the complete traversal.

In directed graphs, strongly connected components are maximal vertex sets in which every vertex can reach every other. Kosaraju’s algorithm uses two DFS passes: one to establish an order based on finishing times and another on the transposed graph. Tarjan’s algorithm finds all strongly connected components in one DFS using low-link values and a stack. Strong components are valuable in dependency analysis, web structure analysis, and identifying mutually reachable states in software or control systems.

3. Ordering Dependencies with DAGs

A topological ordering of a directed graph is a linear ordering of its vertices such that for every edge (u, v), u appears before v. Such an ordering exists if and only if the graph is acyclic. A course prerequisite graph, for example, can be topologically ordered only when the prerequisite relations contain no circular requirement.

Kahn’s algorithm repeatedly selects a vertex of indegree zero, outputs it, removes its outgoing edges, and updates the indegrees of neighboring vertices. If fewer than |V| vertices are output, the graph contains a cycle. A priority queue may be used when a deterministic or lexicographically preferred ordering is required.

DFS provides another method. After exploring all descendants of a vertex, place that vertex at the front of a list or push it onto a stack. Reversing finishing order yields a topological ordering, provided no back edge is found. Both methods require Θ(|V| + |E|) time.

Topological order is not itself a scheduling solution. Real schedules may additionally require processing times, resource constraints, deadlines, and parallel capacity. Nevertheless, topological ordering provides the precedence-feasible structure on which more advanced scheduling procedures operate.

4. Shortest-Path Algorithms and Their Assumptions

The shortest-path problem seeks a minimum-cost route between vertices. Costs may represent distance, latency, energy, monetary expense, or a learned risk score. The meaning of “shortest” depends entirely on the weight model. An algorithm that is correct for nonnegative distance cannot automatically be used when negative weights represent credits, rebates, or state transitions.

Unweighted Shortest Paths

BFS solves the single-source shortest-path problem in an unweighted graph, or in a graph where every edge has equal cost. Its time complexity is Θ(|V| + |E|). Assigning arbitrary weights to edges while continuing to use BFS is a modeling error; BFS minimizes edge count, not total weight.

Dijkstra’s Algorithm

Dijkstra’s algorithm solves single-source shortest paths when all edge weights are nonnegative. It maintains a tentative distance d[v] for each vertex. Initially d[source] = 0 and all other distances are infinity. At each step, the unsettled vertex with minimum tentative distance is selected. Its outgoing edges are relaxed: if d[v] exceeds d[u] + w(u, v), it is reduced and its predecessor is updated.

The greedy choice is valid because nonnegative edges cannot produce a later route that returns to the selected vertex with a smaller cost. With a binary heap and adjacency lists, the complexity is O((|V| + |E|) log |V|), commonly written O(|E| log |V|) for connected sparse graphs. With an array-based priority selection, it is O(|V|²), which can be competitive for dense graphs.

A practical implementation should use a priority queue with lazy deletion or a decrease-key operation. With lazy deletion, obsolete queue entries are ignored when removed. Negative edge weights invalidate Dijkstra’s correctness even if no negative cycle exists.

Bellman–Ford Algorithm

Bellman–Ford also solves the single-source problem but permits negative edge weights. It repeatedly relaxes every edge |V| − 1 times. Any simple shortest path contains at most |V| − 1 edges, so after that many passes all shortest distances must have stabilized if no reachable negative cycle exists. A further successful relaxation indicates a reachable negative cycle.

Its complexity is O(|V||E|), making it slower than Dijkstra on many practical graphs. Its value lies in broader correctness and negative-cycle detection. Early termination is possible when a complete pass makes no changes.

A negative cycle is not merely a technical inconvenience. If reachable from the source, repeated traversal can reduce path cost without bound, so no finite shortest path exists. In financial or optimization systems, such a cycle may indicate arbitrage, an accounting inconsistency, or a flawed cost model.

All-Pairs Shortest Paths

Floyd–Warshall computes shortest distances between every pair of vertices using dynamic programming. Let D^(k)[i][j] be the shortest distance from i to j using only the first k vertices as possible intermediate vertices. The recurrence is:

D^(k)[i][j] = min(D^(k−1)[i][j], D^(k−1)[i][k] + D^(k−1)[k][j]).

The algorithm takes Θ(|V|³) time and Θ(|V|²) space. It is appropriate for relatively small or dense graphs when all-pairs answers are required. Negative edges are allowed, but negative cycles must not exist. A negative diagonal entry after computation indicates a negative cycle.

Choosing a Shortest-Path Method

The central selection questions are: Is the graph weighted? Can weights be negative? Is one source or every pair required? Is the graph static or changing? For nonnegative sparse networks, Dijkstra is a standard choice. For unweighted networks, BFS is simpler and faster. For negative weights, Bellman–Ford is safer. For all-pairs queries on a modest dense graph, Floyd–Warshall may be appropriate. In very large production networks, specialized methods, contraction hierarchies, bidirectional search, or dynamic shortest-path techniques may be needed.

5. Minimum Spanning Trees: Building Economical Networks

A spanning tree of a connected undirected graph contains every vertex and has exactly |V| − 1 edges, with no cycle. A minimum spanning tree (MST) is a spanning tree of minimum total edge weight. Unlike a shortest-path tree, an MST minimizes the total cost of connecting all vertices; it does not necessarily provide the shortest route from one chosen source to every destination.

The cut property explains the main greedy algorithms: for any cut dividing the vertices into two sets, a lightest edge crossing that cut belongs to some MST. The cycle property provides a complementary rule: a heaviest edge on a cycle can be excluded from at least one MST.

Kruskal’s Algorithm

Kruskal’s algorithm sorts all edges by nondecreasing weight and considers them in that order. An edge is accepted if it connects two currently different components; otherwise it is rejected because accepting it would form a cycle. A disjoint-set union structure, also called union–find, supports efficient component testing and merging through path compression and union by rank or size.

Sorting dominates the complexity, giving O(|E| log |E|), with nearly linear additional work for union–find. Kruskal naturally handles disconnected graphs by producing a minimum spanning forest. Ties may lead to multiple valid MSTs with equal total weight.

Prim’s Algorithm

Prim’s algorithm begins with any vertex and grows one tree. At each step, it adds the minimum-weight edge connecting a tree vertex to a vertex outside the tree. With adjacency lists and a binary heap, its complexity is O(|E| log |V|). With an adjacency matrix, it is O(|V|²), often suitable for dense graphs.

MSTs are used in telecommunications design, utility infrastructure, clustering, image processing, and broadcast networks. In clustering, removing the largest edges from an MST can produce a hierarchy of groups. However, the MST objective may be inappropriate when reliability, redundancy, traffic capacity, or geographical constraints matter. A cheapest network can be fragile if every critical connection is a single point of failure.

6. Matching and Maximum Flow

A matching is a set of edges with no shared endpoints. In a bipartite graph, vertices are divided into two disjoint sets, such as applicants and jobs or users and recommendation slots. A maximum matching contains as many edges as possible. A weighted matching instead maximizes or minimizes a total score.

Bipartite matching can be solved by augmenting paths. Begin with an empty matching. If an alternating path starts and ends at unmatched vertices, reversing the matched and unmatched status of its edges increases the matching size by one. Repeating this process until no augmenting path remains yields a maximum matching. The theorem behind this method states that a matching is maximum exactly when no augmenting path exists.

A bipartite matching problem can also be transformed into a maximum-flow problem. Create a source connected to every left-side vertex with capacity 1, direct original bipartite edges with capacity 1, and connect every right-side vertex to a sink with capacity 1. An integral maximum flow corresponds to a maximum matching.

In a flow network, each edge has a capacity, and flow must satisfy capacity constraints and flow conservation at intermediate vertices. The residual network records unused forward capacity and the possibility of undoing previously assigned flow through reverse edges. An augmenting-path algorithm repeatedly finds a source-to-sink path in the residual network and sends the largest possible additional flow, called the bottleneck capacity.

The max-flow min-cut theorem states that the maximum value of a feasible flow equals the minimum capacity of an s–t cut. This provides both an optimality certificate and an interpretive tool: a minimum cut identifies the network bottleneck limiting throughput.

Ford–Fulkerson is a general augmenting-path framework. With integer capacities, it terminates, although the number of iterations can depend on path choices. Edmonds–Karp uses BFS to select shortest augmenting paths and has polynomial complexity O(|V||E|²). More advanced algorithms, such as Dinic’s algorithm and push–relabel methods, are often preferred for large networks.

Flow models are broader than physical transportation. They can represent assignment, image segmentation, project selection, supply chains, data routing, and resource allocation. Capacities, however, must be carefully interpreted. A capacity may represent a legal limit, machine availability, bandwidth, or an approximation; treating a predicted capacity as exact can produce operationally unsafe decisions.

An Illustrative Case: Designing a Regional Delivery Network

Background

Consider a fictional logistics company, Northstar Fulfilment, serving six distribution locations. It must answer three related questions: which locations are reachable under current road conditions, which roads should be funded to connect all depots at minimum construction cost, and which routes should be used to move urgent parcels from a central warehouse.

Situation and Analysis

The road network is modeled as a weighted undirected graph. Vertices represent depots and edges represent roads. Construction cost is used for the MST problem, while travel time is used for shortest paths. These are deliberately separate weights: the cheapest infrastructure network need not provide the fastest deliveries.

BFS is first used on a simplified unweighted version to determine the number of road hops from the warehouse and to detect isolated depots. DFS identifies connected components and helps validate whether the imported road data contains duplicate or disconnected records. If the company introduces one-way delivery restrictions, the graph becomes directed and strong connectivity must be reconsidered.

Approach and Solution

Kruskal’s algorithm is applied to the construction-cost edge list. Union–find prevents cycles and produces a minimum spanning tree when all depots are connected. Dijkstra’s algorithm is then run from the warehouse on nonnegative travel-time weights. The resulting predecessor tree provides fastest routes from the warehouse, but it is not confused with the construction MST.

Suppose the company also has a daily loading limit at a cross-dock. A flow network is created with capacities on roads and handling stations. Maximum flow estimates the greatest feasible parcel throughput. The minimum cut identifies the set of roads or processing stages whose capacity must be expanded.

Outcome

The combined analysis reveals that one depot is reachable but poorly served: it belongs to the connected network, yet its shortest travel time is high. The MST shows a low-cost way to connect all depots, while the flow calculation identifies a loading station rather than a road as the true throughput bottleneck. Management therefore avoids an expensive road expansion that would not increase total delivery capacity.

Learning Points

The case illustrates that graph algorithms answer different optimization questions. Connectivity asks whether a route exists; shortest path asks for the best route between specified endpoints; MST asks for a globally economical connection structure; and maximum flow asks how much can move through a capacitated network. Using one algorithm as a substitute for another can produce an apparently precise but operationally wrong recommendation.

Graph Algorithms in AI and Industry

Graph algorithms often form the structural layer beneath machine-learning systems. In recommendation engines, a user–item bipartite graph supports candidate generation through neighborhood exploration or matching. In knowledge graphs, BFS, DFS, and shortest paths support relation discovery and explanation. Fraud analytics uses connected components, dense subgraphs, and unusual paths to identify coordinated behavior. In computer vision, graph cuts and flows support segmentation. In natural-language and scientific applications, entities and citations can be represented as directed weighted networks.

Graph neural networks learn representations by aggregating information over neighborhoods, but the quality of neighborhood construction remains an algorithmic issue. Sampling methods may use random walks, BFS-like expansion, or importance-based selection. Preprocessing can include removal of duplicate edges, treatment of self-loops, normalization of weights, and detection of disconnected components.

In organizations, graph analysis also supports dependency-aware deployment, supply-chain risk assessment, network resilience, workforce assignment, and infrastructure planning. Managers should distinguish a mathematically optimal solution from an implementable one. Constraints such as maintenance access, fairness, redundancy, regulatory obligations, uncertainty, and changing demand may require a multi-objective or robust formulation.

Limitations, Risks, and Professional Responsibilities

Graph algorithms are exact relative to their model, not necessarily relative to reality. An incomplete graph can make a reachable entity appear isolated. Noisy edge weights can reverse route rankings. A recommendation graph based only on observed behavior may reproduce historical exclusion. A shortest path that minimizes cost may pass through unsafe or restricted locations.

Common technical mistakes include applying Dijkstra to graphs with negative weights, using BFS for weighted shortest paths, confusing an MST with a shortest-path tree, forgetting reverse residual edges in flow implementations, failing to reset visited state between component searches, and allowing integer overflow when distances are large. Recursive DFS may fail on deep inputs, and adjacency matrices may exhaust memory on sparse large graphs.

Ethically sensitive applications require attention to privacy, consent, fairness, and explainability. Social or transaction graphs can expose relationships even when individual records appear anonymized. Access controls and data minimization are therefore essential. When graph-derived scores affect credit, employment, policing, healthcare, or content visibility, organizations should audit the data-generating process, test disparate impacts, document assumptions, and provide mechanisms for review.

Emerging Directions and Best Practices

Modern systems increasingly process dynamic, temporal, uncertain, and attributed graphs. Edges may appear and disappear, weights may change with traffic, and relationships may have validity intervals. Streaming connectivity, incremental shortest paths, temporal reachability, and distributed graph processing address these settings. Large-scale platforms use partitioning, parallel traversal, compressed representations, and specialized graph databases.

A sound professional workflow includes the following practices:

• define precisely what vertices, edges, directions, and weights mean;
• choose a representation based on density, scale, and required operations;
• state algorithm assumptions, especially about weight signs and graph connectivity;
• retain predecessor, parent, or certificate information for verification and explanation;
• test boundary cases such as empty graphs, self-loops, parallel edges, isolated vertices, cycles, and disconnected components;
• validate results against domain constraints rather than trusting numerical optimality alone;
• monitor changing data and recompute when the graph or weights become stale.

The most important discipline is to match the algorithm to the question. A graph is a model of a system, and algorithmic correctness begins with modeling correctness.

Chapter Summary

Graphs represent entities and relationships through vertices and edges. Directedness, weights, density, connectivity, and cycles determine which algorithms are valid and how efficiently they can operate. Adjacency lists are generally effective for sparse graphs, whereas matrices suit dense graphs and constant-time edge lookup.

BFS explores layers and computes shortest paths in unweighted graphs. DFS supports structural analysis, cycle detection, components, and topological sorting. Topological ordering applies to DAGs and expresses precedence constraints. Dijkstra solves nonnegative single-source shortest paths; Bellman–Ford permits negative edges and detects reachable negative cycles; Floyd–Warshall solves all-pairs shortest paths with cubic time complexity.

Minimum spanning trees minimize the total cost of connecting all vertices, with Kruskal and Prim providing complementary greedy approaches. Matching addresses non-overlapping assignments, while maximum flow models capacity-constrained movement and is characterized by the max-flow min-cut theorem. In practice, graph algorithms support logistics, infrastructure, recommendation, scheduling, knowledge representation, and AI pipelines. Their responsible use requires accurate modeling, awareness of assumptions, privacy protection, fairness analysis, and operational validation.

Key Terms

Graph: A structure consisting of vertices and edges representing relationships.

Vertex: An individual node or entity in a graph.

Edge: A connection between two vertices.

Directed graph: A graph whose edges have orientations.

Weighted graph: A graph whose edges carry numerical costs or attributes.

Degree: The number of incident edges at a vertex.

Path: A sequence of vertices connected by edges.

Cycle: A closed path that begins and ends at the same vertex.

Connected component: A maximal connected subgraph.

Strong connectivity: Mutual reachability among every pair of vertices in a directed subgraph.

BFS: A queue-based traversal that explores vertices in increasing edge distance.

DFS: A traversal that explores deeply before backtracking.

Topological ordering: A vertex ordering satisfying all directed precedence edges.

Relaxation: The operation of improving a tentative shortest-path distance.

Minimum spanning tree: A minimum-weight tree connecting every vertex of a connected undirected graph.

Matching: A set of edges sharing no endpoints.

Flow network: A directed capacitated graph used to model transferable quantities.

Residual network: A representation of remaining and reversible flow capacity.

Minimum cut: A partition whose crossing capacity is minimum between a source and sink.

Negative cycle: A cycle whose total edge weight is less than zero.

Review Questions

Short Answer Questions

1. Why is an adjacency list usually preferred for a sparse graph?

2. What property enables BFS to compute shortest paths in an unweighted graph?

3. State the condition under which a directed graph has a topological ordering.

4. What is the difference between a minimum spanning tree and a shortest-path tree?

5. What does a negative diagonal entry in a Floyd–Warshall distance matrix indicate?

Long Answer Questions

1. Explain BFS and DFS, including their data structures, complexity, and principal applications.

2. Compare Dijkstra’s algorithm, Bellman–Ford, and Floyd–Warshall with respect to assumptions, outputs, and complexity.

3. Explain Kruskal’s and Prim’s algorithms and relate each to the cut property.

4. Describe maximum flow, residual networks, augmenting paths, and the max-flow min-cut theorem.

5. Discuss how graph representation and weight interpretation influence the design of an industrial network solution.

Analytical / Application Questions

1. A road network contains one-way roads and a promotional credit that gives one edge a negative cost. Which shortest-path method would you select, and what additional risk must be checked?

2. A company wants to connect all offices as cheaply as possible but also requires two independent routes to every major office. Explain why a minimum spanning tree alone is insufficient and suggest how the model should change.

3. A recommendation platform observes that a minority group has few historical connections. Analyze how graph-based candidate generation could reinforce this pattern and propose technical and governance safeguards.

22. Multiple Choice Questions with Answers

Question 1

Which graph representation is generally most space-efficient for a sparse graph with |V| vertices and |E| edges?

A. Adjacency matrix using Θ(|V|²) space

B. Adjacency list using Θ(|V|+|E|) space

C. A distance matrix using Θ(|V|²) space

D. A complete edge table containing every possible pair

Correct Answer: B. Adjacency list using Θ(|V|+|E|) space

Question 2

Why does breadth-first search compute shortest paths in an unweighted graph?

A. It always selects the numerically smallest vertex

B. It processes vertices in nondecreasing number of edges from the source

C. It sorts all edges by weight

D. It explores the deepest branch first

Correct Answer: B. It processes vertices in nondecreasing number of edges from the source

Question 3

A directed graph has an edge from A to B, B to C, and C to A. What follows?

A. It must have a topological ordering

B. It is a tree

C. It contains a directed cycle and has no topological ordering

D. It is necessarily disconnected

Correct Answer: C. It contains a directed cycle and has no topological ordering

Question 4

Which condition is required for Dijkstra’s algorithm to be correct?

A. All edge weights are nonnegative

B. The graph must be acyclic

C. Every vertex must have the same degree

D. The graph must be represented by an adjacency matrix

Correct Answer: A. All edge weights are nonnegative

Question 5

Which algorithm is designed to detect a reachable negative-weight cycle while computing single-source shortest paths?

A. BFS

B. Prim’s algorithm

C. Bellman–Ford

D. Kruskal’s algorithm

Correct Answer: C. Bellman–Ford

Question 6

What is the primary objective of a minimum spanning tree?

A. Minimize the route from one source to every destination

B. Maximize the number of cycles

C. Connect all vertices with minimum total edge weight and no cycles

D. Maximize flow between a source and sink

Correct Answer: C. Connect all vertices with minimum total edge weight and no cycles

Question 7

In Kruskal’s algorithm, why is a disjoint-set union structure used?

A. To calculate vertex indegrees

B. To determine whether an edge joins two different components

C. To store BFS layers

D. To identify negative edge weights

Correct Answer: B. To determine whether an edge joins two different components

Question 8

In a residual flow network, a reverse edge primarily represents:

A. A guaranteed physical return route

B. The ability to undo or redirect previously assigned flow

C. An edge with negative capacity

D. A disconnected component

Correct Answer: B. The ability to undo or redirect previously assigned flow

Question 9

According to the max-flow min-cut theorem, the value of a maximum flow equals:

A. The number of vertices in the network

B. The capacity of the largest individual edge

C. The capacity of a minimum source–sink cut

D. The total number of paths from source to sink

Correct Answer: C. The capacity of a minimum source–sink cut

Question 10

A logistics manager uses an MST to choose roads for minimum construction cost and then uses Dijkstra with travel times. Why are two algorithms appropriate?

A. MST and shortest path always produce identical results

B. They optimize different objectives: total network connection cost and route travel time

C. Dijkstra is required only because the graph is directed

D. Kruskal cannot process weighted edges

Correct Answer: B. They optimize different objectives: total network connection cost and route travel time