In a directed graph G = (V, E), a vertex v is called middle if and only if for e
ID: 3750586 • Letter: I
Question
In a directed graph G = (V, E), a vertex v is called middle if and only if for every vertex x in V either there exists a directed path from v to x, or there exists a directed path from x to v.
(a) Given a directed acyclic graph G and a vertex u in V, provide an O(|V |+|E|) time algorithm for determining whether or not vertex u is middle in G. (3 marks)
(b) (This part is optional, it may be completed for bonus marks) Given an acyclic directed graph G = (V, E) provide an O(|V | + |E|) time algorithm for computing all the middle vertices of G. (4 bonus marks)
(c) (When doing this part you may assume a solution to part (b) is available) Given a general directed graph G = (V, E) provide an O(|V | + |E|) time algorithm for computing all the middle vertices of G. (4 marks, for 2 marks provide a correct but slower algorithm)
Explanation / Answer
Hello,
In the question, the middle vertices act as a source to the graph. Thus, to check whether a vertex is a middle vertex would simply entail running a DFS/BFS algorithm on G to check whether all vertices are reachable from the given vertex.
Thus, to answer subquestion one, start from the given vertex on the graph. Maintain an array storing the visited vertices (it will initially only contain the given vertex.) As you proceed to explore, keep adding a vertex to the array if it is not a member already. Hence, if the current node leads you to two vertices, v1, and v2 where v1 is a part of the VISITED array, and v2 isn't: Just add v2 in the array. Explore the nodes you add to the array in each iteration. The stopping condition would be the step when no new nodes are added to the VISITED array. The algorithm is well documented and has a time complexity of O(V + E).
What works for third shall surely work for the second subquestion. A naive approach would be to check and see all vertices for the property of the middle value. However, an optimized approach is possible. We can safely assume that a middle vertice, if any, shall have the largest possible traversal time in an acyclic graph.
Hence, we simply need to prove that there does not exist a "non middle" vertex that completes traversals after a middle vertex, i.e, there does not exist a non middle vertex y and a middle vertex x such that there is an edge from x to y (x --> y).
Thus, make recursive DFS calls. If the call for y occurs before x, and edge (y --> x) exists, then x finishes after y (middle finishes after its connected nodes).
Else, if x occurs before y and edge (y --> x) exists, then the assumption that x is a middle node is incorrect (which cannot be as the middle node finishes last) or that y also is a middle node.
Since each step has a time complexity f O(V+E), the corresponding time complexity is O(V+E).
Please find the code below for reference.
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.V = vertices
self.graph = defaultdict(list)
def DFSUtil(self, v, visited):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
def addEdge(self, v, w):
self.graph[v].append(w)
def Middle(self):
visited =[False]*(self.V)
v=0
for i in range(self.V):
if visited[i]==False:
self.DFSUtil(i,visited)
v = i
visited = [False]*(self.V)
self.DFSUtil(v, visited)
if any(i == False for i in visited):
return -1
else:
return v
g = Graph(7)
g.addEdge(6, 4)
g.addEdge(5, 6)
g.addEdge(5, 2)
g.addEdge(6, 0)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(4, 1)
print ("A middle vertex is " + str(g.Middle()))
Hope this is helpful.