breadth-first-search - BFS 在邻接矩阵列表 O(m+n) 上如何？

Question

我试图弄清楚 BFS 如何是 O(m+n)，其中 n 是顶点数，m 是边数。

算法是:

public void bfs()
{
    //BFS uses Queue data structure
    Queue q=new LinkedList();
    q.add(this.rootNode);
    printNode(this.rootNode);
    rootNode.visited=true;
    while(!q.isEmpty())
    {
        Node n=(Node)q.remove();
        Node child=null;
        while((child=getUnvisitedChildNode(n))!=null)
        {
            child.visited=true;
            printNode(child);
            q.add(child);
        }
    }
    //Clear visited property of nodes
    clearNodes();
}
//

在邻接列表中，我们将顶点存储在数组/哈希表中，以及每个顶点与其他顶点形成的边的链表。

我的主要问题是:我们如何实现未访问的子节点？很明显，您将节点标记为已访问，但是在遍历时，您会遍历所有链表，因此您将每条边计数两次，因此复杂度为 O(2m+n) 对吗？这是否只是四舍五入到 O(m+n) ？

另外，我们可以对邻接矩阵采用类似的策略吗？如果给我一个大小为 n x n 的矩阵，并且我想知道是否存在特定元素，我可以做一个 BFS 来弄清楚吗？

谢谢。

Answer 1

O 符号将乘法常数“减少”为 1，因此 O(2m+n) 减少为 O(m+n)。