Graph Representation and Traversal

Introduction

Graphs provide a general model for relationships among objects. In a graph, objects are represented by vertices (or nodes), and relationships are represented by edges (or arcs). This model supports applications such as road navigation, computer networks, social networks, recommendation systems, dependency management, web crawling, and knowledge graphs.

A graph differs from a linear data structure because a vertex may be related to many other vertices, and relationships may form cycles. Consequently, graph algorithms must address questions such as:

• How should a graph be stored efficiently?
• Which vertices can be reached from a starting vertex?
• What is the shortest number of links between two vertices?
• Does a dependency graph contain a cycle?
• Can tasks be ordered so that all prerequisites are satisfied?
• Which groups of vertices are mutually reachable?

This chapter develops the principal representations and traversal algorithms used in practical graph processing. It focuses on adjacency structures, breadth-first search, depth-first search, topological sorting, cycle detection, connected components, and strongly connected components.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define directed, undirected, weighted, and unweighted graphs.

2. Select an adjacency matrix, adjacency list, or edge-list representation for a problem.

3. Implement and analyze breadth-first search (BFS) and depth-first search (DFS).

4. Use BFS to determine reachability and shortest paths in unweighted graphs.

5. Use DFS for classification of edges, cycle detection, and topological sorting.

6. Compute connected components in undirected graphs.

7. Explain and apply strongly connected component algorithms for directed graphs.

8. Evaluate graph algorithms according to time, space, and application requirements.

1. Graph Foundations

A graph is commonly written as \(G=(V,E)\), where \(V\) is a set of vertices and \(E\) is a set of edges. The number of vertices is \(|V|=n\), and the number of edges is \(|E|=m\).

In an undirected graph, an edge \(\{u,v\}\) represents a two-way relationship. If \(u\) is adjacent to \(v\), then \(v\) is adjacent to \(u\). In a directed graph, an edge \((u,v)\) has an origin \(u\) and destination \(v\); the reverse edge need not exist.

A weighted graph assigns a value, such as distance, cost, or latency, to each edge. An unweighted graph treats all edges as having equal significance for traversal purposes. A graph may contain self-loops, such as \((u,u)\), and parallel edges, although many textbook implementations exclude them.

The degree of a vertex in an undirected graph is the number of incident edges. In a directed graph, the indegree is the number of incoming edges and the outdegree is the number of outgoing edges. A path is a sequence of vertices connected by edges. A path with no repeated vertices is a simple path. A cycle is a closed path with at least one edge; in a directed graph, edge direction must be respected.

A graph is connected if every pair of vertices is joined by a path. More precisely, an undirected graph is connected when every vertex is reachable from every other vertex. A directed graph is strongly connected when every vertex can reach every other vertex following edge directions. It is weakly connected when connectivity exists after ignoring directions.

A subgraph contains selected vertices and edges from another graph. A spanning tree of a connected undirected graph contains all vertices, is connected, and has no cycles. Every spanning tree with \(n\) vertices has exactly \(n-1\) edges.

2. Graph Representations

The appropriate representation depends on graph density, the operations required, and memory constraints.

2.1 Adjacency Matrix

For a graph with \(n\) vertices, an adjacency matrix is an \(n\times n\) table \(A\). For an unweighted directed graph,

\[

A[i][j]=

\begin{cases}

1 & \text{if an edge }(i,j)\text{ exists},\\

0 & \text{otherwise.}

\end{cases}

\]

For a weighted graph, an entry may store the edge weight, while a special value such as infinity indicates no edge. The matrix requires \(O(n^2)\) space. Testing whether a particular edge exists takes \(O(1)\) time, and inserting or deleting an edge also takes \(O(1)\) time. Enumerating all neighbors of a vertex requires \(O(n)\) time because an entire row may need to be scanned.

For an undirected graph, the matrix is symmetric: \(A[i][j]=A[j][i]\). This representation is attractive for dense graphs, where \(m\) is close to \(n^2\), or when constant-time edge lookup is important. It is wasteful for sparse graphs because most entries may be zero.

2.2 Adjacency List

An adjacency list stores, for each vertex, a collection of its neighbors. For example, the directed edges \(A\to B\), \(A\to C\), \(B\to D\), and \(C\to D\) can be stored as:

```text

A: B, C

B: D

C: D

D:

```

