This is an algorithm question, please help with a clear steps answer. thank you.

Question

This is an algorithm question, please help with a clear steps answer. thank you.

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 in V in the directed graph (V, E). The algorithm should produce its result in the form of an array indegree, so that on completion, indegree [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 in V, indegree [v] is v'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 runs in time O(|V| + |E|).

Explanation / Answer

a)

to find the indegree you can use the below algorithm:

indegree[x] = indegreeree of node x (compute this by going through the adjacency lists)
zero = [ x in nodes | indegree[x] = 0 ]
result = []
while zero != []:
    x = zero.pop()
    result.push(x)
    for y in adj(x):
        indegree[y]--
        if indegree[y] = 0:
            zero.push(y)

b)

for topological sort you can use the dfs

result = []
visited = {}
dfs(x):
    if x in visited: return
    visited.insert(x)
    for y in adj(x):
        dfs(y)
    result.push(x)
for x in V: dfs(x)
reverse(result)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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