9. 그래프 (Graph)

인접 리스트로 구현 - class 선언

typedef ChainNode* ChainNodePointer;

class Graph {
   private:
      ChainNodePointer *HeadNodes;	// first들의 배열 선언
      int n;				// 정점 수
      bool* visited;			// 방문 여부
   
   public:
      Graph (const int vertices = 0) : n(vertices) 
      { HeadNodes = new ChainNodePointer[n]; };

}

 

 

 

연결 요소

인접 리스트 : 모든 node 1번씩 방문, O(e) + for 반복문, O(n) = O(n+e) 소요

인접 행렬 : O($n^2$) 소요                  

void Graph::Components(){
// graph의 연결 요소들 결정
   
   visited = new bool[n];
   
   for (int i=0; i<n; i++)		// 미방문으로 초기화
      visited[i] = false;
   
   for(int i=0; i<n; i++){
      if (!visited[i]){
         DFS(i);		// 하나의 요소 발견
         OutputNewComponent();
      }
   }
   
   delete[] visited;
}