2

我试图弄清楚 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）？

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

谢谢。

4

1 回答 1

3

The O-notation "reduces" multiplicative constants to 1, so O(2m+n) gets reduced to O(m+n).

于 2011-12-22T18:09:47.933 回答