The space requirement is \(O(n+m)\), assuming the graph stores one record per directed edge. In an undirected graph, each edge is normally stored twice, once in each endpoint's list; the asymptotic space remains \(O(n+m)\). Iterating through the neighbors of vertex \(v\) takes \(O(\deg(v))\) time. A search for a particular edge may take \(O(\deg(v))\), unless additional indexing is used.

Adjacency lists are usually preferred for sparse graphs and for traversal algorithms. BFS and DFS can process a graph represented by adjacency lists in \(O(n+m)\) time because each vertex and each stored edge is examined a constant number of times.

2.3 Edge List

An edge list stores edges as records, for example:

```text

(A, B), (A, C), (B, D), (C, D)

```

It requires \(O(m)\) space, apart from vertex storage. It is simple and useful when algorithms primarily process all edges, such as some minimum-spanning-tree procedures. However, finding all neighbors of a particular vertex requires scanning the entire list, which is inefficient for repeated traversal.

2.4 Representation Choice

A useful decision rule is:

• Choose an adjacency matrix for dense graphs or frequent constant-time edge queries.
• Choose adjacency lists for sparse graphs and graph traversal.
• Choose an edge list when edges are processed globally and neighborhood queries are uncommon.

The choice can materially affect performance. For example, BFS on an adjacency matrix takes \(O(n^2)\), while BFS on an adjacency list takes \(O(n+m)\). When a sparse graph has \(m=O(n)\), the latter is approximately linear rather than quadratic.

3. Breadth-First Search

Breadth-first search explores a graph in layers according to the number of edges from a starting vertex. It uses a queue, following the first-in, first-out principle. BFS is especially important because, in an unweighted graph, it discovers shortest paths measured by number of edges.

3.1 BFS Algorithm

For a graph represented by adjacency lists, the algorithm is:

```text

BFS(G, s):

for each vertex v in G:

visited[v] = false

distance[v] = infinity

parent[v] = NIL

visited[s] = true

distance[s] = 0

enqueue(Q, s)

while Q is not empty:

u = dequeue(Q)

for each v in Adj[u]:

if visited[v] == false:

visited[v] = true

distance[v] = distance[u] + 1

parent[v] = u

enqueue(Q, v)

```

A vertex is marked when it is enqueued, not when it is removed. This prevents the same vertex from being inserted multiple times. The parent array records a search tree. To reconstruct a path from \(s\) to a reachable vertex \(t\), repeatedly follow `parent` from \(t\) until reaching \(s\), then reverse the resulting sequence.

3.2 Correctness of BFS Shortest Paths

BFS processes all vertices at distance \(k\) before any vertex at distance \(k+1\). Initially, the source has distance zero. When an unvisited neighbor of a vertex at distance \(k\) is discovered, it is assigned distance \(k+1\). Since no undiscovered path can bypass an earlier layer, the first assigned distance is minimal. This guarantee assumes an unweighted graph, or that every edge is treated as having equal cost. BFS is not generally correct for weighted graphs with unequal positive weights.

3.3 Complexity

With adjacency lists, BFS has time complexity \(O(n+m)\) and auxiliary space \(O(n)\), excluding the graph representation. Each vertex is enqueued at most once, and each adjacency-list entry is inspected at most once. With an adjacency matrix, neighbor scanning causes \(O(n^2)\) time.

3.4 Applications

BFS is used for:

• Minimum-hop routing in unweighted networks.
• Finding all vertices reachable from a source.
• Testing bipartiteness by assigning alternating levels.
• Computing degrees of separation in social networks.
• Web crawling subject to depth limits.
• Discovering shortest sequences of actions in state-space problems.

4. Depth-First Search

Depth-first search explores one path as far as possible before backtracking. It can be implemented recursively or with an explicit stack. DFS is particularly useful for structural analysis, including cycle detection, topological sorting, connected components, and strongly connected components.

4.1 Recursive DFS

```text

DFS(G):

for each vertex v in G:

color[v] = WHITE

parent[v] = NIL

for each vertex v in G:

if color[v] == WHITE:

DFS-Visit(v)

DFS-Visit(u):

color[u] = GRAY

for each v in Adj[u]:

if color[v] == WHITE:

parent[v] = u

DFS-Visit(v)

color[u] = BLACK

```

The colors have standard meanings: white means undiscovered, gray means discovered but not fully explored, and black means fully explored. The gray state is essential for detecting a directed back edge.

