Skip to content

Instantly share code, notes, and snippets.

@yssharma
Created October 31, 2012 10:43
Show Gist options
  • Save yssharma/3986375 to your computer and use it in GitHub Desktop.
Save yssharma/3986375 to your computer and use it in GitHub Desktop.
BFS - Breadth First Java (Confused Coders)
// Came across this cool code with neat code style for BFS
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Node {
String data;
boolean visited;
List<Node> neighbours = new ArrayList<Node>();
public Node(String data) {
this.data = data;
}
public void addNeighBour(Node node) {
neighbours.add(node);
node.neighbours.add(this);
}
}
class Graph {
List nodes = new ArrayList();
public void breadthFirstTraversal(Node rootNode) {
LinkedList q = new LinkedList();
q.add(rootNode);
rootNode.visited = true;
while (!q.isEmpty()) {
Node n = (Node) q.poll();
System.out.print(n.data + " ");
for (Node adj : n.neighbours) {
if (!adj.visited) {
adj.visited = true;
q.add(adj);
}
}
}
}
}
class Bfs{
public static void main(String[] args) {
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
Node G = new Node("G");
Node H = new Node("H");
Node I = new Node("I");
Node J = new Node("J");
Graph g = new Graph();
g.nodes.add(A);
g.nodes.add(B);
g.nodes.add(C);
g.nodes.add(D);
g.nodes.add(E);
g.nodes.add(F);
g.nodes.add(G);
g.nodes.add(H);
g.nodes.add(I);
g.nodes.add(J);
A.addNeighBour(C);
A.addNeighBour(B);
A.addNeighBour(E);
B.addNeighBour(F);
F.addNeighBour(I);
I.addNeighBour(J);
J.addNeighBour(E);
J.addNeighBour(H);
C.addNeighBour(G);
C.addNeighBour(H);
H.addNeighBour(D);
g.breadthFirstTraversal(A);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment