Created
August 9, 2019 17:36
-
-
Save ajinkyajawale14499/e0b6c1ead56d39c50ff50bbb9bd7ebe0 to your computer and use it in GitHub Desktop.
Depth First Search of a graph
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.LinkedList; | |
| import java.util.Stack; | |
| public class Graph{ | |
| int V; | |
| LinkedList<Integer> List[]; | |
| public Graph(int V){ | |
| this.V=V; | |
| List=new LinkedList[V]; | |
| for(int i=0;i<V;i++){ | |
| List[i]=new LinkedList<Integer>(); | |
| } | |
| } | |
| public void addEdge(int x, int y) | |
| { | |
| List[x].addFirst(y); | |
| } | |
| public void DFS() | |
| { | |
| System.out.print("DFS:"); | |
| boolean[] visited = new boolean[V]; | |
| Stack<Integer> st = new Stack<Integer>(); | |
| for(int i=0;i<V;i++){ | |
| if(visited[i] == false){ | |
| st.push(i); | |
| System.out.println(st); | |
| visited[i] = true; | |
| while(st.isEmpty() == false){ | |
| int out = st.pop(); | |
| System.out.print(out+" "); | |
| LinkedList<Integer> nodelist = List[out]; | |
| for(int ii=0;ii<nodelist.size();ii++) | |
| { | |
| int y = nodelist.get(ii); | |
| if(visited[y] == false){ | |
| st.push(y); | |
| visited[y] = true; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| public void printGraph(){ | |
| for (int i = 0; i <V ; i++) { | |
| LinkedList<Integer> nodeList = List[i]; | |
| if(nodeList.isEmpty()==false) { | |
| System.out.print("source = " + i + " is connected to nodes: "); | |
| for (int j = 0; j < nodeList.size(); j++) { | |
| System.out.print(" " + nodeList.get(j)); | |
| } | |
| } | |
| System.out.println(); | |
| } | |
| } | |
| public static void main(String[] args){ | |
| Graph graph =new Graph(6); | |
| graph.addEdge(0, 1); | |
| graph.addEdge(0, 2); | |
| graph.addEdge(1, 2); | |
| graph.addEdge(1, 3); | |
| graph.addEdge(3, 4); | |
| graph.addEdge(2, 3); | |
| graph.addEdge(4, 0); | |
| graph.addEdge(4, 1); | |
| graph.addEdge(4, 5); | |
| graph.printGraph(); | |
| graph.DFS(); | |
| } | |
| } |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
solution:
Finished in 88 ms
source = 0 is connected to nodes: 2 1
source = 1 is connected to nodes: 3 2
source = 2 is connected to nodes: 3
source = 3 is connected to nodes: 4
source = 4 is connected to nodes: 5 1 0
DFS:[0]
0 1 3 4 5 2