A recursive implementation uses the call stack. For very deep graphs, recursion may exceed a language's stack limit; an explicit stack is then safer. The iterative version must carefully simulate the point at which a recursive call would resume, often by storing an iterator position for each vertex.

4.2 DFS Timestamps and Edge Classification

DFS can assign a discovery time \(d[u]\) when a vertex becomes gray and a finishing time \(f[u]\) when it becomes black. For every vertex, \(d[u]<f[u]\). In a directed graph, edges may be classified as:

• Tree edge: leads to a previously undiscovered vertex.
• Back edge: leads to an ancestor currently on the recursion stack.
• Forward edge: leads to a descendant that is not a tree edge.
• Cross edge: connects vertices without an ancestor–descendant relationship.

The classification depends on the directed graph and DFS forest. In an undirected graph, non-tree edges encountered during DFS generally connect a vertex to an ancestor and therefore reveal cycles.

5. Cycle Detection

5.1 Undirected Graphs

For an undirected graph, DFS can detect a cycle by tracking the parent of each vertex. When examining an edge from `u` to `v`:

• If `v` is unvisited, recursively explore it with parent `u`.
• If `v` is visited and `v` is not `parent[u]`, a cycle exists.

The parent exception is necessary because every undirected tree edge appears twice in adjacency lists: once from parent to child and once from child to parent.

An alternative is the disjoint-set union data structure when edges are processed incrementally. If the endpoints of an edge already belong to the same set, adding that edge creates a cycle.

5.2 Directed Graphs

For a directed graph, a cycle exists if DFS encounters an edge to a gray vertex. Such an edge points to a vertex still on the active recursion path, so it closes a directed cycle. An edge to a black vertex does not by itself imply a cycle.

A three-state implementation is therefore appropriate:

```text

HasCycle(u):

state[u] = GRAY

for v in Adj[u]:

if state[v] == GRAY:

return true

if state[v] == WHITE and HasCycle(v):

return true

state[u] = BLACK

return false

```

The procedure must be started from every white vertex so that disconnected portions are included. Its time complexity with adjacency lists is \(O(n+m)\).

6. Topological Sorting

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

Topological sorting is useful for course prerequisites, build systems, package installation, project scheduling, and data-processing pipelines.

6.1 DFS-Based Method

Run DFS and place each vertex at the front of a list when it finishes. Equivalently, append vertices on completion and reverse the list. For every edge \((u,v)\) in an acyclic graph, DFS ensures that \(u\) finishes after \(v\) when the edge is a tree, forward, or cross edge in the relevant ordering; reversing finish order places \(u\) before \(v\). A gray-edge detection step must be included to reject cyclic graphs.

```text

TopologicalSort(G):

result = empty list

run DFS with WHITE, GRAY, BLACK states

when a vertex u becomes BLACK:

prepend u to result

if a gray edge is found:

report that no ordering exists

else:

return result

```

6.2 Kahn's Algorithm

Kahn's algorithm uses indegrees:

1. Compute the indegree of every vertex.

2. Insert every zero-indegree vertex into a queue.

3. Remove one such vertex and append it to the ordering.

4. Decrease the indegree of each outgoing neighbor.

5. Insert a neighbor when its indegree becomes zero.

6. If fewer than \(n\) vertices are output, the graph contains a cycle.

With adjacency lists and a queue, the complexity is \(O(n+m)\). Kahn's algorithm makes the dependency interpretation explicit and can identify vertices that are initially available. If a priority queue is used instead, a deterministic lexicographically smallest ordering may be produced, but the time complexity becomes \(O((n+m)\log n)\) in the usual implementation.

A topological order is not necessarily unique. For example, independent tasks may be exchanged without violating any dependency.

7. Connected Components

In an undirected graph, a connected component is a maximal set of vertices in which every pair is connected by a path. Components can be found by running DFS or BFS from each unvisited vertex:

```text

count = 0

for each vertex v:

if not visited[v]:

count = count + 1

BFS-or-DFS(v)

```

Each traversal marks exactly one component. Therefore, the number of traversals is the number of connected components, and the total time is \(O(n+m)\) with adjacency lists.

Applications include identifying isolated network segments, grouping related records, image-region analysis, and determining whether an undirected communication network is operationally connected.

