Connected Component1 [Algorithm] 연결 성분(Connected Component) 연결 성분(Connected Component) 나누어진 각각의 그래프 그래프는 여러개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수있다. 즉, 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부른다. 연결 성분의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또, 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. 연결 성분을 찾는 방법은 DFS,BFS 탐색을 이용하면 된다. 연결 성분을 찾는 방법 연결 성분을 찾는 방법은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용하면 된다. BFS,DFS를 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 된다. 다음에 방문하지 않은 정점을 선택해서 .. 2020. 6. 27. 이전 1 다음