How do you implement public String depthFirstSearch(int startVertex){} and publi

Question

How do you implement public String depthFirstSearch(int startVertex){} and public String breadthFirstSearch(int startVertex){} ?

import java.util.*;
public class MyGraph
{
    private int[][] graph;
    private int numberOfVertices;
  
    /**
     * @param numberOfVertices number of vertices of the graph
     */
    public MyGraph(int numberOfVertices){
        this.numberOfVertices = numberOfVertices;
        graph = new int[numberOfVertices+1][numberOfVertices+1];
    }
  
    /**
     * @param graph The matrix representation on the given graph. Assume column 0 and row 0 are not used
     */
    public MyGraph(int [][] graph){
        this.graph = graph;
        // change any 0 to infinity if the 0 is not on diagonal
        for(int i = 1; i < graph.length; i++){
            for(int j = 1; j < graph.length; j++){
                if(i == j) graph[i][j] = 0;
                else if(i != j && graph[i][j] == 0)
                    graph[i][j] = Integer.MAX_VALUE;
            }
        }
        numberOfVertices = graph.length - 1;
    }
  
    /**
   * BREADTH-FIRST SEARCH
     * return a String that represent the vertices in order if the BFS algorithm is used to traversal the graph
     * starting from the given vertex. If the startVertex not exists, return an error message
     * @param startVertex The vertex where the traversal starts
     * @return A String that describes the vertices visited in order
     */
    public String breadthFirstSearch(int startVertex){
         //NEEDS TO BE IMPLEMENTED
    }
  
    /**
   * DEPTH-FIRST SEARCH
     * return a String that represents the vertices in order if the DFS algorithm is used to traversal the graph
     * starting from the given vertex. If the startVertex not exist, return an error message
     * @param startVertex The vertex where the traversal starts
     * @return An ArrayList of Integer that represents the vertices visited in order
     */
    public String depthFirstSearch(int startVertex){
         //NEEDS TO BE IMPLEMENTED
    }
}

Explanation / Answer

Let me know if you face any issue with the code:



import java.util.*;
/**
*
* @author sambh
*/
public class MyGraph
{
private int[][] graph;
private int numberOfVertices;
  
/**
* @param numberOfVertices number of vertices of the graph
*/
public MyGraph(int numberOfVertices){
this.numberOfVertices = numberOfVertices;
graph = new int[numberOfVertices+1][numberOfVertices+1];
}
  
/**
* @param graph The matrix representation on the given graph. Assume column 0 and row 0 are not used
*/
public MyGraph(int [][] graph){
this.graph = graph;
// change any 0 to infinity if the 0 is not on diagonal
for(int i = 1; i < graph.length; i++){
for(int j = 1; j < graph.length; j++){
if(i == j) graph[i][j] = 0;
else if(i != j && graph[i][j] == 0)
graph[i][j] = Integer.MAX_VALUE;
}
}
numberOfVertices = graph.length - 1;
}
  
/**
* BREADTH-FIRST SEARCH
* return a String that represent the vertices in order if the BFS algorithm is used to traversal the graph
* starting from the given vertex. If the startVertex not exists, return an error message
* @param startVertex The vertex where the traversal starts
* @return A String that describes the vertices visited in order
*/
public String breadthFirstSearch(int startVertex){
if (startVertex < 1 || startVertex > numberOfVertices)
throw new IllegalArgumentException("Invalid vertex");
String result = "";
LinkedList<Integer> visited = new LinkedList<>();
LinkedList<Integer> queue = new LinkedList<>();

int presentVertex = startVertex;
while (visited.size() != numberOfVertices) { //loop while all vertices are not added
result += " " + presentVertex;
visited.add(presentVertex);
for (int i = 0; i < numberOfVertices; i++)
if (graph[presentVertex][i] != Integer.MAX_VALUE && !visited.contains(i) && !queue.contains(i))
queue.add(i);
if (queue.isEmpty())
break;
else
presentVertex = queue.remove(0);
}
return result;
}
  
/**
* DEPTH-FIRST SEARCH
* return a String that represents the vertices in order if the DFS algorithm is used to traversal the graph
* starting from the given vertex. If the startVertex not exist, return an error message
* @param startVertex The vertex where the traversal starts
* @return An LinkedList of Integer that represents the vertices visited in order
*/
public LinkedList<Integer> depthFirstSearch(int startVertex){
if (startVertex < 1 || startVertex > numberOfVertices)
throw new IllegalArgumentException("Invalid vertex");
LinkedList<Integer> visited = new LinkedList<>();
LinkedList<Integer> queue = new LinkedList<>();

int presentVertex = startVertex;
while (visited.size() != numberOfVertices) { //loop while all vertices are not added
queue.add(presentVertex);
boolean flag = false;
for (int i = 0; i < numberOfVertices; i++)   
if (graph[presentVertex][i] != Integer.MAX_VALUE && !visited.contains(i) && !queue.contains(i)) {
queue.add(i);
flag = true;
}
if (!flag)
visited.add(presentVertex);
if (queue.isEmpty())
break;
else
presentVertex = queue.remove(queue.size() - 1); //remove the last elemet
}
return visited;
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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