您尚未实现BFS搜索,因为您不会在到达顶点时迭代地将其添加到队列中——您只会在每次外循环时添加顶点及其紧邻的邻居,这不是BFS。
在Java中:
-
HashMap.foreach
时间复杂度为
O(buckets + n)
-对于固定数量的哈希桶,这是有效的
O(n)
.
-
Collection.add
时间复杂度为
O(1)
.
-
Collection.addAll
时间复杂度为
O(n)
.
-
LinkedList.poll
时间复杂度为
O(1)
.
-
Collection.isEmpty
时间复杂度为
O(1)
.
-
HashSet.contains
最坏情况下的时间复杂度为
O(log(n))
(或
O(n)
如果您使用的是Java 7或更低版本)。假设你的对象哈希分布均匀,项目的数量不比所使用的桶的数量大几个数量级
HashSet
则可以认为平均时间复杂度为
O(1)
.
因此,代码的每一行都有时间复杂度:
this.graph.getNodes().forEach((key, value) -> { // O(|V|)
this.queue.add(key); // O(1)
this.queue.addAll(value); // O(|vertex.adjacent|)
while(!this.queue.isEmpty()) { // O(1)
Vertex vertex = this.queue.poll(); // O(1)
if(this.visited.contains(vertex)) { // O(log(|V|)) worst-case
continue; // O(1)
} //
System.out.print(vertex + " -> "); // O(1)
visited.add(vertex); // O(1)
} //
}); //
在这种情况下,使用
addAll
实际上这不是问题,因为对于每个顶点,您都在添加每个相邻的顶点,这相当于在单个方向上迭代边。所以,在整个外环上聚合,你要在每个方向上添加每条边的相邻顶点,所以这是
O(2E)
,或者简单地说
O(E)
.
你遇到的问题是,检查顶点是否被访问是
O(log(n))
最坏情况下的时间复杂度,每次您想将每个顶点添加到队列中时,都会对其执行此操作。由于您检查了每条边的每个相邻顶点,因此在整个过程中,这是
O(E.log(V))
最坏情况下的时间复杂度(以及
O(E)
假设前面提到的前提条件成立)。
你的整个算法是
O(V + E.log(V))
最坏情况下的时间复杂度(或
O(V + E.V)
如果您使用的是Java 7或更早版本,则最坏情况下的时间复杂度)以及
O(V + E)
最佳情况/平均时间复杂度(再次假设满足前面的先决条件)。
要解决最坏情况下的时间复杂性问题:
-
你可以添加一个
visited
旗到
Vertex
对象并在对象上设置标志,或者,如果您的每个顶点都有一个唯一的顺序数字索引(即它们被编号
0 .. |V|-1
),您可以在
BreadthFirstSearch
对应于每个顶点的对象,并更新数组中的标志。无论哪种方式,您都可以在中更新标志
O(1)
时间。
-
您可以停止使用
HashMap
存储邻接列表,并将列表作为每个顶点的属性进行存储。
类似于:
public class BreadthFirstSearch {
private final Graph graph;
private final Queue<Vertex> queue;
private final boolean[] visited;
public BreadthFirstSearch(Graph graph) {
this.graph = graph;
this.queue = new LinkedList<>();
this.visited = new boolean[graph.nodes.size()];
}
private void enqueue(final Vertex vertex)
{
int index = vertex.index;
if (!this.visited[index])
{
this.queue.add(vertex);
}
}
public void doBFS() {
this.graph.getNodes().forEach((key, value) -> {
this.enqueue(key);
while(!this.queue.isEmpty()) {
final Vertex vertex = this.queue.poll();
System.out.print(vertex + " -> ");
LinkedList<Vertex> neighbours = vertex.getAdjacent();
for (final Vertex adjacent: neighbours)
{
this.enqueue(adjacent);
}
}
});
}
}
这假设你可以写一个
vertex.getAdjacent
方法具有
O(1)
最坏情况下的时间复杂性。使用您当前的实现
哈希图
要存储关系,这不太可能,因为
HashMap.get
有
O(log(n)
最坏情况下的时间复杂性。相反,您可能需要将存储相邻边视为每个边上的属性
顶点
实例而不是
哈希图
在图表上。