Graphs

Prev: Greedy Algorithms and Invariants Next: Parallel Computing

Problems

19.1

A maze can be viewed as a 2D array whose entries are either black or white. White entries are open squares, black entries are walls. Given two white entries corresponding to an entrance and an exit, write a program that finds a path from the entrance to the exit, if one exists.

Hint: Model the maze as a graph.

---

19.2

Let $A$ be a Boolean $2$D array encoding a black-and-white image. Two entries are adjacent if one is directly above, below, to the left, or to the right of the other. Define the region associated with a point $(i,j)$ to be all points of the same color that are reachable from $(i,j)$ through a path of adjacent entries of that same color.

Implement a routine that takes an $n\times m$ Boolean array $A$ together with an entry $(x,y)$ and flips the color of the entire region associated with $(x,y)$.

---

19.3

Let $A$ be a $2$D array whose entries are either $W$ or $B$. A white entry is enclosed if there is no path from it to the boundary that passes only through white entries.

Write a program that takes $A$ and replaces every enclosed $W$ with a $B$.

Hint: It is easier to compute the complement of the desired result.

---

19.4

High-performance database systems may use resource locking and therefore need deadlock detection. One standard model is a wait-for graph: processes are vertices, and there is an edge from process $P$ to process $Q$ if $Q$ holds a resource that $P$ is waiting for. A cycle in this directed graph implies the possibility of deadlock.

Write a program that takes as input a directed graph and checks whether the graph contains a cycle.

Hint: Focus on back edges.

Variant: Solve the same problem for an undirected graph.

Variant: Write a program that takes as input a connected undirected graph and checks whether it remains connected if any one edge is removed.

---

19.5

Consider a vertex type for a directed graph in which each vertex has an integer label and a list of references to other vertices. Design an algorithm that takes a reference to a vertex $u$, creates a copy of the graph induced by the vertices reachable from $u$, and returns the copy of $u$.

Hint: Maintain a map from vertices in the original graph to their counterparts in the clone.

---

19.6

Consider a collection of electrical pins on a printed circuit board. For each pair of pins, there may or may not be a wire joining them. Design an algorithm that takes a set of pins and a set of wires connecting pairs of pins, and determines whether it is possible to place some pins on the left half of the board and the rest on the right half so that every wire goes between the two halves. Return such a division if one exists.

Hint: Model the instance as a graph and think about the implication of an odd-length cycle.

---

19.7

Let $s$ and $t$ be strings and let $D$ be a dictionary, i.e., a set of strings. Define $s$ to produce $t$ if there exists a sequence of dictionary strings $P=⟨s_0,s_1,\dots ,s_{n-1}⟩$ such that the first string is $s$, the last string is $t$, and adjacent strings have the same length and differ in exactly one character.

Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine whether $s$ produces $t$. If it does, output the length of a shortest production sequence; otherwise, output $-1$.

Hint: Treat strings as vertices in an undirected graph, with an edge between $u$ and $v$ if and only if the corresponding strings differ in one character.

---

19.8

How would you generalize your solution to Problem 14.8 to determine the largest number of teams that can be photographed simultaneously subject to the same constraints?

Hint: Form a DAG in which paths correspond to valid placements.

---

19.9

In the usual shortest-path problem, the number of edges on the path is not part of the objective. Design an algorithm that takes as input a graph $G=(V,E)$, directed or undirected, a nonnegative cost function on $E$, and vertices $s$ and $t$, and outputs a path with the fewest edges among all shortest paths from $s$ to $t$.

Hint: Change the edge cost and cast it as an instance of the standard shortest-path problem.

Variant: A flight is specified by a start time, origin city, destination city, and arrival time. Given a timetable, a starting city, a starting time, and a destination city, compute the soonest you can reach the destination city, assuming flights start and end on time, you need 60 minutes between flights, and a flight from $A$ to $B$ cannot arrive earlier than another flight from $A$ to $B$ that departed earlier.

Answers

19.1

Treat each white cell as a vertex and connect orthogonally adjacent white cells. Then run DFS or BFS from the entrance while marking visited cells. If the exit is reached, return the path reconstructed from the search; otherwise no path exists. This is $O(V+E)$, which is $O(mn)$ for an $m\times n$ maze.

---

19.2

Do a flood fill from $(x,y)$ over cells of the original color, using BFS or DFS, and flip each reachable same-color cell as it is visited. Since each cell is processed at most once, the running time is $O(mn)$ in the worst case.

---

19.3

It is easier to find the white cells that should remain white: start a BFS or DFS from every white boundary cell and mark all white cells reachable from the boundary. After that, scan the interior and flip every unmarked white cell to black. This is linear in the grid size.

---

19.4

Run DFS while maintaining the standard white-gray-black coloring. Encountering an edge to a gray vertex means there is a back edge, hence a directed cycle. If no such edge is found in any DFS tree, the graph is acyclic. The algorithm is $O(V+E)$.

---

19.5

Traverse the reachable subgraph from $u$ with BFS or DFS while maintaining a hash table from each original vertex to its clone. When an unseen vertex is discovered, allocate its copy; whenever an edge $v\to w$ is examined, append the cloned edge from clone$(v)$ to clone$(w)$. This clones the reachable graph in $O(V+E)$ time.

---

19.6

This is the bipartite-graph test. Run BFS from each unvisited vertex and assign vertices to sides by parity of distance from the BFS root. If an edge ever connects two vertices at the same parity, the graph contains an odd cycle and no such placement exists. Otherwise the parity classes give the required left-right partition.

---

19.7

View dictionary words as graph vertices, with edges between words that differ in exactly one position. Then the problem is shortest path in an unweighted graph, so BFS from $s$ gives the minimum number of transformations to every reachable word and in particular to $t$. Generate neighbors by trying all one-character substitutions and checking dictionary membership. This avoids building all edges explicitly.

---

19.8

Build a DAG whose vertices are teams, with an edge from team $X$ to team $Y$ if $X$ can stand behind $Y$. Any feasible multi-team photo corresponds to a path in this DAG, so the answer is the length of the longest path. Compute it by topologically ordering the DAG and doing the standard longest-path DP over that order.

---

19.9

Replace each edge weight $c$ by the pair $(c,1)$ and compare path lengths lexicographically: first by total cost, then by number of edges. Run Dijkstra’s algorithm using this pair-valued distance. The shortest path under this ordering is exactly a minimum-cost path with the fewest edges among all such minimum-cost paths.