For dynamic connectivity, where edges are repeatedly added and connectivity queries are interleaved, disjoint-set union is often preferable. Its union and find operations are nearly constant amortized time when path compression and union by rank or size are used, although this structure does not naturally support arbitrary edge deletion.

8. Strongly Connected Components

A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that every vertex can reach every other vertex in the set. SCCs partition the vertices. If each SCC is contracted into a single super-vertex, the resulting condensation graph is always a DAG.

SCCs reveal mutually dependent modules, circular web-link structures, recurrent states in a transition system, and groups of entities with mutual reachability.

8.1 Kosaraju's Algorithm

Kosaraju's algorithm uses two DFS passes:

1. Run DFS on the original graph and record vertices by finishing time.

2. Reverse every edge to form the transpose graph.

3. Process vertices in decreasing order of finishing time from the first pass.

4. Run DFS in the transpose graph from each unvisited vertex. Each traversal identifies one SCC.

The first finishing order ensures that, in the transpose graph, a new DFS begins at a source component in the remaining condensation structure and does not incorrectly merge components. Constructing the transpose and performing both DFS passes takes \(O(n+m)\) time and \(O(n+m)\) space.

8.2 Tarjan's Algorithm

Tarjan's algorithm finds all SCCs in one DFS. It maintains:

• `index[u]`, the discovery index of \(u\);
• `low[u]`, the smallest discovery index reachable from \(u\) using zero or more tree edges followed by at most one back edge;
• a stack containing active vertices.

When `low[u] == index[u]`, \(u\) is the root of an SCC; vertices are popped from the stack until \(u\) is removed. Tarjan's algorithm runs in \(O(n+m)\) time and uses linear auxiliary space. It is efficient but more subtle to implement correctly than Kosaraju's method.

9. Worked Example: Dependency Planning

Consider a software project with tasks:

• `Design` must precede `Implement`.
• `Design` must precede `Test`.
• `Implement` must precede `Integrate`.
• `Test` must precede `Integrate`.
• `Integrate` must precede `Deploy`.

Represent these dependencies as directed edges:

```text

Design -> Implement

Design -> Test

Implement -> Integrate

Test -> Integrate

Integrate -> Deploy

```

The indegrees are:

```text

Design: 0, Implement: 1, Test: 1, Integrate: 2, Deploy: 1

```

Kahn's algorithm begins with `Design`. Removing it reduces the indegrees of `Implement` and `Test` to zero. Either may be selected next. If `Implement` is selected, `Test` may follow; after both are removed, `Integrate` reaches indegree zero, followed by `Deploy`.

One valid order is:

```text

Design, Implement, Test, Integrate, Deploy

```

Another valid order is:

```text

Design, Test, Implement, Integrate, Deploy

```

The two orders differ because `Implement` and `Test` are independent once `Design` is complete. If an additional edge `Deploy -> Design` were introduced, every vertex would lie in a cycle, and Kahn's algorithm would output fewer than five vertices. The project would then have no feasible topological schedule.

10. Applied Case: Urban Emergency Routing

Background

Consider an emergency-response authority that models intersections as vertices and one-way or two-way roads as directed or undirected edges. The system must answer whether a station can reach an incident, determine a route with the fewest road segments when all segments are treated equally, and identify isolated neighborhoods after a network disruption.

Problem

The authority has a sparse road network with thousands of intersections but relatively few roads per intersection. It requires rapid repeated traversal and must account for one-way streets. A matrix would consume substantial memory, while an edge list would make neighborhood exploration unnecessarily slow.

Analysis and Approach

An adjacency list is selected. For reachability from a station, BFS or DFS is appropriate. BFS supplies a minimum-hop route in the unweighted model and records parent pointers for route reconstruction. If road lengths or travel times are important, BFS is no longer sufficient; a weighted shortest-path algorithm such as Dijkstra's algorithm may be required when weights are nonnegative.

To identify neighborhoods disconnected in the undirected road-maintenance view, the system runs a component search. For the directed traffic network, SCC analysis identifies areas in which every intersection can reach every other intersection following one-way streets. These SCCs can be contracted into a DAG to reveal one-way movement between mutually reachable regions.

Outcome

The adjacency-list design reduces traversal work to \(O(n+m)\), rather than scanning all \(n^2\) possible pairs. BFS provides transparent route reconstruction, component analysis identifies affected regions, and SCC analysis distinguishes mutual circulation from merely one-way reachability.

