7.25. Discussion Questions¶

1. Draw the graph corresponding to the following adjacency matrix.

1. 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

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

1. What is the Big-O running time of the build_graph function?

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 59)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: BigO

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

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 63)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: BigOTwo

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

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

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

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

2. Express branching factor $$k$$ as a function of the board size $$n$$.

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

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 86)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: DFS

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

1. What is the Big-O running time for Prim’s minimum spanning tree algorithm?