The following graph will be used throughout this question. a. (Given the graph c
ID: 3850607 • Letter: T
Question
The following graph will be used throughout this question. a. (Given the graph classes Vertex, java and Graph.java in the Appendix, lava code for a depth-first traversal on a connected component of a graph is as follows: public void depthFirstTraversalRec1(Integer v) {//PRE: v is the id of a vertex in the graph//POST: Prints out a depth-first traversal of a graph//starting from v System. out. print(" " + v): getVertex(v). setMarked(): //get vertex object with id v, //indicate visited by setting marked VertexIDList adjList = getVertex(v). getAdjs();//get adjacency list representing neighbours Iterator vIt = adjList. Iterator(): while (vIt hasNext()) {//iterate over neighbours Integer nextVertex = vIt. next(): if (!getVertex(nextVertex).isMarked())//if neighbour hasn't been visited depthFirstTraversalRec1(nextVertex);//visit it } } Give the depth-first traversal of the graph above, starting from vertex 1. b. Using the code in a. as a starting point, give a Java function that will detect whether there is a cycle in a graph:Explanation / Answer
a) Depth first traversal = 1 2 5 8 4 3 9 6 7
by following the algorithm the idea is to go till the depth of neighbours of a node. so here I assume that neighbour ordering is in sorted order. so I start from 1 and next neighbour for "1" is "2"' in sorted order. now I should do DFS starting from "2" -> so next neighbour of "2" is 5 like wise you visit till u visit all the neighbours or you found marked vertice. so here I found from "3" , We found that vertice "1" is already visited so we backtrack and visit the other neighbour vertices of " 5".
b)
the idea to find if there is cycle in connected component of a graph is that you analyse that is there any vertice that is visited twice ? If any vertice is visited twice then it means that CYCLE is found.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.