Please complete the findPathBFS() method. here\'s part 1 of the question: https:

Question

Please complete the findPathBFS() method.

here's part 1 of the question: https://www.chegg.com/homework-help/questions-and-answers/please-complete-completegraph-method-q20794417

here's part 2 of the question: https://www.chegg.com/homework-help/questions-and-answers/please-complete-valence-method-s-part-1-question-https-wwwcheggcom-homework-help-questions-q20794561

here's part 3 of the question: https://www.chegg.com/homework-help/questions-and-answers/please-complete-dfs-method-s-part-1-question-https-wwwcheggcom-homework-help-questions-ans-q20794695

1 import java .ut ArrayList 6 Generic vertex class 7 class Vertex public T data public boolean visited 10e public Vertex data null visited false 130 public Vertex(T data data -data; visited false 16e public string tostring t return data. tos tring 19 Declare any additional vertex attribute you may need 20 22 public class Graph T 23 array of vertices 24 protected ArrayList verts 25 26 20 array representing adjacency matrix of an unweighted graph If adj Mat is true, there is an edge from verte i to j 27 otherwise the element adj Mat l is false. 28 29 protected boolean adj Mat 30 32 public Graph ArrayList tex> verts boolean -mat) check the validity of input parameters 33 int nverts J verts 34 adjacency matrix must be square matrix of NxN 35 if Jmat. ength nverts return 36 for (int i30; i nverts i++) 37 if -mat ength nverts return 38

Explanation / Answer

public ArrayList<Integer> findPathBFS(int start, int end){
      
       for (int i=0;i<numVerts();i++){
           verts.get(i).visited=false;
       }
       Queue<Integer> queue=new LinkedList<Integer>();
      
      
       // INSERT CODE HERE
      
       int n=numVerts();   // total number of vertices
      
       /* declare a parent array to keep track of path */
      
       int [] parent=new int[n];      
      
       /* Initialize parent of all vertices to -1 */
       for (int i=0;i<n;i++){  
           parent[i]=-1;
       }
      
      
       queue.add(start);   /* add start vertex to Q */
       this.verts.get(start).visited=true;   /* make start vertex visited flag true */
      
       while(!queue.isEmpty()){ /* while queue is not empty keep running */
          
           int pop_vertex=queue.remove();   /* remove one vertex */
          
           if(pop_vertex==end){/* if this vertex is end vertex */
              
               break;   /* break the loop */
           }
          
           for(int i=0;i<n;i++){ /* for all vertices */
              
               /* if there exist an edge between vertex i and pop_vertex and
               * its not self edge
               * i is already not in Queue
               */
               if(this.adjMat[pop_vertex][i]==true && i!=pop_vertex && this.verts.get(start).visited==false){
                  
                   parent[i]=pop_vertex;   /* set parent of i to pop_vertex */
                   queue.add(i);           /* add vertex i to queue */
                   this.verts.get(i).visited=true;           /* mark it visited so that its not pushed in Queue again*/
                  
               }
           }
                      
       }
      
       ArrayList<Integer> revPath=new ArrayList<Integer>();
      
       revPath.add(end);
       int pi=parent[end];
       while(pi!=-1){   /* while parent is not -1*/
          
           revPath.add(pi);   /* add parent to the path*/
           pi=parent[pi];   /* get parent of parent */
          
       }
       int pathSize=revPath.size();
      
       if(revPath.get(n-1)!= start){   /* if last vertex in rev path is not start vertex */
      
           return null;
       }
      
       /* reverse the list of path */
       ArrayList<Integer> path=new ArrayList<Integer>();
       for(int i=pathSize-1;i>=0;i--){
          
           path.add(revPath.get(i));
       }
       return path;
   }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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