# 代写代考 FIT2004 Week 9 Studio Sheet (Solutions) – cscodehelp代写

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
and should support the following operations:
• Initialise the graph with n vertices, where n is a given parameter
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
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