data structures and algorithms Question 23 of 27 /14 mark A graph is represented
ID: 3742415 • Letter: D
Question
data structures and algorithms
Question 23 of 27 /14 mark A graph is represented in adjacency list shown below. Starting at vertex 2, the sequence of vertices of the araph visited using a depth first-search algo s (blank a) (Hint: a sample representation of a sequence of vertices is (2, 3, 4)) Starting at verfex 3 the sequence of vertices of the grap d using a breadth-first-sear orithm is (blank b), The first row (or the top row) in the jacency matrix of this graph is (hlank c) running time of removing one vertex trom this graph is sample representation of a row in an adjacency matrix is (10101101). The in terms of the performarice of the adjacency list structure. Vertex Adiacent vertces 2, 3, 4 1, 3, 4 1, 2, 4 1, 2, 3 6 6, 7, 8 5, 6, 8 /3.5 marks Answer a.Explanation / Answer
(a) In depth-first search(DFS), the algorithm starts at the root node(any arbitrary node) and keeps on going as far as possible along each branch before backtracking. Here, the root vertex is 2, so we will keep on going along a branch before there are no more vertices to explore or we encounter an already visited vertex.
So, from 2 we go to 1, then we go to 3(as 2 is already visited), then 4, 6, 5, 7, 8. Then vertices start repeating. So, the DFS sequence is (2, 1, 3, 4, 6, 5, 7, 8).
(b) In breadth-first search(BFS), the algorithm starts at the root node(any arbitrary node) and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
So, from 3 we go to 1, 2, 4. As there are no adjacent nodes to 3, we go to 1. As the adjacent nodes of 1 and 2 are already visited, we go to 4. From 4 we go to 6, then to 5, 7 and 8.
So, the BFS sequence becomes (3,1,2,4,6,5,7,8).
(c) As 1 has 2,3 and 4 as its adjacent nodes, so indices 2,3,4 will be 1 and all others 0.
So. top row is (0111000)
(d) The running time for removing a vertex from the adjacency list structure is O(E) as you may have to go to all the edges to remove a vertex from the graph.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.