1.
Draw the graph corresponding to the following adjacency matrix.
Section 7.25 Graphs and Graphing Algorithms: Exercises
Exercises Exercises
2.
Draw the graph corresponding to the following list of edges.
| From | To | Cost |
|---|---|---|
| 1 | 2 | 10 |
| 1 | 3 | 15 |
| 1 | 6 | 5 |
| 2 | 3 | 7 |
| 3 | 4 | 7 |
| 3 | 6 | 10 |
| 4 | 5 | 7 |
| 6 | 4 | 5 |
| 5 | 6 | 13 |
3.
Ignoring the weights, perform a breadth-first search on the graph drawn for question 1 or 2.
4.
- \(O(n)\)
-
\(O(n)\) would suggest that there is no nesting. There are several nested
forloops. - \(O(n^2)\)
- Correct. The two consecutively nested
forloops 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
forloops 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.
What is the Big-O running time of the
build_graph function?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.
- \(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{.}\)
What is the Big-O running time for Prim’s minimum spanning tree algorithm?
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.
You have attempted of activities on this page.
