ArraList.forEach для Java не работает должным образом в течение цикла

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 может обрабатывать только А и его ребра, как показано ниже ...

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, который останется пустым.

Другими словами, вершина "B", на которую ссылаются из "A", отличается от экземпляра вершины "B", которая находится в * 1020.**

например, что-то вроде этого:

 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));
         }
     });
  }