如何使用Queue实现BFS？ [英] how to implement BFS using Queue?

问题描述

我正在图表上实现DFS和BFS。我正在阅读包含数据的文本文件来制作图表。我已经完成了DFS但在BFS中遇到了问题。这是我所有的课程：



//graph.text

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

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

//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

//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

//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)
		{
			//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面临BFS功能问题。请帮我根据方法读取输入来纠正这个问题。谢谢

i am facing problem in BFS function. please help me to correct this according to method how i reading the input. thanks

推荐答案

参考：使用广度优先搜索（BFS）和深度优先搜索（DFS）遍历在JAVA中实施的图表简介 [ ^ ]

这篇关于如何使用Queue实现BFS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！