Java program to print bfs traversal from a given source vertex



Download 25.5 Kb.
Sana07.06.2021
Hajmi25.5 Kb.

// Java program to print BFS traversal from a given source vertex.

// BFS(int s) traverses vertices reachable from s.

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency list

// representation

class Graph

{

private int V; // No. of vertices



private LinkedList adj[]; //Adjacency Lists

// Constructor

Graph(int v)

{

V = v;



adj = new LinkedList[v];

for (int i=0; i

adj[i] = new LinkedList();

}

// Function to add an edge into the graph



void addEdge(int v,int w)

{

adj[v].add(w);



}

// prints BFS traversal from a given source s

void BFS(int s)

{

// Mark all the vertices as not visited(By default



// set as false)

boolean visited[] = new boolean[V];

// Create a queue for BFS

LinkedList queue = new LinkedList();

// Mark the current node as visited and enqueue it

visited[s]=true;

queue.add(s);

while (queue.size() != 0)

{

// Dequeue a vertex from queue and print it



s = queue.poll();

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

// Get all adjacent vertices of the dequeued vertex s

// If a adjacent has not been visited, then mark it

// visited and enqueue it

Iterator i = adj[s].listIterator();

while (i.hasNext())

{

int n = i.next();



if (!visited[n])

{

visited[n] = true;



queue.add(n);

}

}



}

}

// Driver method to



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);

System.out.println("Following is Breadth First Traversal "+

"(starting from vertex 2)");

g.BFS(2);

}

}



// BFS algorithm in Java

import java.util.*;

public class Graph {

private int V;

private LinkedList adj[];

// Create a graph

Graph(int v) {

V = v;


adj = new LinkedList[v];

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

adj[i] = new LinkedList();

}

// Add edges to the graph



void addEdge(int v, int w) {

adj[v].add(w);

}

// BFS algorithm



void BFS(int s) {

boolean visited[] = new boolean[V];

LinkedList queue = new LinkedList();

visited[s] = true;

queue.add(s);

while (queue.size() != 0) {

s = queue.poll();

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

Iterator i = adj[s].listIterator();

while (i.hasNext()) {

int n = i.next();

if (!visited[n]) {

visited[n] = true;

queue.add(n);

}

}

}



}

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);

System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");



g.BFS(2);

}

}

Download 25.5 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2020
ma'muriyatiga murojaat qiling

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
O’zbekiston respublikasi
maxsus ta’lim
zbekiston respublikasi
axborot texnologiyalari
o’rta maxsus
davlat pedagogika
nomidagi toshkent
guruh talabasi
pedagogika instituti
texnologiyalari universiteti
toshkent axborot
xorazmiy nomidagi
rivojlantirish vazirligi
samarqand davlat
haqida tushuncha
navoiy nomidagi
toshkent davlat
nomidagi samarqand
ta’limi vazirligi
Darsning maqsadi
vazirligi toshkent
Toshkent davlat
tashkil etish
kommunikatsiyalarini rivojlantirish
Ўзбекистон республикаси
Alisher navoiy
matematika fakulteti
bilan ishlash
Nizomiy nomidagi
vazirligi muhammad
pedagogika universiteti
fanining predmeti
таълим вазирлиги
sinflar uchun
o’rta ta’lim
maxsus ta'lim
fanlar fakulteti
ta'lim vazirligi
Toshkent axborot
махсус таълим
tibbiyot akademiyasi
umumiy o’rta
pedagogika fakulteti
haqida umumiy
Referat mavzu
fizika matematika
universiteti fizika
ishlab chiqarish
Navoiy davlat