quiz حل الأسئلة الجامعية manage_search الأرشيف

تم الحل ✓
categoryهندسة الحاسبات schoolبكالوريوس event_available2026-07-14

السؤال

Transcribed Image Text:

Question 2 (4 points) a) Can we run topological sort on graph G in Question 1? Why or why not? b) By removing a minimum number of edges from G, we will be able to run topological sort on the resulting new graph G'. Which edges need be removed? How are these edges classified according to the DFS result in Question 1 (c)? (I.e., tree, back, forward, or cross?) c) Run DFS on G' and record the finishing times of each vertex (same alphabetic assumptions as Question 1). Then show the result of running topological sort on G'. d) Run the STRONGLY-CONNECTED-COMPONENTS procedure (slide #59 in lecture 8) on G. Show the transpose GT, and the resulting forest of strongly connected components. You can use the finishing times computed in Question 1 (c) directly.

check_circle الجواب — حل مفصل خطوة بخطوة

hourglass_top