그래프 연결요소
-
[NetwrokX] 그래프 연결성분(연결요소, Connected Components)Data & ML & AI/NetworkX 2022. 11. 15. 01:47
그래프 연결성분(연결요소)이란 쉽게 말해서 서로 분리되어 있는 그래프를 뜻합니다. 위의 (A~O)그래프에서는 3개의 연결성분이 있는거죠. 연결성분의 조건 연결성분 안의 모든 노드들은 동일한 성분 내의 다른 노드와 연결되어 있어야한다. 연결성분 밖에 있는 노드와 연결되면 안된다. 즉, 소외 되는 노드가 없으면서도 외부와의 접촉도 없는, 일종의 섬같은 성분을 연결성분이라고 부르는 겁니다. 위의 조건에 따라, 1번 : {A,E,F,G}는 연결성분이 아닙니다. (서로 분리되어 있으므로) 2번 : {K,L,O}는 연결성분이 아닙니다. (외부의 노드 M,L과 연결되어있으므로) 3번 : 오로지 {A,B,C,D,E}, {E,F,G,H,I}, {J,K,L,M,N,O}만 위 그래프의 연결성분입니다. 무방향 그래프 연결성분..