Graph Representations and Traversals (a) Write pseudo-code for an algorithm that

Question

Graph Representations and Traversals

(a) Write pseudo-code for an algorithm that performs depth first search of a directed graph: G - (V, E) and prints out all of the edges visited. [10 marks] (b) The following questions relate to traversals of directed graphs i. The graph-search algorithms shown in lectures always keep track of visited nodes because failing to to do so can result in non termination. Draw a graph that will lead to non-termination of Depth-First-Search if we fail to keep track of nodes already vis- ited. [3 marks] ii. Under what conditions can the Single-Source-Shortest-Path prob- lem be solved using Breadth-First-Search? [2 marks] (c) When is it advantageous in terms of memory-use to store a graph as an adjacency list rather than an adjacency matrix? Briefly justify your answer. 2 marks]

Explanation / Answer

a) It involves following steps

step-1

we do dfs on a point and store each visited point in a vector like we move 1,2,3,4,5 .

step-2

Now we create edge by taking two adjecent number like 1-2,2-3,3-4,4-5 and print it.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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