Exercise Solutions

Problem Set Solutions

1. What are the vertices and edges in the graph below? Include colour labels for the vertices.

   

   Solution: The vertices are $\{1,\text{pink}\},\{3,\text{pink}\},\{6,\text{purple}\},\{7,\text{blue}\},\{D,\text{blue}\},\{M,\text{yellow}\},$ $\{W,\text{purple}\}$. The edges are $\{1,7\},\{1,D\},\{1,M\},\{3,7\},\{3,D\},\{6,D\},\{D,M\},\{D,W\}$.

2. List the neighbourhoods of all the vertices in the graph in question 1.

   Solution: The neighbourhood for vertex $1$ is $7,D,M$. The neighbourhood for vertex $3$ is $7,D$. The neighbourhood for vertex $6$ is $D$. The neighbourhood for vertex $7$ is $1,3$. The neighbourhood for vertex $D$ is $1,3,6,M,W$. The neighbourhood for vertex $M$ is $1,D$. Finally, the neighbourhood for vertex $W$ is $D$.

3. Do BFS on the graph below until all the vertices are coloured black. Start at vertex $H$ and pick neighbours from right-to-left (in other words, visually from the right side of the graph to the left). What order did you look at the vertices?

   

   Solution: The order that the vertices were looked at should be $H,G,B,E,D,C,F,A$.

4. Do DFS on the graph in question 3 until all the vertices are coloured black. Start at vertex $E$ and pick neighbours alphabetically. What order did you look at the vertices?

   Solution: The order that the vertices were looked at should be $E,H,B,C,A,B,G,D,F,H$.

5. Search for vertex $F$ starting from vertex $A$ using BFS for the following graph, picking neighbours alphabetically. What order did you look at the vertices?

   

   Solution: The order that the vertices were looked at should be $A,C,B,E,D,F$.

6. For the graph in question 5, would it be faster to find vertex $G$ from vertex $B$ using BFS or DFS if you pick neighbours from left-to-right? What about from right-to-left?

   Solution: Picking neighbours from left-to-right, the ordered list for BFS should be $B,C,A,E,D,F,G$ and the ordered list for DFS should be $B,C,A,C,E,D,E,F,G$. Therefore, BFS is faster because there is no need to backtrack. Picking neighbours from right-to-left, the ordered list for BFS should be $B,C,E,A,G$ and the ordered list for DFS should be $B,C,E,G$. Therefore, DFS is faster because we didn’t have to look at $A$.

7. 1. Search through the whole graph below three times using BFS. Pick neighbours alphabetically and use the starting points $G$, $A$, and $E$. List the order that you look at the vertices for those three searches. What do you notice about the length of the lists of vertices?

   2. Search through the whole graph below three times using DFS. Pick neighbours alphabetically and use the starting points $G$, $A$, and $E$. List the order that you look at the vertices for those three searches. What do you notice about the length of the lists of vertices?

      

   Solution:

   1. With the starting point $G$, the order that the vertices were looked at should be $G,D,B,A,C,E,F,H$. With the starting point $A$, the order that the vertices were looked at should be $A,B,C,D,E,F,G,H$. With the starting point $E$, the order that the vertices were looked at should be $E,C,F,H,A,B,D,G$. The lists of vertices are all the same length, $8$ items. We can come to the conclusion that BFS will always give ordered lists of the same length because each vertex is only looked at once.

   2. With the starting point $G$, the order that the vertices were looked at should be $G,D,B,A,C,E,F,E,H,C$. With the starting point $A$, the order that the vertices were looked at should be $A,B,D,G,A,C,E,F,E,H,C$. With the starting point $E$, the order that the vertices were looked at should be $E,C,A,B,D,G,E,F,E,H$. The lists of vertices are not all the same length, two of them have $10$ items and one has $11$ items. We can come to the conclusion that DFS will give ordered lists of different length because more backtracking will add more items to the ordered list.

8. 1. Compare your lists from part (a) and part (b) in question 7 for each separate starting point. Which vertices can be found faster using BFS from the starting point $G$? What about for the staring points $A$ and $E$?

   2. Compare your lists from part (a) and part (b) in question 7 for each separate starting point. Which vertices can be found faster using DFS from the starting point $G$? What about for the staring points $A$ and $E$?

   3. Compare your lists from part (a) and part (b) in question 7 for each separate starting point. Are there any vertices found in the same order or at the same time between using BFS and DFS from the starting point $G$? What about for the staring points $A$ and $E$?

   Solution:

   1. From starting point $G$, the vertex $H$ can be found faster using BFS. From starting point $A$, the vertices $C$, $E$, $F$, and $H$ can be found faster using BFS. Lastly, from starting point $E$, the vertices $F$ and $H$ can be found faster using BFS.

   2. From starting point $G$, no vertices can be found faster using DFS. From starting point $A$, the vertices $D$ and $G$ can be found faster using DFS. Lastly, from starting point $E$, the vertices $A$, $B$, $D$, and $G$ can be found faster using DFS.

   3. From starting point $G$, the vertices $G,D,B,A,C,E,$ and $F$ are found at the same time and in the same order between using BFS or DFS. From starting point $A$, the vertices $A$ and $B$ are found at the same time and in the same order between using BFS or DFS. Lastly, from starting point $E$, the vertices $E$ and $C$ are found at the same time and in the same order between using BFS or DFS.