Thank you for helping with this question. The in-degree of a node v in a directe

Question

Thank you for helping with this question.

The in-degree of a node v in a directed graph is the number of edges flowing into v. (a) Give an O(|V| + |E|) algorithm to determine the in-degree of every node v belongs to V in the directed graph (V, E). The algorithm should produce its result in the form of an array in degree, So that on completion, in degree(v) will hold the in-degree of node v. Towards the end of Levitin Section 4.2, a decrease-and-conquer approach to the topological sorting problem is suggested. The idea is to repeatedly remove a source (a node with no incoming edges) and list the order in which such nodes were removed. (b) Give an algorithm for this version of topological sort. Given the input graph (V, E), you can assume that an array indegree has already been initialised correctly, so that for each v belongs to V, indegree (v) is It's in-degree. You can also assume the graph is acyclic (note that we can detect cycles in linear time with, for example, depth-first traversal). Partial marks will be given for a correct algorithm: full marks will be given for an algorithm that rums in time O(|V| + |E|).

Explanation / Answer

a) Here is the algorithm

indegree[v] = indegree of node x (computing by adjacency list)
count = [ v in nodes | indegree[x] = 0 ] //this will stores vertices we visited
result = []
while count != []:
v = count.pop()
result.push(v)
for x in adj(v): //if incoming edges are there
indegree[x]-- //decrementing indegree for adjacent vertices
if indegree[x] = 0: // checking for vertices have no incoming edges
count.push(x)

-------------------------------------------------------------------

b)
so ....topological sort of version of above algorithm....
result = []
visited = {}
dfs(v): //pushing into stack in decreasing order
if v in visited: return
visited.insert(v)
for y in adj(v):
dfs(y)
result.push(v)
for v in V: dfs(v)
reverse(result) //finally reversing to get increasing order

------------------
we are using DFS we are sorting......And it has which has complexity O(|v| + |E|) for the directed graph.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.