ArraList.forEach for Java 在 while 循环中无法正常工作

Question

我正在使用Java实现无向图的广度优先搜索。但是，只处理一个顶点。其他顶点的相邻节点将返回为 0，即使它们已正确添加也是如此。

public class Graph {
   class Vertex {
        String label;
        ArrayList<Vertex> adjNodeList;
        boolean isVisited;
        public Vertex(String label) {
            this.label = label;
            this.adjNodeList = new ArrayList<>();
            this.isVisited = false;
        }
   }
   ArrayList<Vertex> vertices;
   public Graph() {
        this.vertices = new ArrayList<>();    
   }
   public void addNode(String label) {
       this.vertices.add(new Vertex(label));
   }
   public void addEdge(String start, String end) {
       this.vertices.forEach((e) -> {
           if(e.label.equalsIgnoreCase(start)) {
               e.adjNodeList.add(new Vertex(end));
           }
       });
   }
   public void printGraph() {
      this.vertices.forEach((e -> {
          System.out.print("Vertex - " + e.label + " -> ");
          e.adjNodeList.forEach((v -> {
              System.out.print(v.label);
          }));
          System.out.println();
      }));
   }
   public void breadthFirstSearch() {
        Queue<Vertex> theQueue = new LinkedList<>();
        Vertex rv = this.vertices.get(0);
        rv.isVisited = true;
        theQueue.add(rv);
        while(!theQueue.isEmpty()) {
            Vertex vertex = theQueue.remove();
            System.out.println("Processing - " + vertex.label);
            System.out.println("List size - " + vertex.adjNodeList.size());
            vertex.adjNodeList.forEach((e) -> {
                if(!e.isVisited) {
                    e.isVisited = true;
                    theQueue.add(e);
                    System.out.println("Enqueued - " + e.label);
                }
            });
        }
   }

打印图形时，它会正确显示所有边缘，但 BFS 方法只能处理 A 及其边缘，如下所示...

Vertex - A -> BC
Vertex - B -> G
Vertex - C -> D
Vertex - D -> E
Vertex - E -> 
Vertex - G -> 
Processing - A
List size - 2
Enqueued - B
Enqueued - C
Processing - B
List size - 0
Processing - C
List size - 0

Answer 1

即使它们已正确添加。

我假设当您调用addEdge时 - 例如，通过addEdge("A", "B"); - 我们可以假设您已经调用了addNode("A")和addNode("B")。

如果是这样，则问题出在您的addEdge方法中：

public void addEdge(String start, String end) {
   this.vertices.forEach((e) -> {
       if(e.label.equalsIgnoreCase(start)) {
           e.adjNodeList.add(new Vertex(end));
       }
   });

}

所以给定addEdge("A", "B");，这段代码找到你已经添加的起始顶点"A" - 但随后创建一个new Vertex"B"，而不寻找任何可能已经添加的顶点。 该新顶点有一个空的adjNodeList，它将保持为空。

换句话说，从"A"引用的顶点"B"与this.vertices中的顶点"B"是不同的实例。

因此，您应该更改addEdge(并且，为了确定工作，addNode(首先在this.vertices中查找现有顶点。

例如像这样：

 public Vertex fetchNode(String label) {
   return this.vertices.stream()
              .filter(v -> v.getLabel().equals(label))
              .findAny()
              .orElseGet( () -> {
                  Vertex newVertex = new Vertex(label));
                  this.vertices.add(newVertex);
                  return newVertex;
               });
  }
  public void addEdge(String start, String end) {
     this.vertices.forEach((e) -> {
         if(e.label.equalsIgnoreCase(start)) {
             e.adjNodeList.add(fetchNode(end));
         }
     });
  }