Week 9 Studio Sheet (Solutions)
Useful advice: The following solutions pertain to the theoretical problems given in the tutorial classes. You are strongly advised to attempt the problems thoroughly before looking at these solutions. Simply reading the solu- tions without thinking about the problems will rob you of the practice required to be able to solve complicated problems on your own. You will perform poorly on the exam if you simply attempt to memorise solutions to the tutorial problems. Thinking about a problem, even if you do not solve it will greatly increase your understanding of the underlying concepts. Solutions are typically not provided for Python implementation questions. In some cases, psuedocode may be provided where it illustrates a particular useful concept.
Implementation checklist
Assessed Preparation
Problem1. ImplementadirectedgraphclassinPython.Yourgraphshoulduseanadjacencylistrepresentation
and should support the following operations:
• Initialise the graph with n vertices, where n is a given parameter
• Addadirected,weightededgebetweentheverticesuandv,withweightw
You may wish to make an internal class for your edge data, to improve readability.
Problem 2. Label the vertices of the following graph in the order that they might be visited by a depth-first
search, and by a breadth-first search, from the source s .
It will be most beneficial for your learning if you have completed this checklist before the studio.
By the end of week 9, write Python code for • Breadth-firstsearch
• Depth-Firstsearch3
There are two possible solutions for depth-first search depending on which order you traverse the edges. One valid order is the following.
The other valid order is to visit 8 & 9 before 2 & 3. A valid order for breadth-first search is the following. 2467
The other valid order swaps nodes 2 and 3 with each other, and nodes 4 and 5 with each other.
Problem 3. Consider an undirected connected graph G . In plain words, describe how can you use depth-first search to find whether the graph G has a cycle or not.
If at any point during depth-first search, the algorithm finds an edge that leads to a vertex which has already been visited, then there must be a cycle in the graph. For more details, see Cycle-finding in Chapter 12.3 of the unit notes.
Studio Problems
Problem4. Writepsuedocodeforanalgorithmthatgivenadirectedgraphandasourcevertex,returnsalistof
all of the vertices reachable in the graph from that source vertex. Your algorithm should run in O (V + E ) time. Solution
This problem can be solved with a depth-first search or breadth-first search. The vertices reachable from a given vertex are simply those that are visited by a search when that vertex is the starting node. So we simply perform a DFS from s and then return a list of the nodes that were visited.
1: functionREACHABLE(G=(V,E),s)
2: Set visited[1..n ] = False
4: Set reachable = empty array
5: foreachvertexu=1ton do
6: if visited[u] then
7: reachable.append(u)
9: end for
10: return reachable
11: endfunction
13: functionDFS(u)
14: 15: 16: 17: 18: 19: 20:
visited[u] = True
for each vertex v adjacent to u do
if not visited[v] then DFS(V)
end if end for
endfunction
Problem 5. Devise an algorithm for determining whether a given undirected graph is two-colourable. A graph is two-colourable if each vertex can be assigned a colour, black or white, such that no two adjacent vertices are the same colour. Your algorithm should run in O (V + E ) time. Write psuedocode for your algorithm
To two colour a graph, the key observation to make is that once we pick a colour for a particular vertex, the colours of all of its neighbours must be the opposite. That is, once we decide on a colour for one vertex, all other reachable vertices must be set accordingly, we do not get to make any more decisions. Secondly, it does not matter whether we decide to set the first vertex to white or to black, since changing from one to the other will just swap the colour of every other vertex. With these observations in mind, we can proceed greedily.
Let’s perform depth-first search on the graph, and for each vertex, if it has not been coloured yet, select an arbitrary colour and then recursively colour all of its neighbours the opposite colour. If at any point a vertex sees that one of its neighbours has the same colour as it, we know that the graph is not two- colourable. Here is some psuedocode that implements this idea.
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:
functionTWO_COLOUR(G=(V,E)) Set colour[1..n] = null foreachvertexu=1ton do
if colour[u] = null then
if DFS(u, BLACK) = False then
return False end if
end if end for
return True, colour[1..n ] endfunction
//Returnstrueifthecomponentwassuccessfullycoloured functionDFS(u,c)
colour[u] = c
for each vertex v adjacent to u do
if colour[v] = c then // A neighbour has the same colour as us! return False
else if colour[v] = null and DFS(v, opposite(c)) = False then return False
end if end for
return True endfunction
Here, opposite(c) is a function that returns WHITE or BLACK if c is BLACK or WHITE respectively. Problem6. ThisproblemisaboutcyclefindingasdiscussedinSection12.3oftheunitnotes.
(a) Explainusinganexamplewhythealgorithmgivenforfindingcyclesinanundirectedgraphdoesnotwork when applied to a directed graph
(b) Describe an algorithm based on depth-first search that determines whether a given directed graph con- tains any cycles. Your algorithm should run in O (V + E ) time. Write psuedocode for your algorithm
The undirected cycle finding algorithm works by checking whether the depth-first search encounters an edge to a vertex that has already been visited. This works fine for undirected graphs, but when the graph is directed, this might yield false positives since there could be multiple paths to the same vertex with the
edges in the same direction, which does not constitute a cycle. For example, the algorithm would falsely identify this as a cycle:
To correct this, we need to think a bit more carefully about the edges that depth-first search examines during traversal. In a different example like the following, the cycle a , b , d if identified would in fact be correct,whileb,c,e,d wouldnot.
How do we distinguish between the two? Suppose that the edges traversed by the search are those de- noted in red below.
The critical observation is that when the search looks along the edge (d , e ) and sees that e has already been visited, we see that the branch that visited e is a different branch than the one that visited d . Because of this, the edges will be in the same direction, and hence not a cycle. However, when the search looks along the edge (d,a) and notices that a has already been visited, we observe that a is a parent of the current branch of the search tree. This means that there is a path from a d , and since we just discovered an edge d → a , we have found a directed cycle!
So, to write an algorithm for directed cycle finding we need to perform a depth-first search and keep track of which branches of the search tree are still active, and which ones are finished. Whenever we encounter an edge to an already visited vertex, we identify it as a cycle only if the target vertex is still active, otherwise it is part of a different branch and hence not part of a cycle. Therefore instead of marking each vertex as visited or not, we will have three possible states, unvisited, inactive, and active. A vertex is active if its descendants are still being explored. Once we finish exploring a node’s descendants, we mark it as inactive. The algorithm might then look like the following
1: 2: 3: 4: 5: 6: 7:
functionCYCLE_DETECTION(G=(V,E)) Set status[1..n] = Unvisited foreachvertexu=1ton do
if status[u] == Unvisited and DFS(u) then return True
end if end for
9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
return False endfunction
functionDFS(u)
status[u] = Active
for each vertex v adjacent to u do
if status[v] = Active then // We found a cycle return True
else if status[v] = Unvisited and DFS(v) = True then return True
end if end for
status[u] = Inactive
return False endfunction
// Finished this branch – mark as inactive
Problem 7. Recall from lectures that breadth-first search can be used to find single-source shortest paths on unweighted graphs, or equivalently, graphs where all edges have weight one. Consider the similar problem where instead of only having weight one, edges are now allowed to have weight zero or one. We call this the zero-one shortest path problem. Write psuedocode for an algorithm for solving this problem. Your solution should run in O (V + E ) time (this means that you can not use Dijkstra’s algorithm!) [Hint: Combine ideas from breadth-first search and Dijkstra’s algorithm]
Recall that in a breadth-first search, vertices are visited in order by their distance from the source vertex. Suppose that the vertex at the front of the queue has distance d . Any unvisited adjacent vertices will be inserted into the back of the queue at distance d + 1. This implies that the queue maintained by BFS always contains vertices that are at most one distance different. In essence, the queue contains vertices on the current level at the front, and vertices on the next level at the back.
We wish to modify BFS to allow it to handle edges with zero weight. Notice that if we wish to traverse an edge of zero weight, that the target vertex will have the same distance as the current distance. Therefore we would simply like to insert this vertex not at the back, but at the front of the queue! To support this, we could use a data structure called a “deque”. A deque is short for double-ended queue, which simply means a queue that can be inserted and removed from at both ends. A deque can be implemented quite easily using a standard dynamic array. Alternatively, if you do not wish to use a deque, you can simply maintain two queues, one for the vertices at the current distance d , and one for the vertices at the next distance d + 1.
Another interpretation of this algorithm is as a modification of Dijkstra’s. Dijkstra’s algorithm would solve this problem, but in O ((V + E ) log(V )) complexity, which is a log factor too high due to the use of a heap- based priority queue. However, as per the observation above, the queue for this algorithm will only ever contain vertices at distance d and distance d + 1, hence we only need a priority queue that supports having at most two keys at once. Having a double-ended queue and appending the higher keys onto the end and the smaller keys onto the front satisfies this requirement.
Finally, note that unlike ordinary BFS, we also have to check the distances when visiting neighbours now since we can not guarantee that the first time we discover a vertex that we necessarily have the smallest distance (since we may discover it via a weight one edge when someone else can reach it via a weight zero edge). This is similar to how Dijkstra’s algorithm relaxes outgoing edges. A psuedocode implementation in presented below.
1: functionZERO_ONE_BFS(G=(V,E),s)
2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
Set dist[1..n ] = ∞
Set pred[1..n ] = null
Set deque = Deque() deque.push((s, 0))
dist[s] = 0
while deque is not empty do
u, d = deque.pop()
if d = dist[u] then // Ignore entries in the queue for out-of-date distances (like Dijkstra’s)
for each vertex v adjacent to u do
if dist[u] + w(u,v) < dist[v] then
dist[v] = dist[u] + w(u,v)
pred[v] = u
ifw(u,v)=0thendeque.push_front((v,dist[v])) //Addtothefrontofthequeue
else deque.push_back((v, dist[v])) end if
end for end if
end while endfunction
// Add to the back of the queue
There are other ways to solve this problem. One very different solution is to perform a depth-first search on the graph and find all of the components that are connected by zero-weight edges. Since vertices in these components can reach each other with zero distance, they will all have the same distances in the answer, hence these components can be contracted into single vertices, and then we can perform an ordinary breadth-first search on this contracted graph.
Problem 8. Describe an algorithm for finding the shortest cycle in an unweighted, directed graph. A shortest cycle is a cycle with the minimum possible number of edges. You may need more than linear time to solve this one. Write psuedocode for your algorithm.
Since we are asking for the shortest cycle, the first thing that we should try is breadth-first search since it visits vertices in order of distance. Suppose that we run the ordinary cycle detection algorithm but using a breadth-first search in place of depth-first search. Will this find the shortest cycle for us? Unfortunately not. See the following example in which we start the search from the source s .
Thecyclea,b,c,d isoflengthfourandadistanceofonefromthesource,anditwillbefoundbythetime the search reaches a distance five. However, the shortest cycle f , g , h is distance five away, and will not be found until the search reaches distance eight.
To fix this, let’s simply perform multiple breadth-first searches, one from every possible source vertex. If the source vertex is contained within a cycle of length k , then the cycle will be detected when the search reaches distance k, before any longer cycle has had a chance to be detected. By trying every possible source, we are therefore guaranteed to find the shortest cycle. This solution will take O (V (V + E )) time
since we perform |V | breadth-first searches and each one takes O (V + E ) time.
Notice finally that if we are searching from a vertex contained inside the shortest cycle, then the first already-visited vertex encountered will in fact be the source itself, so we can just check for that in our implementation.
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
functionSHORTEST_CYCLE(G=(V,E))
Set best_found = ∞
for each vertex s = 1 to n do // Try every vertex as the source
best_found = min(best_found, BFS(s)) end for
return best_found endfunction
functionBFS(s)
Set dist[1..n ] = ∞
dist[s] = 0
Set queue = Queue() queue.push(s)
while queue is not empty do
u = queue.pop()
for each vertex v adjacent to u do
ifv=sthen //Wemadeitbacktothesource–wefoundacycle! return dist[u] + 1
else if dist[v] == ∞ then dist[v] = dist[u] + 1 queue.push(v)
end if end for
return ∞ endfunction
Have a think about how you would solve this problem for undirected graphs. The same general ideas work, but some extra care is needed to account for some situations that do not appear in the directed case.
Supplementary Problems
Problem9. Writepsuedocodeforanon-recursiveimplementationofdepth-firstsearchthatusesastackinstead
of recursion.
The function looks almost identical to the recursive version. We simply replace the recursive calls by pushing the corresponding vertex onto the stack, and loop until the stack is empty.
1: 2: 3: 4: 5:
functionDFS(u)
Create empty stack stack.push(u)
while stack is not empty do
u = stack.pop()
6: 7: 8: 9:
10: 11: 12: 13:
visited[u] = True
for each vertex v adjacent to u do
if not visited[v] then stack.push(v)
end if end for
end while endfunction
Problem10. Writepsuedocodeforanalgorithmthatcountsthenumberofconnectedcomponentsinanundi- rected graph that are cycles. A cycle is a non-empty sequence of edges (u1,u2),(u2,u3),...(uk,u1) such that no vertex or edge is repeated.
To solve this problem, we notice that for a component to be a cycle, it must be the case that the degree (number of adjacent edges) of every vertex is exactly two. Armed with this fact, the solution to this prob- lem is to perform a depth-first search much like the ordinary connected components algorithm and add in a check to see whether the degree of a vertex is not two.
1: 2: 3: 4: 5: 6: 7: 8: 9:
10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
functionCOUNT_CYCLE_COMPONENTS(G=(V,E)) Set visited[1..n] = False
Set num_components = 0 foreachvertexu=1ton do
if visited[u] == False then if DFS(u) then
num_components = num_components + 1 end if
end if end for
return num_components endfunction
//Returntrueifthecomponentcontaininguisasimplecycle functionDFS(u)
visited[u] = True
Set is_cycle = True if degree(u) = 2 else False for each vertex v adjacent to u do
if visited[v] == False then if DFS(v) = False then
is_cycle = False end if
end if end for
return is_cycle endfunction
Problem11. Inthisquestionweconsideravariantofthesingle-sourceshortestpathproblem,themulti-source shortest path problem. In this problem, we are given an unweighted graph and a set of many source vertices. We wish to find for every vertex v in the graph, the minimum distance to any one of the source vertices. Formally,
given the sources s1,s2,...sk , we wish to find for every vertex v d[v]= mindist(v,si).
Describe how to solve this problem using a modification to breadth-first search. Your algorithm should run in
O(V +E)time. Solution
The solution to this problem is rather simple. We perform a breadth-first search on the graph, but instead of beginning with a single vertex in the queue at distance zero, we place all of the given source vertices in the queue with distance zero. The algorithm then proceeds exactly the same. This works because the breadth-first search will discover all of the vertices that are a distance one from every source vertex before discovering vertices of distance two and so on. If a vertex has already been discovered via another source, then the breadth-first search can safely ignore it since the first source to find it must be the closest one.
An alternate solution is to add a new super source vertex to the graph and connect it to all of the given sources. After performing breadth-first search from the super source, the distances to all of the vertices will be one greater than the answer, since we had to travel along one additional edge from the super source to the real sources. Therefore we can subtract one from each of the distances and return those.
Problem12. Recallthedefinitionoftwo-colourabilityfromProblem5.Describeanalgorithmforcountingthe number of valid two colourings of a given undirected graph.
First, run the algorithm from Problem 5 to check whether the graph is two colourable at all. If it is not, return zero. Otherwise, observe that after selecting a colour for a vertex, every other vertex in the same component is fixed to a particular colour. We can therefore colour each component two ways, hence the total number of possible colourings is
2number of connected components.
We can compute the number of connected components using depth-first search, so this algorithm takes
O(V +E)time.
Problem 13. Argue that the algorithm given in the course notes for detecting whether an undirected graph
contains a cycle actually runs in O (V ) time, not O (V + E ) time, i.e. its complexity is independent of |E |. Solution
If the given graph is acyclic, then E ≤ V − 1, so the ordinary depth-first search complexity of O (V + E ) is just O (V ). If instead the graph contains a cycle, then the depth-first search will find it as soon as it examines an edge to an already-visited vertex. Up until this point, none of the edges examined led to already-visited vertices, so they formed a forest of depth-first search trees, which means that there were at most V −1 of them. After we examine the cycle-producing edge, the algorithm immediately terminates, and hence it did at most O (V ) work in total.
Problem 14. (Advanced) Given a directed graph G in adjacency matrix form, determine whether it contains a “universal sink” vertex. A universal sink is a vertex v with in-degree |V |−1 and out-degree 0,