apply the topological sort algorithm to this example Topological Sort Algorithm

Question

apply the topological sort algorithm to this example

Topological Sort Algorithm Computing in-degrees: 1. Initialize each node's in 1. Compute the in-degree of all vertices degree to 0 2. Go over all edges, add 1 2. Color all vertices white to each ending vertex. 3. For each y, if in-degree (v)J0, insert v into Q; 4. While Q is not empty: 1) Pop v from Q; 2) For all out-going edges (y, u) do a) n-degree (u) b) If in-degree (u) 0, insert u into Q; 3) Color v black 5. If all vertices are black, list them in the order they are popped from Q; otherwise, the graph is not acyclic.

Explanation / Answer

IN degrees

A = 0

B = 2

C = 2

D = 2

E = 1

F = 1

2 nd step colored all white

3. Add A into Q

While Q is not empty

So topological sort is A, F, B, C, E, D

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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