nik*_*yas 4 breadth-first-search adjacency-matrix
在bfs中我们必须查找每个节点,并且对于每个节点,我们必须查看row的所有元素.这不需要O(V ^ 2)(邻接矩阵中的元素数)时间,因此对于邻接矩阵不应该总时间为O(V ^ 2 + E).
Vam*_*gam 10
使用邻接矩阵实现的BFS的复杂度将为O(| V | 2).这主要是因为每次我们想要找到与给定顶点'U'相邻的边是什么时,我们必须遍历整个数组AdjacencyMatrix [U],这是长度| V |的偏离.
想象一下BFS作为前沿发展.你得到一个起始顶点S,它处于-0级.所有相邻的顶点都处于-1级.然后,我们将所有顶点的所有相邻顶点标记为级别-1,这些顶点没有级别. - 2.因此,每个顶点只属于一个边界(或级别).当一个元素在边界时,我们检查一次它的相邻顶点,这需要O(| V |)时间.因为,边界覆盖| V | 在算法过程中,总时间将变为O(| V |*| V |),即O(| V | 2).
当由邻接矩阵和矩阵实现时BFS的复杂度差异是由于这样的事实:在邻接矩阵中,为了告知哪个节点与给定顶点相邻,我们采用O(| V |)时间,而不考虑边缘.然而,在邻接列表中,它立即可供我们使用,花费时间与相邻顶点本身成比例,这对于所有顶点的总和| V | 是| E |.因此,邻接列表的BFS给出O(| V | + | E |).
我希望我的回答对你有帮助,如果有,请告诉我......!☺