如何使用Queue实现BFS？

编程入门行业动态更新时间:2024-10-10 19:27:13

本文介绍了如何使用Queue实现BFS？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

我正在图表上实现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

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

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