Hi,
i am implementing DFS and BFS on a graph. i am reading a text file containing data to make graph. i have done with DFS but having a problem in BFS. here is my all the classes:
//graph.text
A B 10
B A 12
B C 3
C B 3
B D 6
D B 7
D A 1
A D 2
D C 4
C D 3
//Main.java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class tester {
public static void main(String[] args) {
try
{
Scanner scan=new Scanner(new File("graph.txt"));
graph obj=new graph();
while(scan.hasNext())
{
String start=scan.next();
String end=scan.next();
int w=scan.nextInt();
obj.add(start,end,w);
}
obj.BFS("A");
}
catch (FileNotFoundException e)
{
e.printStackTrace();
}
}
}
//Node.java
import java.util.ArrayList;
public class Node {
String name;
ArrayList<Edge> edges=new ArrayList<Edge>();
boolean visited;
Node(String pname){
name=pname;
visited=false;
}
void makeedge(Node pend,int w){
Edge temp=new Edge(this,pend,w);
edges.add(temp);
}
}
//Edge.java
public class Edge {
Node start;
Node end;
int w;
boolean visited;
Edge(Node pstart,Node pend,int w){
start = pstart;
end = pend;
this.w = w;
}
}
//graph.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class graph {
ArrayList<String> names=new ArrayList<String>();
ArrayList<Node> nodes=new ArrayList<Node>();
boolean visited = true;
void add(String a,String b,int w)
{
if(!names.contains(a))
{
Node temp=new Node(a);
nodes.add(temp);
names.add(a);
}
if(!names.contains(b))
{
Node temp1=new Node(b);
nodes.add(temp1);
names.add(b);
}
makeEdge(a, b, w);
}
void makeEdge(String a,String b, int w)
{
Node temp1=search(a);
Node temp2=search(b);
temp1.makeedge(temp2, w);
}
Node search(String a)
{
for (Node n : nodes)
{
if(n.name.equals(a))
{
return n;
}
}
return null;
}
void DFS(String a)
{
Node temp=search(a);
if(!temp.visited)
{
rec(temp);
}
}
void rec(Node a){
a.visited=true;
for (Edge e : a.edges)
{
if(!e.end.visited)
{
rec(e.end);
System.out.println(e.start.name+"-->"+e.end.name+" "+e.w);
}
}
}
void BFS(String a)
{
Queue<Node> q = new LinkedList<Node>();
Node temp = search(a);
q.add(temp);
temp.visited = true;
while(!q.isEmpty())
{
Node n = (Node)q.poll();
for(Edge e: n.edges)
{
if(!e.visited)
{
e.visited = true;
e.add(a);
}
}
}
}
}
i am facing problem in BFS function. please help me to correct this according to method how i reading the input. thanks