Learning Points

The case illustrates that graph representation and algorithm selection are linked. The same road data may support several models: an undirected graph for physical connectivity, a directed graph for traffic flow, and a weighted graph for travel time. No single traversal algorithm answers every routing question.

11. Implementation and Engineering Considerations

A reliable implementation should first define whether vertex identifiers are integers, strings, or external records. Integer identifiers permit compact arrays; string identifiers usually require a mapping to integer indices. The implementation should also state whether duplicate edges and self-loops are allowed.

For large graphs, adjacency lists should avoid unnecessary object overhead where possible. Streaming edge input may be preferable to constructing a matrix. In parallel or distributed systems, graph partitioning and communication costs become important; an algorithm with good sequential complexity may still perform poorly if it repeatedly transfers frontier data between machines.

Traversal code should explicitly handle disconnected graphs by starting a new search from every unvisited vertex when a complete graph analysis is required. It should also distinguish directed and undirected insertion: an undirected edge must be inserted in both adjacency lists, whereas a directed edge is inserted only in the source list.

Testing should include an empty graph, a single vertex, isolated vertices, a tree, a graph with parallel edges if supported, self-loops, disconnected graphs, directed cycles, DAGs with multiple valid topological orders, and very deep paths that stress recursion limits.

12. Limitations, Governance, and Contemporary Uses

Graph algorithms describe structural relationships; they do not automatically guarantee that the underlying data is correct. In recommendation or social-network systems, graph traversal may amplify popularity bias, expose sensitive relationships, or infer personal attributes. Access controls, data minimization, retention limits, and auditability are therefore important when graphs contain personal or operational data.

In AI and machine learning, graphs support knowledge graphs, fraud detection, molecular modeling, graph neural networks, and retrieval systems. Classical traversal remains foundational even when a learned model is used. For example, a graph neural network may require neighborhood aggregation, while a knowledge-retrieval system may use BFS-like expansion with limits. Engineers should control traversal depth and branching to avoid excessive computation and unintended propagation of irrelevant or sensitive information.

A graph can also change over time. Static algorithms may need adaptation for streaming edges, failures, or rapidly changing networks. Approximate methods, incremental connectivity algorithms, compressed representations, and external-memory processing are active engineering directions. Nevertheless, the basic distinctions among adjacency structures, BFS, DFS, and component analysis remain central.

Best Practices

1. Choose the representation based on density and dominant operations.

2. Use adjacency lists for most sparse traversal workloads.

3. Mark vertices when enqueuing in BFS and when first discovered in DFS.

4. Record parents when path reconstruction is required.

5. Use three-state DFS for directed cycle detection.

6. Verify that a topological sort outputs every vertex; otherwise report a cycle.

7. Start traversal from every unvisited vertex when disconnected graphs are possible.

8. Do not use BFS as a weighted shortest-path algorithm unless all edge weights are equal.

9. Test recursion depth and consider an explicit stack for large graphs.

10. Protect graph data containing personal, confidential, or safety-critical information.

Chapter Summary

Graphs model relationships using vertices and edges. Directedness, weights, density, and connectivity determine both representation and algorithm choice. Adjacency matrices offer constant-time edge lookup but require quadratic space; adjacency lists use linear-in-vertices-plus-edges space and are generally preferable for sparse graphs; edge lists are convenient for global edge processing.

BFS explores vertices in layers using a queue and finds shortest paths by edge count in unweighted graphs. DFS explores deeply using recursion or a stack and supports structural analysis through discovery and finishing states. DFS detects cycles, while topological sorting orders the vertices of a DAG; Kahn's algorithm provides an alternative indegree-based method. Repeated BFS or DFS identifies connected components in undirected graphs. Strongly connected components in directed graphs can be found by Kosaraju's two-pass method or Tarjan's one-pass method, both in linear time with adjacency lists.

Effective graph engineering requires more than memorizing algorithms. It requires matching the model to the application, accounting for disconnected and cyclic structures, validating complexity assumptions, and protecting sensitive relationship data.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An object or entity represented in a graph.

Edge: A relationship connecting two vertices.

Directed graph: A graph whose edges have orientations.

Undirected graph: A graph whose edges represent two-way relationships.

Weighted graph: A graph whose edges carry values such as cost or distance.

