The post shows you Graph Depth First Search in Java. Depth First Search or Depth First Traversal is a recursive algorithm for visiting all the vertices of a graph or tree data structure. Here, there is different a bit between the implementation of Depth First Search and Breadth First Search algorithm. Let’s dive into it.
Graph Depth First Search in Java
Depth First Search (DFS) Algorithm
When visiting a graph from a vertex to another vertex, you maybe get loops so a vertex might be visited again. Here, we can fix it by using a flag of boolean type to mark a visited vertex. It’s not same as Breadth First Search, we use a stack to store vertices that need to visited here.
The Depth First Search Algorithm works as follows:
- Push a vertex of the graph on top of a stack.
- Pop the top item of the stack and mark it as visited.
- Create a list of that vertex’s adjacent nodes. Then just add the ones which aren’t visited on the top of the stack.
- Keep repeating steps 2 and 3 until the stack is empty.
Depth First Search Algorithm pseudocode
|
1 2 3 4 5 |
create a stack STACK mark v as visited and push v into STACK while STACK is non-empty pop the top uv of STACK mark and push all (unvisited) adjacencies of uv into STACK |
Time and space complexity
The time complexity can be expressed as O(V + E), V is the number of vertices and E is the number of edges in the graph since every vertex and every edge will be explored in the worst case.
The space complexity can be expressed as O(V).
Implement of DFS
Now, you can implement a Graph Depth First Search in Java looks like this program
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
// Simple program implements a Graph in adjacency list import java.util.*; class Graph { // We use Hashmap to store the edges in the graph // Hashmap keys are the vertices and values are the edges private Map<Node, List<Node>> map; // Store vertices that need to visit private Stack<Node> stack; static class Node{ int data; boolean visited; Node(int data){ this.data=data; } public int getData(){ return data; } } Graph(){ this.map = new HashMap<>(); this.stack = new Stack<Node>(); } // adds a new vertex to the graph public void addVertex(Node vertex) { map.put(vertex, new LinkedList<Node>()); } // adds the edge of source and destination vertexs public void addEdge(Node sVertex, Node dVertex) { if (!map.containsKey(sVertex)) addVertex(sVertex); if (!map.containsKey(dVertex)) addVertex(dVertex); map.get(sVertex).add(dVertex); } // get graph size public Integer size() { return map.keySet().size(); } // return the count of edges public Integer getEdgesCount() { int count = 0; for (Object v : map.keySet()) { count += map.get(v).size(); } return count; } // graph contains a vertex or not. public boolean containsVertex(Node vertex) { return map.containsKey(vertex)?true:false; } // an edge of two vertices is present or not. public boolean existEdge(Node sVertex, Node dVertex) { return map.get(sVertex).contains(dVertex)?true:false; } // Displays the adjancency list of each vertex. @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Node vertex : map.keySet()) { builder.append(vertex.getData() + ": "); for (Node dVertex : map.get(vertex)) { builder.append(dVertex.getData()+ " "); } builder.append("\n"); } return (builder.toString()); } // Depth First Search method public void dFS(Node node){ stack.push(node); node.visited=true; while (!stack.isEmpty()){ Node adjacencyNode =stack.pop(); System.out.print(adjacencyNode.getData() + "\t"); List<Node> adjacencies = map.get(adjacencyNode); for (int i = 0; i < adjacencies.size(); i++) { Node n=adjacencies.get(i); if(n!=null && !n.visited) { stack.push(n); n.visited=true; } } } } public static void main(String args[]) { // create new graph instance Graph g = new Graph(); Node n10 = new Node(10); Node n20 = new Node(20); Node n30 = new Node(30); Node n40 = new Node(40); // edges are added. g.addEdge(n10, n20); g.addEdge(n10, n40); g.addEdge(n20, n10); g.addEdge(n20, n30); g.addEdge(n20, n40); g.addEdge(n30, n20); g.addEdge(n30, n40); g.addEdge(n40, n10); g.addEdge(n40, n20); g.addEdge(n40, n30); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); // Depth First Search System.out.println("Depth First Search for Graph:"); g.dFS(n10); } } |
Here is output
That’s all about Graph Depth First Search in Java.
References
Graph documentation
