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)로 감소합니다.