Adjacency matrix: A two-dimensional representation recording edge relationships between every pair of vertices.

Adjacency list: A representation storing the neighbors of each vertex.

Edge list: A collection of records, each representing an edge.

Degree: The number of incident edges of a vertex in an undirected graph.

Indegree: The number of incoming edges to a directed vertex.

Outdegree: The number of outgoing edges from a directed vertex.

Breadth-first search: A queue-based traversal that explores by increasing distance from a source.

Depth-first search: A traversal that explores a path deeply before backtracking.

Connected component: A maximal mutually reachable set in an undirected graph.

Strongly connected component: A maximal set of vertices with directed reachability in both directions between every pair.

Cycle: A closed path in a graph.

Topological ordering: A linear order placing the source of every directed edge before its destination.

Directed acyclic graph: A directed graph containing no directed cycle.

Condensation graph: The DAG formed by contracting each strongly connected component into one vertex.

Review Questions

Short Answer Questions

1. What is the main difference between a directed and an undirected graph?

2. Why are adjacency lists usually preferable for sparse graphs?

3. What data structure does BFS use to control exploration order?

4. What does a gray vertex represent during DFS?

5. Under what condition does a topological ordering exist?

Long Answer Questions

1. Compare adjacency matrices, adjacency lists, and edge lists in terms of space, edge lookup, and traversal performance.

2. Explain BFS and prove why it finds minimum-edge paths in an unweighted graph.

3. Describe DFS edge states and explain how they support directed cycle detection.

4. Present Kahn's topological-sorting algorithm and explain how it detects cycles.

5. Compare Kosaraju's and Tarjan's algorithms for finding strongly connected components.

Analytical / Application Questions

1. A network has 100,000 vertices and 150,000 edges. Recommend a representation and justify your choice using asymptotic space and traversal considerations.

2. Design an algorithm to determine whether a course-prerequisite system is feasible and to produce a valid course order if it is. Explain how cycles are reported.

3. A directed transportation network contains several groups of mutually reachable intersections. Explain how SCC contraction could help an operations team analyze one-way movement between those groups.

Multiple Choice Questions with Answers

Question 1

Which representation provides constant-time testing of whether a particular edge exists, assuming direct indexing?

A. Adjacency matrix

B. Adjacency list

C. Edge list

D. DFS tree

Correct Answer: A. Adjacency matrix

Question 2

Which data structure is fundamental to standard breadth-first search?

A. Stack

B. Queue

C. Priority queue

D. Hash table

Correct Answer: B. Queue

Question 3

In an unweighted graph, BFS discovers a shortest path measured by:

A. Total vertex weights

B. Number of edges

C. Largest edge weight

D. Number of cycles

Correct Answer: B. Number of edges

Question 4

In directed DFS, an edge to a gray vertex indicates:

A. A disconnected component

B. A topological ordering

C. A directed cycle

D. A minimum spanning tree

Correct Answer: C. A directed cycle

Question 5

A topological ordering is guaranteed to exist for:

A. Every directed graph

B. Every undirected graph

C. Every directed acyclic graph

D. Every strongly connected graph

Correct Answer: C. Every directed acyclic graph

Question 6

What does Kahn's algorithm primarily maintain while constructing a topological order?

A. Vertex indegrees

B. DFS finishing times

C. Edge weights

D. Discovery depths only

Correct Answer: A. Vertex indegrees

Question 7

With adjacency lists, BFS or DFS over a graph with n vertices and m edges has time complexity:

A. O(n²) always

B. O(m²)

C. O(n+m)

D. O(log n)

Correct Answer: C. O(n+m)

Question 8

A connected component in an undirected graph is best described as:

A. A maximal set connected by paths

B. A set containing only vertices of degree two

C. A directed cycle

D. A single adjacency-matrix row

Correct Answer: A. A maximal set connected by paths

Question 9

Which statement about strongly connected components is correct?

A. They are defined only for weighted graphs

B. Every pair of vertices in an SCC can reach each other following directions

C. They can exist only in DAGs

D. They require an adjacency matrix

Correct Answer: B. Every pair of vertices in an SCC can reach each other following directions

Question 10

If Kahn's algorithm outputs fewer vertices than the graph contains, what can be concluded?

A. The graph has a cycle

B. The graph is necessarily complete

C. The graph has no edges

D. The graph is undirected

Correct Answer: A. The graph has a cycle