隣接行列リストの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(); 
} 
// 

、我々は、アレイ/ハッシュテーブル内の頂点を格納し、他の頂点と各頂点を形成縁のリンクされたリスト。

私の主な質問はこれです：どのように私たちは未訪問の子ノードを実装するのですか？訪問したノードにマークを付けるのは明らかですが、トラバースするとすべてのリンクされたリストを通過するので、すべてのエッジを2回カウントするので、複雑さはO（2m + n）ですか？それはちょうどO（m + n）に切り下げられますか？

また、隣接行列にも同様の戦略を適用できますか？サイズn x nの行列が与えられていて、特定の要素が存在するかどうかを知りたければ、それを理解するためにBFSを行うことはできますか？

ありがとうございました。

Answer 1

O表記は1に乗法定数を「減らす」ので、O（2m + n）はO（m + n）に減少します。