| Graph Search |
About This Exercise
The objectives of this exercise are
- to ensure that you understand the definitions and graph search, specifically depth-first search and breadth-first search, well enough to be able to compare and contrast these search strategies, informally describe the algorithms for these types of search, and trace the executions of these algorithms by hand on small examples;
- to ensure that you understand properties of these search algorithms, notably including properties related to their correctness and efficiency.
Students should read through and try to solve the problems on this exercise before attending the tutorial.
Expected Background
This is based on lectures on depth-first search and on breadth-first search that were presented in class. A lecture supplement on breadth-first search completes a proof of the correctness of this algorithm and might also be helpful.
Chapter 22 of Cormen, Leiserson, Rivest and Stein’s text, Introduction to Algorithms, include more information about these algorithms and was the primary reference for an earlier version of the the course notes on this topic. University of Calgary students can read this book online.
Finally, the Wikipedia pages on depth-first search and breadth-first search include quite a bit more information about this topic and are recommended.
Warmup Problems — To Check That You Understand the Basics
It is expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course and attended the lectures in which graph search was introduced (reviewing the online notes, as needed).
These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.
-
Give definitions of each of the following.
- a connected component of a graph
- depth-first search
- breadth-first search
-
Briefly describe what the DFS algorithm does.
Then trace the execution of DFS(G, 0) on each of the following graphs G.
-
-
Briefly describe what the BFS algorithm does.
Then trace the execution of BFS(G, 0) on each of the graphs given in the previous question.
-
As discussed in lectures there will generally be more than one depth-first search tree corresponding to a given undirected graph G and vertex s. Why is that the case?
Is this true for breadth-first search trees, as well? Why (or why not)?
On the other hand, some of the other information that some of these algorithms compute is unique. Which is information is this, and why is it unique?
To Be Discussed in The Tutorial
-
Recall that an argument was given that each of the search algorithms that were discussed uses O(|V| + |E|) operations in the worst case, when it is applied to a graph G = (V, E).
-
Explain why this is the case.
-
Explain why these algorithms also use Ω(|V| + |E|) operations, in the best case, if the graph is connected.
-
Give a better bound on the number of steps used by these algorithms on inputs G and s, for a vertex s, if the graph is not connected.
-
Finally, consider an algorithm to find a spanning forest of a graph, including a spanning tree for each connected component of the graph, as follows:
- Colour each vertex white.
- For each vertex, run a search using this vertex as the second input, without changing colours back to white, if the vertex is still white when it is considered in this iteration. Skip over the vertex (without doing anything more) otherwise.
Use your answers for the previous parts of this question to show that this algorithm uses O(|V| + |E|) operations when run on a graph G = (V, E), as well.
-
-
Modify the BFS algorithm, by changing the data structure that is used as well as a few (minor) details in the algorithm, to produce an algorithm for a depth-first search in a graph that is not recursive.
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial21.html |