鄰接矩陣列表O（m + n）上的BFS如何？

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×n的矩陣，並且我想知道是否存在特定元素，那麼我可以通過BFS來計算出結果嗎？

謝謝。

Answer 1

O符號「減少」乘法常數爲1，所以O（2m + n）減少到O（m + n）。