广度优先使用队列在图中搜索

Question

我认为我的代码有错误，我不知道原因。

图表为：这是图

输出为：

BFS 的输出

输出为：1->2->4->5

但这是不正确的，因为正确的答案是：

1->2->4->5->3

我的代码是用Java编写的，我有类NodoG(表示图的节点(、Grafo(表示图(和Principal(我在其中进行操作(。

此外，我不考虑边的权重，我只考虑在相应节点中引入相邻边的顺序。

例如：

• 1->2重3：我先写
• 1->4重10：我把它放在第二位
• 1->5重12：我把它放在第三位

我处理每个节点。但是，如果一个节点没有邻居，我就不会把它写成数据。

public class NodoG {
private int dato;
boolean visitado;
List<NodoG> adyacentes;
public NodoG(int dato){
this.dato = dato;
this.visitado = false;
this.adyacentes = new ArrayList<>();
}
public int getDato() {
return dato;
}
public void setDato(int dato) {
this.dato = dato;
}
public boolean isVisitado() {
return visitado;
}
public void setVisitado(boolean visitado) {
this.visitado = visitado;
}
public List<NodoG> getAdyacentes() {
return adyacentes;
}
public void setAdyacentes(ArrayList<NodoG> adyacentes) {
this.adyacentes = adyacentes;
}

@Override
public String toString(){
return (dato + "->");
} 
}

我的另一个班：Grafo

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Grafo {
private List<NodoG> nodoGrafo;

public Grafo(){
nodoGrafo = new ArrayList<NodoG>();
}

public List<NodoG> getNodoGrafo() {
return nodoGrafo;
}

public void setNodoGrafo(ArrayList<NodoG> nodoGrafo) {
this.nodoGrafo = nodoGrafo;
}

public void insertarNodoG(){
System.out.println("Write data: ");
Scanner entrada = new Scanner(System.in);
System.out.print("->");
int valor = entrada.nextInt();
NodoG nodo = new NodoG(valor);
nodoGrafo.add(nodo);       
}

public NodoG buscarNodoGrafo(int n1){
NodoG nodo = null;
for (NodoG nodoGrafo1 : nodoGrafo) {
if(nodoGrafo1.getDato() == n1){
nodo = nodoGrafo1;
}
}
return nodo;
}

public void insertarAdyacente(){
System.out.println("Write the data of the graph's node: ");
Scanner entrada = new Scanner(System.in);
System.out.print("->");
int valor = entrada.nextInt();
NodoG nodo = buscarNodoGrafo(valor);
if(nodo!=null){
System.out.println("Write the data of the adjacent: ");
System.out.print("->");
int dato = entrada.nextInt();
NodoG nuevo = new NodoG(dato);
nodo.getAdyacentes().add(nuevo);
}
else{
System.out.println("->This node doesn't exist.");
}
}

public void busquedaAmplitud(){
System.out.println("Write the initial node: ");
Scanner entrada = new Scanner(System.in);
int dato = entrada.nextInt();
System.out.println("-----------------------");
NodoG inicio = buscarNodoGrafo(dato);
if(inicio!=null){
Queue<NodoG> cola = new LinkedList<NodoG>();

cola.add(inicio);
inicio.setVisitado(true);
while(!cola.isEmpty()){
//  System.out.println("size: "+cola.size());
NodoG elem = cola.poll();
//System.out.println("--------------");
System.out.print("->" + elem.getDato());
//System.out.println("--------------");
List<NodoG> ady = elem.getAdyacentes();
for (int i = 0;i<ady.size();i++) {
NodoG ady1 = ady.get(i);
if(ady1!= null && !ady1.isVisitado()){
cola.add(ady1);
ady1.setVisitado(true);
}
}
}
}
else{
System.out.println("This node doesn't exist.");
}
}

}

我的最后一堂课：校长

import java.util.Scanner;
public class Principal {
public static void main(String[] args) {
Grafo G = new Grafo();
int opc;
System.out.println("=========================");
System.out.println("BFS");
System.out.println("=========================");
System.out.println("¿How many nodes does the graph have?: ");
Scanner entrada = new Scanner(System.in);
int cant = entrada.nextInt();
System.out.println("---------------------------------");
System.out.println("Write the data of the nodes: ");
for(int i=0;i<cant;i++){
G.insertarNodoG();
}
System.out.println("==================================");
System.out.println("Adjacent of the node");
System.out.println("===================================");
do{
System.out.println("Enter the node you want to write an adjacent:");
G.insertarAdyacente();
System.out.println("-----------------------------------------");
System.out.print("¿Do you want to write another adjacent?: (Yes: 1) (No: Any number) -> ");
opc = entrada.nextInt();
System.out.println("-----------------------------------");
}while(opc == 1);
do{
System.out.println("==========================");
System.out.println("BFS: ");
System.out.println("---------------------------");
G.busquedaAmplitud();
System.out.println("n---------------------------");
//restartnodes() //To restar the boolean values of the nodes
System.out.println("¿Do you want to use another node? (Yes: 1) (No: Any number)->");
opc = entrada.nextInt();
}while(opc==1);
}
}

拜托，有人能帮我吗？此外，我需要知道如何重新启动节点的布尔值。

Answer 1

对代码进行了两次修复。首先，您的insertarAdyacente()函数工作不正常。因为您创建了一个新节点，而不是找到具有给定数据的已创建节点。您可以在下面找到正确的版本

public void insertarAdyacente(){
System.out.println("Write the data of the graph's node: ");
Scanner entrada = new Scanner(System.in);
System.out.print("->");
int valor = entrada.nextInt();
NodoG nodo = buscarNodoGrafo(valor);
if(nodo!=null){
System.out.println("Write the data of the adjacent: ");
System.out.print("->");
int dato = entrada.nextInt();
NodoG nuevo = buscarNodoGrafo(dato);  // fixed here.
nodo.getAdyacentes().add(nuevo);
}
else{
System.out.println("->This node doesn't exist.");
}
}

其次，我认为给所有节点一个isVisited字段，而不是简单地在BFS函数中创建一个布尔数组，这似乎是一种糟糕的做法。但我不想更改您正在应用的逻辑，而是在Grafo中创建了一个新函数，这样每当我们想调用busquedaAmplitud()时，它都会将所有可见项设置为False

public void setVisitadoFalse() {
for(NodoG node: this.getNodoGrafo()) {
node.setVisitado(false);
}
}
public void busquedaAmplitud(){
this.setVisitadoFalse();   // No one is visited at the beginning.
System.out.println("Write the initial node: ");
Scanner entrada = new Scanner(System.in);
int dato = entrada.nextInt();
System.out.println("-----------------------");
NodoG inicio = buscarNodoGrafo(dato);
if(inicio!=null){
Queue<NodoG> cola = new LinkedList<NodoG>();

cola.add(inicio);
inicio.setVisitado(true);
while(!cola.isEmpty()){
NodoG elem = cola.poll();
//System.out.println("--------------");
System.out.print("->" + elem.getDato());
//System.out.println("--------------");
List<NodoG> ady = elem.getAdyacentes();

for (int i = 0;i<ady.size();i++) {
NodoG ady1 = ady.get(i);
if(ady1!= null && !ady1.isVisitado()){
cola.add(ady1);
ady1.setVisitado(true);
}
}
}
}
else{
System.out.println("This node doesn't exist.");
}
}