Scribd
Upload
3 views6 pages

Basic Graph

The document contains Java implementations of graph traversal algorithms: Depth-First Search (DFS) without a stack, DFS with a stack, and Breadth-First Search (BFS) with a queue. Each algorithm uses an adjacency list representation of the graph and marks nodes as seen to avoid revisiting them. The main method demonstrates the construction of a sample graph and calls the respective traversal methods starting from node 0.

Uploaded by

srinithijasivakumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views6 pages

Basic Graph

The document contains Java implementations of graph traversal algorithms: Depth-First Search (DFS) without a stack, DFS with a stack, and Breadth-First Search (BFS) with a queue. Each algorithm uses an adjacency list representation of the graph and marks nodes as seen to avoid revisiting them. The main method demonstrates the construction of a sample graph and calls the respective traversal methods starting from node 0.

Uploaded by

srinithijasivakumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DFS WITHOUT STACK:

import [Link].*;

import [Link].*;

public class adjacencylist {

static void dfs(ArrayList<ArrayList<Integer>> a ,int s, boolean seen[]){

seen[s]=true;

[Link](s);

for(int n: [Link](s)){

if(!seen[n]){

dfs(a,n,seen);

public static void main(String [] args){

ArrayList<ArrayList<Integer>> a = new ArrayList<>();

for(int i=0;i<5;i++){

[Link](new ArrayList<>());

[Link](0).add(1);

[Link](0).add(2);

[Link](1).add(3);

[Link](2).add(4);

for(int i=0;i<5;i++){

[Link](i+"->"+[Link](i));

}
boolean seen[]=new boolean[5];

int s=0;

[Link]("DFS with no stack");

dfs(a,s,seen);

DFS WITH STACK:

import [Link].*;

import [Link].*;

public class adjacencylist {

static void dfs(ArrayList<ArrayList<Integer>> a ,int s, boolean seen[]){

seen[s]=true;

Stack <Integer> st= new Stack<>();

[Link](s);

while(![Link]()){

int n=[Link]();

[Link](n);

for(int ne:[Link](n)){
if(!seen[ne]){

[Link](ne);

seen[ne]=true;

public static void main(String [] args){

ArrayList<ArrayList<Integer>> a = new ArrayList<>();

for(int i=0;i<5;i++){

[Link](new ArrayList<>());

[Link](0).add(1);

[Link](0).add(2);

[Link](1).add(3);

[Link](2).add(4);

for(int i=0;i<5;i++){

[Link](i+"->"+[Link](i));

boolean seen[]=new boolean[5];

int s=0;

[Link]("DFS with stack");

dfs(a,s,seen);

}
BFS WITH QUEUE

import [Link].*;

import [Link].*;

public class adjacencylist {

static void bfs(ArrayList<ArrayList<Integer>> a ,int s, boolean seen[]){

seen[s]=true;

Queue <Integer> q= new LinkedList<>();

[Link](s);

while(![Link]()){

int n=[Link]();

[Link](n);

for(int ne:[Link](n)){

if(!seen[ne]){

[Link](ne);

seen[ne]=true;

}
public static void main(String [] args){

ArrayList<ArrayList<Integer>> a = new ArrayList<>();

for(int i=0;i<5;i++){

[Link](new ArrayList<>());

[Link](0).add(1);

[Link](0).add(2);

[Link](1).add(3);

[Link](2).add(4);

for(int i=0;i<5;i++){

[Link](i+"->"+[Link](i));

boolean seen[]=new boolean[5];

int s=0;

[Link]("BFS with Queue");

bfs(a,s,seen);

You might also like