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();
}
//

隣接リストでは、頂点を配列/ハッシュ テーブルに格納し、各頂点が他の頂点と形成するエッジのリンク リストを格納します。

私の主な質問はこれです: get unvisited child node をどのように実装しますか? ノードを訪問済みとしてマークすることは明らかですが、トラバースするときに、リンクされたすべてのリストを通過するため、すべてのエッジを 2 回カウントするため、複雑さは O(2m+n) ですよね? それはO（m + n）に切り捨てられますか？

また、隣接行列に同様の戦略を採用できますか? サイズ nxn の行列が与えられ、特定の要素が存在するかどうかを知りたい場合、それを把握するために BFS を実行できますか?

ありがとう。

4

1 に答える 1

3

O 表記法は乗法定数を 1 に「還元」するため、O(2m+n) は O(m+n) に還元されます。

于 2011-12-22T18:09:47.933 に答える