# Problem Solving with Algorithms and Data Structures using Java: The Interactive Edition

## Section7.25Graphs and Graphing Algorithms: Exercises

### ExercisesExercises

#### 1.

Draw the graph corresponding to the following adjacency matrix.

#### 2.

Draw the graph corresponding to the following list of edges.

#### 3.

Ignoring the weights, perform a breadth-first search on the graph drawn for question 1 or 2.

#### 4.

What is the Big-O running time of the build_graph function?
• $$O(n)$$
• $$O(n)$$ would suggest that there is no nesting. There are several nested for loops.
• $$O(n^2)$$
• Correct. The two consecutively nested for loops would dictate that this is in the realm of $$O(n^2)$$
• $$O(1)$$
• $$O(1)$$ would suggest that the function is constant. Since there are multiple for loops intertwined, it is not in constant time.
• $$O(n^3)$$
• $$O(n^3)$$ would suggest that there are three consecutively nested for loops. There are only two.

#### 5.

Derive the Big-O running time for the topological sort algorithm.

#### 6.

Derive the Big-O running time for the strongly connected components algorithm.

#### 7.

Show each step in applying Dijkstra’s algorithm to the graph drawn for question 1 or 2.

#### 8.

Using Prim’s algorithm, find the minimum weight spanning tree for the graph drawn for question 1 or 2.

#### 9.

Draw a dependency graph illustrating the steps needed to send an email. Perform a topological sort on your graph.

#### 10.

Express branching factor $$k$$ as a function of the board size $$>n\text{.}$$

#### 11.

Derive an expression for the base of the exponent used in expressing the running time of the knights tour.

#### 12.

Explain why the general DFS algorithm is not suitable for solving the knight’s tour problem.

#### 13.

What is the Big-O running time for Prim’s minimum spanning tree algorithm?
• $$O(1)$$
• $$O(1)$$ would mean that the algorithm runs in constant time. This isn’t true because there are several comparisons happening in the algorithm.
• $$O(n^3)$$
• $$O(n^3)$$ suggests that there are three consecutively nested loops. If you look at the example algorithm, you can see that there are not three nested loops.
• $$O(n)$$
• $$O(n)$$ is linear time. The time it takes for this program to run doesn’t grow linearly.
• $$O(n^2)$$
• Correct. Since you are not only comparing the weight of a branch but also if the branch has already been connected to, this would make the Big-O of the algorithm $$O(n^2)\text{.}$$

#### 14.

Modify the depth-first search function to produce a topological sort.

#### 15.

Write the transpose method for the Graph class.

#### 16.

Modify the depth-first search to produce strongly connected components. Hint: produce an ArrayList<ArrayList<T>> (where T is your data type). The main ArrayList contains one ArrayList per forest, with each forest containing the keys for that forest.

#### 17.

Using breadth-first search, write an algorithm that can determine the shortest path from each vertex to every other vertex. This is called the “all pairs shortest path problem.”

#### 18.

Using breadth-first search revise the maze program from Chapter 4 to find the shortest path out of a maze.