我正在使用 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
即使它们被正确添加。
我假设当你调用 addEdge - 例如， by addEdge("A", "B");- 我们可以假设你已经调用了addNode("A")and 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.
所以你应该改变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));
}
});
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句