bfs in java code example
Example 1: python breadth first search
def breadthFirstSearch(root):
q = [root]
while q:
current = q.pop(0)
print(current)
if current.left is not None: q.append(current.left)
if current.right is not None: q.append(current.right)
Example 2: breadth first traversal python program
class Graph:
def __init__(self):
self.vertices = {}
def add_vertex(self, key):
"""Add a vertex with the given key to the graph."""
vertex = Vertex(key)
self.vertices[key] = vertex
def get_vertex(self, key):
"""Return vertex object with the corresponding key."""
return self.vertices[key]
def __contains__(self, key):
return key in self.vertices
def add_edge(self, src_key, dest_key, weight=1):
"""Add edge from src_key to dest_key with given weight."""
self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)
def does_edge_exist(self, src_key, dest_key):
"""Return True if there is an edge from src_key to dest_key."""
return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])
def __iter__(self):
return iter(self.vertices.values())
class Vertex:
def __init__(self, key):
self.key = key
self.points_to = {}
def get_key(self):
"""Return key corresponding to this vertex object."""
return self.key
def add_neighbour(self, dest, weight):
"""Make this vertex point to dest with given edge weight."""
self.points_to[dest] = weight
def get_neighbours(self):
"""Return all vertices pointed to by this vertex."""
return self.points_to.keys()
def get_weight(self, dest):
"""Get weight of edge from this vertex to dest."""
return self.points_to[dest]
def does_it_point_to(self, dest):
"""Return True if this vertex points to dest."""
return dest in self.points_to
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, data):
self.items.append(data)
def dequeue(self):
return self.items.pop(0)
def display_bfs(vertex):
"""Display BFS Traversal starting at vertex."""
visited = set()
q = Queue()
q.enqueue(vertex)
visited.add(vertex)
while not q.is_empty():
current = q.dequeue()
print(current.get_key(), end=' ')
for dest in current.get_neighbours():
if dest not in visited:
visited.add(dest)
q.enqueue(dest)
g = Graph()
print('Menu')
print('add vertex <key>')
print('add edge <src> <dest>')
print('bfs <vertex key>')
print('display')
print('quit')
while True:
do = input('What would you like to do? ').split()
operation = do[0]
if operation == 'add':
suboperation = do[1]
if suboperation == 'vertex':
key = int(do[2])
if key not in g:
g.add_vertex(key)
else:
print('Vertex already exists.')
elif suboperation == 'edge':
src = int(do[2])
dest = int(do[3])
if src not in g:
print('Vertex {} does not exist.'.format(src))
elif dest not in g:
print('Vertex {} does not exist.'.format(dest))
else:
if not g.does_edge_exist(src, dest):
g.add_edge(src, dest)
else:
print('Edge already exists.')
elif operation == 'bfs':
key = int(do[1])
print('Breadth-first Traversal: ', end='')
vertex = g.get_vertex(key)
display_bfs(vertex)
print()
elif operation == 'display':
print('Vertices: ', end='')
for v in g:
print(v.get_key(), end=' ')
print()
print('Edges: ')
for v in g:
for dest in v.get_neighbours():
w = v.get_weight(dest)
print('(src={}, dest={}, weight={}) '.format(v.get_key(),
dest.get_key(), w))
print()
elif operation == 'quit':
break
Example 3: bfs solutions java
package com.javaaid.hackerrank.solutions.tutorials.ctci;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
class Graph {
private final int V;
private int E;
private ArrayList<Integer>[] adj;
Graph(int V) {
adj = (ArrayList<Integer>[]) new ArrayList[V + 1];
this.V = V;
this.E = 0;
for (int v = 1; v <= V; v++) adj[v] = new ArrayList<Integer>(V);
}
Graph(Scanner in) {
this(in.nextInt());
int E = in.nextInt();
for (int i = 0; i < E; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}
public int V() {
return V;
}
public int E() {
return E;
}
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
class BreadthFirstPaths {
private int s;
private boolean marked[];
private int edgeTo[];
BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V() + 1];
this.s = s;
edgeTo = new int[G.V() + 1];
bfs(G, s);
}
private void bfs(Graph G, int s) {
Queue<Integer> q = (Queue<Integer>) new LinkedList<Integer>();
q.add(s);
while (!q.isEmpty()) {
int v = q.poll();
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
marked[w] = true;
edgeTo[w] = v;
q.add(w);
}
}
}
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) path.push(x);
path.push(s);
return path;
}
public boolean hasPathTo(int v) {
return marked[v];
}
}
public class BFSShortestReachInAGraph {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int q = sc.nextInt();
for (int i = 0; i < q; i++) {
Graph G = new Graph(sc);
int s = sc.nextInt();
BreadthFirstPaths bfp = new BreadthFirstPaths(G, s);
for (int v = 1; v <= G.V(); v++) {
if (s != v) {
if (bfp.hasPathTo(v)) {
Stack<Integer> st = (Stack<Integer>) bfp.pathTo(v);
int sum = 0;
for (int x = 1; x < st.size(); x++) {
sum += 6;
}
System.out.print(sum + " ");
} else {
System.out.print(-1 + " ");
}
}
}
System.out.println();
sc.close();
}
}
}