GeezerVison is showing github.com — Java/Programs/DFS.java at main · rochards/Java

Expand file tree

DFS.java

Copy path

More file actions

Latest commit

History

67 lines (48 loc) · 1.31 KB

DFS.java

Copy path

File metadata and controls

67 lines (48 loc) · 1.31 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

//Note - for disconnected graph use the approach for checking connected components.

package project0;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

class Graph{

private int v ; //total number of vertices

private LinkedList<Integer> adj[]; //adjacency list

private boolean visited[]; //to keep track of the node which are visited.

Graph(int v){

this.v = v;

this.adj = new LinkedList[v];

this.visited = new boolean[v];

for(int i=0;i<this.v;i++) {

adj[i] = new LinkedList<Integer>();

this.visited[i] = false;

}

public void addEdge(int u,int v) { // edge from u -> v

this.adj[u].add(v);

}

public void DFS(int source) {

//if the node is already visited, then backtrack.

if(this.visited[source] == true) {

return;

}

//mark the source vertex as visited

System.out.print(source+" ");

this.visited[source] = true;

//traverse through all the neighbours and backtrack if already visited.

LinkedList<Integer> neighbours = this.adj[source];

for(int next : neighbours) {

DFS(next);

}

public class Main {

public static void main(String args[]){

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

g.DFS(2);

}