Thursday, March 17, 2022

BFS implementation in Java

 package javaCodes;


import java.util.Arrays;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;


class bfs_graph

{

void bfs_traversal(int g[][], int source, int total_vertices)

{

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

queue.add(source);

boolean visited[] = new boolean[total_vertices];

Arrays.fill(visited, false);

System.out.print("BFS sequence : ");

while(queue.size() > 0)

{

int top = queue.remove();

if(!visited[top])

{

visited[top] = true;

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

for(int i=0; i<total_vertices; i++)

{

if(g[top][i] == 1 && !visited[i])

{

queue.add(i);

}

}

}

}

}

}


public class BFS {

public static void main(String args[])

{

int total_vertices, edges, left_node, right_node;

Scanner sc = new Scanner(System.in);

System.out.println("Enter total number of vertices and esges : ");

total_vertices = sc.nextInt();

edges = sc.nextInt();

int g[][] = new int[total_vertices+1][total_vertices+1];

System.out.println("Enter values of nodes according to each edge : ");

for(int i=0; i<edges; i++)

{

left_node = sc.nextInt();

right_node = sc.nextInt();

g[left_node][right_node] = 1;

g[right_node][left_node] = 1;

}

int source;

System.out.print("Enter source : ");

source = sc.nextInt();

bfs_graph bfs = new bfs_graph();

bfs.bfs_traversal(g, source, total_vertices+1);

}


}


No comments:

Post a Comment