什么是BFS的时间复杂度取决于图的表示？ [英] What is time complexity of BFS depending on the representation of the graph?

问题描述

$ b

• 一个邻接矩阵
$ b $我想知道BFS的时间复杂度是多少b
• 邻接列表


• 边缘列表





与其空间复杂度相同吗？

解决方案

使用邻接矩阵实现的BFS的复杂度将为O（| V | ² ） 。而且，当由邻接列表实现时， O（| V | + | E |）。




为什么在Adjacency Matrix的情况下更是如此？


这主要是因为每次我们想要找到与给定顶点'U'相邻的边时，我们必须遍历整个数组 AdjacencyMatrix [U] ，这是长度 | V | 。





想象一下BFS的进展是前沿。你需要一个起始顶点 S ，该顶点在 0 级别。所有相邻的顶点都在 1 级别。然后，我们将所有等级为1的顶点的所有相邻顶点都标记为 2 。所以，每个顶点只属于一个边界（或水平）。当一个元素处于边界时，我们检查一次它的相邻顶点，这需要O（| V |）时间。因为，边界覆盖| V |元素在算法的过程中，总时间将变为O（| V | * | V |），即O（| V | ² ）。



由邻接矩阵和矩阵实现的BFS的复杂性差异是由于在邻接矩阵中，为了告诉哪些节点与给定顶点相邻，我们采用O（| V |）时间，而不考虑边缘。然而，在邻接列表中，它立即可用，需要与邻近顶点本身成比例的时间，对所有顶点进行求和| V |是| E |。所以，按邻接列表的BFS给出O（| V | + | E |）。




I was wondering what is the time complexity of BFS, if I use:

• an adjacency matrix
• adjacency list
• edge list

Is it same as their space complexity?

解决方案

The complexity of BFS implemented using an Adjacency Matrix will be O(|V|²). And that when implemented by an Adjacency List is O(|V| + |E|).

Why is it more in the case of Adjacency Matrix?

This is mainly because every time we want to find what are the edges adjacent to a given vertex 'U', we would have to traverse the whole array AdjacencyMatrix[U], which is off course of length |V|.

Imagine the BFS progressing as frontiers. You take a starting vertex S, which is at level 0. All the adjacent vertices are at level 1. Then, we mark all the adjacent vertices of all vertices at level 1, which don't have a level, to level 2. So, every vertex will belong to one frontier (or level) only. And when an element is in a frontier, we check once for its adjacent vertices, which takes O(|V|) time. As, the frontier covers |V| elements over the course of the algorithm, the total time would become O(|V| * |V|) which is O(|V|²).

The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take O(|V|) time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives O(|V| + |E|).

这篇关于什么是BFS的时间复杂度取决于图的表示？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！