그래프에서 연결이 끊어진 서브 그래프를 찾습니다
https://stackoverflow.com/questions/1348783
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
알 수없는 수의 연결이 끊어진 서브 그래프가 포함 된 그래프가 있습니다. 그들 모두를 찾기위한 좋은 알고리즘 (또는 Java 라이브러리)은 무엇입니까?
해결책
나는 당신이 찾고있는 것이 일반적으로 홍수 채우기. BFS 또는 DFS를 통해 그래프를 가로 지르는 것은 당신에게 달려 있습니다.
기본적으로 당신은 표지되지 않은 (일명 무분별한) 노드를 가져 와서 새 레이블을 할당합니다. 해당 노드에서 인접한 모든 노드에 동일한 레이블을 할당하며 해당 노드에서 도달 할 수있는 모든 노드에도 할당합니다.
더 이상 도달 가능한 노드에 레이블을 지정할 수없는 경우 다른 표지되지 않은 노드를 선택하여 다시 시작합니다. 이 새 노드가 표지되지 않았다는 사실은 이전 노드에서 도달 할 수 없으므로 다른 분리 된 구성 요소에 있음을 의미합니다.
더 이상 표지되지 않은 노드가 없으면 사용해야 할 고유 한 레이블의 수는 그래프의 구성 요소 수입니다. 각 노드의 레이블은 어떤 노드가 어떤 구성 요소의 일부인지 알려줍니다.
다른 팁
Java 구현은 아니지만 누군가에게 유용 할 것입니다. 여기 Python에서 수행하는 방법은 다음과 같습니다.
import networkx as nx
g = nx.Graph()
# add nodes/edges to graph
d = list(nx.connected_component_subgraphs(g))
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph
추가 정보 여기.
이 질문에는 완전히 설명되지 않은 많은 측면이 있으므로 다소 철저한 대답을하겠습니다. 텍스트의 벽을 게시하는 경향이 있음에도 불구하고. :/ 이것은 이것이 숙제 또는 자기 교육 질문이라고 가정하고 있기 때문에 똑바로 대답하지 않을 것입니다.
그래프 연결을 감지하기위한 두 가지 기본 알고리즘은 깊이의 첫 번째 검색 그리고 폭 너비 첫 번째 검색. 그것들은 실제로 당신이보고 싶은 2 개의 출발점입니다. 둘 다 솔루션에 도달 할 것이지만 다른 방식으로, 그리고 문제의 심층적 인 측면을 고려하지 않고 "더 나은"것을 주장하기가 어렵습니다. 하지만 계속하자.
앞에서 언급했듯이, 당신은 몇 가지 중요한 세부 사항을 배제했으며 여기서 몇 가지 가능성을 다룰 것입니다.
그래프가 지향적이거나 방향이 없습니까? 그리고 "강한"의미에서 연결성을 고려합니까 (이 경우 Oggy의 답변을 참조하십시오) 또는 "약한"의미에서 연결성이 있습니까? 답변에 따라 알고리즘에 미묘하게 다른 방식으로 접근해야합니다. 방향이없는 그래프의 경우 약하고 강한 연결성이 동일하므로 좋습니다. 그러나 알고리즘을 구현하거나 찾는 동안 그래프 구조를 염두에 두어야합니다.
또한, "서브 그래프를 찾는 것"(paraphrase)이 의미하는 바에 대한 질문이 있습니다. 일반적으로 그래프 연결은 결정 문제입니다. 단순히 "연결된 그래프가 하나 있습니다"또는 "두 개 이상의 하위 그래프 (일명, 연결이 끊어 졌음)가 있습니다." 이에 대한 알고리즘이 있으므로 최소한 양의 서적이 필요합니다. :) 다음 단계는 다음과 같습니다 세다 그래프의 수는 문자 그대로 그 수와 그 책은 그렇게 나쁘지 않습니다. 두드러지기, 각 하위 그래프에서 노드 목록을 원할 수 있습니다. 마지막으로, 당신은 문자 그대로 서브 그래프, 가장자리 및 모든 것을 복사하고 싶을 수도 있습니다 (따라서 리턴 유형은 각 그래프가 연결되어 있음을 암시 한 무적의 그래프 목록이 될 것입니다). 이러한 다른 결과 유형 중 어느 것도 다른 알고리즘이 필요하지 않지만 확실히 서적에 대한 다른 접근법이 필요합니다.
이 모든 것은 꽤 기본적인 질문에 대해 말도 안되는 양의 과잉처럼 보일지 모르지만 간단한 그래프 질문과 관련된 모든 측면을 강조 할 것이라고 생각했습니다. 일종의 절벽 행거로서,이 중 어느 것도 런타임이나 메모리 사용에 대해서도 아직 접촉하지 않는 방법에 주목하십시오! :) -Agor
나는 당신이 모든 (강하게) 연결된 구성 요소를 찾고 싶다고 가정하고 있습니까? 그것을 위해 당신은 사용할 수 있습니다 타잔의 알고리즘 (DFS의 변형)
연결된 모든 연결 노드를 찾기위한 폭이 넓은 첫 번째 검색은 어떻습니까? 연결된 노드 목록이 있으면 모든 노드 목록 에서이 목록을 빼냅니다. 연결이 끊긴 노드 목록으로 끝납니다
