Click here to Skip to main content
15,561,246 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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
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();
			//DFS dfs = new DFS();
			
			while(scan.hasNext())
			{
				String start=scan.next();
				String end=scan.next();
				int w=scan.nextInt();
				obj.add(start,end,w);
			}
			
			//obj.DFS("A");
			obj.BFS("A");
		} 
		catch (FileNotFoundException e) 
		{
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

}

//Node.java
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
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
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)
		{
			//temp.visited=true;
			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
Posted
Updated 29-Nov-14 4:34am
v2
Comments
Richard MacCutchan 29-Nov-14 13:46pm    
What problem? Please explain clearly what results you expect, what results you see, and exactly where in the code the problem occurs.
Hamza Javed 30-Nov-14 2:12am    
actually i am reading all the nodes(A, B, C.........) from text file as string and edges between them as integer. In BFS function,at the end, i am doing "e.add(a)" which is giving me error that change the type of "a" as node and when i do it it creates error in my add() function because it takes string. i dont now what to do it :(
Richard MacCutchan 30-Nov-14 5:19am    
I don't see an add method defined anywhere for the Edge class. However, if the parameters are incorrect you just need to check the definition and use the correct types.

1 solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900