Create a class: AdjListGraph.java, and just submit AdjListGraph.java. where Step

Question

Create a class: AdjListGraph.java, and just submit AdjListGraph.java. where Step 1 (1 credit): Please implement a graph by adjacency list. Step 2 (1 credit): Write a method: void dfs(){\TO-DO}; which can traverse a graph by DFS (stack based or recursive) The class adjListGraph.java will be test as public class Test {public static void main (String[] args) {AdjListGraph theGraph = new AdjListGraph (); the Graph.addvertex ('A');//0 (start for dfs) the Graph.addvertex ('B');//1 theGraph. addVertex ('C');//2 the Graphs.addVertex ('D');//3 theGraph.addvertex ('E');//4 the Graph. addvertex ('F');//5 the Graph.addEdge (0, 1);//AB the Graph.addEdge (0, 2)//AC theGraph. addEdge (1, 3);//BD the Graphs.addEdge (2, 4)//CE theGraph.addEdge (2, 3);//CD the Graph. addEdge (0, 3);//AD the Graph.addEdge (3 4);//DE theGraph.addEdge (3, 5)//DE System. out.print ("dfs visits:_____"); theGraph.dfs (); System.out.println();}//end main ()}

Explanation / Answer

Below is the required code with methods .It is tested for the test class data . You can rate the answer if satisified else leave a comment

package Chegg;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class AdjListGraph<V> {
   private Map<V, List<Edge<V>>> adjacencyList; // [vertices] -> [edge]
   private Map<V, VertexInfo<V>> vertexInfo; // [vertex] -> [info]

   public AdjListGraph() {
       this.adjacencyList = new HashMap<V, List<Edge<V>>>();
       this.vertexInfo = new HashMap<V, VertexInfo<V>>();
   }

   // Edge class
   class Edge<V> {
       public V from, to;

       public Edge(V from, V to) {
           if (from == null || to == null) {
               throw new IllegalArgumentException("null");
           }
           this.from = from;
           this.to = to;

       }

       public String toString() {
           return "<" + from + ", " + to + ">";
       }
   }

   // Vertex class
   class VertexInfo<V> {
       /** The vertex itself. */
       public V v;

       public boolean visited;

       /** Constructs information for the given vertex. */
       public VertexInfo(V v) {
           this.v = v;
           this.clear();
       }

       /** Resets the visited field. */
       public void clear() {
           this.visited = false;
       }
   }

   public void addVertex(V v) {
       if (v == null) {
           throw new IllegalArgumentException("null");
       }

       adjacencyList.put(v, new ArrayList<Edge<V>>());
       vertexInfo.put(v, new VertexInfo<V>(v));
   }

   public void addEdge(V from, V to) {
       /*
       * List<Edge<V>> edgeList = adjacencyList.get(from); if (edgeList ==
       * null) { throw new IllegalArgumentException(
       * "source vertex not in graph"); }
       */
       List<Edge<V>> edgeList = new ArrayList<Edge<V>>();
       Edge<V> newEdge = new Edge<V>(from, to);
       edgeList.add(newEdge);
   }

   void DFSUtil(char v, boolean visited[]) {
       // Mark the current node as visited and print it
       int n = assignInt(v);
       visited[n] = true;
       System.out.print(v + " ");

       // Recur for all the vertices adjacent to this vertex
       Iterator i = vertexInfo.keySet().iterator();
       while (i.hasNext()) {
           char v1 = (char) i.next();
           int m = assignInt(v1);
           if (!visited[m])
               DFSUtil(v1, visited);
       }
   }

   private int assignInt(char v) {
       int n;
       if (v == 'A') {
           n = 0;
       } else if (v == 'B') {
           n = 1;
       } else if (v == 'C') {
           n = 2;
       } else if (v == 'D') {
           n = 3;
       } else if (v == 'E') {
           n = 4;
       } else {
           n = 5;
       }
       return n;
   }

   // The function to do DFS traversal. It uses recursive DFSUtil()
   void dfs(char v) {
       // Mark all the vertices as not visited(set as
       // false by default in java)
       boolean visited[] = new boolean[vertexInfo.size()];

       // Call the recursive helper function to print DFS traversal
       DFSUtil(v, visited);
   }

   public String toString() {
       Set<V> keys = adjacencyList.keySet();
       String str = "";

       for (V v : keys) {
           str += v + ": ";

           List<Edge<V>> edgeList = adjacencyList.get(v);

           for (Edge<V> edge : edgeList) {
               str += edge + " ";
           }
           str += " ";
       }
       return str;
   }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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