__Depth First Search Implementation in Graph__

--Graph //This is a class to define the vertex in a graph public class Vertex { char label; boolean visited; public Vertex(char label){ this.label=label; this.visited=false; } package Graph; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; // this class is abstract because we won't allow you make instance of it , it is of no use until not extended abstract public class GraphBase { //declaring instance of vertex Vertex vertex; //declaring an array of vertex to hold all the vertex static Vertex[] vertexlist=new Vertex[10]; //declaring edgelist to hold all edges key is vertex value is neighbouring vertex static HashMap<Character,ArrayList<Character>> edgelist=new HashMap<>(); //count of vertex and edge static int vertexcount=0; int edgecount=0; /* * This function takes a label and insert in the vertex list as well as edge list since it is new vertex it will add * null to its adjoining vertices */ int addVertex(char label) { vertex=new Vertex(label); vertexlist[vertexcount]=vertex; System.out.println(vertexlist[vertexcount].label); edgelist.put(vertex.label, null); vertexcount++; return vertexcount; } /* * in the same edgelist we add the vertices that are now in connection by simply updating value for a key */ int addEdge(char v1,char[] v2) { ArrayList<Character> vertextoadd=new ArrayList<>(); for(int i=0;i<v2.length;i++) { edgecount++; vertextoadd.add(v2[i]); } edgelist.put(v1, vertextoadd); return edgecount; } //A function that returns neighbour vertices for a given vertex ArrayList getNeighbours(char vertex) { return edgelist.get(vertex); } void listOfVertex() { System.out.println("Total Vertex:"+ vertexcount); //This is how we traverse over a hashmap for(Object key:edgelist.keySet()) { System.out.println(key+" " +edgelist.get(key)); } } } package Graph; import java.util.ArrayList; import java.util.Stack; public class GraphSearch extends GraphBase { /*Depth First Search * Basically it works on the concept of stack we take vertex from it serach its neighbour and do the same till no vertex left * *1. Push first element in stack *2. Search for its neigbour and add them in stack and pop the vertex *3. do same for rest of the vertices until there is no vertex left in a stack * */ void searchDFS() { Stack<Character> stack=new Stack<>(); stack.push(vertexlist[0].label); while(!stack.isEmpty()) { System.out.println("traverse"+stack.peek()); ArrayList adjvertex=getNeighbours(stack.peek()); stack.pop(); if(adjvertex!=null) { for(int i=adjvertex.size()-1;i>=0;i--) { stack.push((Character) adjvertex.get(i)); } } } } } package Graph; import java.util.Map.Entry; public class GraphImpl extends GraphBase { public static void main(String[] args) { GraphImpl graph=new GraphImpl(); //Adding vertices graph.addVertex('A'); graph.addVertex('B'); graph.addVertex('C'); graph.addVertex('D'); graph.addVertex('E'); graph.addVertex('F'); graph.addVertex('G'); graph.addVertex('H'); //Adding edges and this is how we initialize inline array graph.addEdge('A', new char[]{'B','C'}); graph.addEdge('B', new char[]{'D','E'}); graph.addEdge('C',new char[]{'F','G'} ); graph.addEdge('D',new char[]{'H'} ); graph.listOfVertex(); GraphSearch search=new GraphSearch(); search.searchDFS(); } }

```
```

```
```

```
```

breadth-first-search-implementation-in-java

## Comments

## Post a Comment