Exercise 1
What are the vertices and edges in the graph below? What is the neighbourhood of \(B\)?
What are the vertices and edges in the graph below? What is the neighbourhood of \(B\)?
The vertices in the graph are \(A,B,K,L,T,Y,Z\). The edges in the graph are \(\{A,Y\},\{B,K\},\{B,L\},\{B,T\},\{K,Z\}, \{Y,Z\}\). The neighbourhood of \(B\) is \(K,L,T\).
What is the queue for each of the five graphs above?
The queue for the first graph is \(Q=H,C,E,G\). The queue for the second graph is \(Q=C,E,G\). The queue for the third graph is \(Q=E,G\). The queue for the fourth graph is \(Q=G\). Finally, the queue for the fifth graph is empty.
For the same graph as above, use BFS to do the following searches. Add neighbours to the queue in alphabetical order for both searches and list the order that you looked at the vertices.
Search for vertex \(H\) starting from vertex \(B\).
Search for vertex \(E\) starting from vertex \(F\).
The order that the vertices were looked at should be \(B,A,C,D,F,H\).
The order that the vertices were looked at should be \(F,A,H,B,D,C,E\).
For the same graph as above, use DFS to do the following searches. Choose neighbours in alphabetical order for both searches and list the order that you looked at the vertices.
Search for vertex \(H\) starting from vertex \(B\).
Search for vertex \(E\) starting from vertex \(F\).
How do the ordered lists using DFS in this exercise compare to the ordered lists using BFS in Exercise 3? Which search method is quicker for each search?
The order that the vertices were looked at should be \(B,A,D,E,C,D,G,A,F,H\).
The order that the vertices were looked at should be \(F,A,B,C,E\).
For search (a), BFS is faster. For search (b), DFS is faster. The answer for other comparisons may vary. A few things that could have been said are:
The BFS and DFS for the searches start with the same two letters (\(B,A\) and \(F,A\)).
Vertex \(E\) appears in the DFS for (a) but not the BFS for (a). This could be done with other vertices too, like vertex \(H\) appears in BFS for (b) but not DFS for (b).
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\}\).
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\).
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\).
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\).
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\).
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\).
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?
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:
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.
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.
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\)?
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\)?
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:
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.
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.
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.