Skip to content

Instantly share code, notes, and snippets.

@ajinkyajawale14499
Created August 9, 2019 17:36
Show Gist options
  • Select an option

  • Save ajinkyajawale14499/e0b6c1ead56d39c50ff50bbb9bd7ebe0 to your computer and use it in GitHub Desktop.

Select an option

Save ajinkyajawale14499/e0b6c1ead56d39c50ff50bbb9bd7ebe0 to your computer and use it in GitHub Desktop.
Depth First Search of a graph
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();
}
}
@ajinkyajawale14499
Copy link
Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment