정점 X와 Y가 무방향 그래프의 동일한 연결 구성요소에 있는지 쿼리

그래프 이론은 모든 정점 쌍이 경로로 연결되고 다른 정점은 연결되지 않은 무방향 그래프의 하위 그래프인 연결된 구성 요소에 대한 연구를 다룹니다.

이 글에서는 C/C++ 프로그래밍 언어를 사용하여 무방향 그래프에서 두 정점 X와 Y가 동일한 연결 구성 요소에 속하는지 확인하는 방법을 살펴보겠습니다. 이 문제를 해결하기 위한 최소한 두 가지 다른 방법을 명확히 하기 전에 방법의 구문과 이론적 근거를 명확히 할 것입니다. 또한 각 방법에 대한 구체적인 코드 예제와 해당 결과를 제공합니다.

문법

제공된 코드 조각은 그래픽 표현을 위해 C++에서 세 가지 함수를 선언합니다. isConnected 함수는 두 정점 X와 Y를 가져와 동일한 연결 구성 요소에 속하는지 여부를 나타내는 부울 값을 반환합니다. addEdge 함수는 두 개의 꼭지점 X와 Y를 가져와 그래프에서 두 꼭지점 사이에 연결을 만듭니다. InitializeGraph 함수는 정수 값 n을 입력으로 사용하고 n개의 정점이 있는 그래프를 설정합니다. 이러한 기능은 깊이 우선 탐색, 너비 우선 탐색 등 다양한 그래프 알고리즘을 사용하여 실행되어 두 꼭지점의 연결성을 확인하고 그래프에서 꼭지점 간의 연결을 설정할 수 있습니다.

으아악

알고리즘

1단계 - 그래프 초기화 기능을 사용하여 지정된 정점 수로 그래프를 초기화합니다.

2단계 - addEdge 함수를 사용하여 정점 사이에 가장자리를 추가하세요

3단계 - 정점과 관련된 모든 정점을 순회하고 방문한 것으로 표시하는 그래프 순회 방법을 구현합니다.

4단계 - 구성된 그래프 순회 방법을 사용하여 정점 X와 Y를 모두 방문했는지 확인합니다.

5단계 - 정점 X와 Y를 모두 방문하면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

방법

• 방법 1 - DFS를 사용합니다. 이는 그래프를 연구하기 위해 정점을 반복적으로 방문하고 방문한 것으로 표시하는 그래프 순회 알고리즘입니다.

• 방법 2 - 데이터 구조를 사용하여 컬렉션을 여러 하위 그룹으로 분할하는 것을 모니터링하는 통합 검색 방법을 사용합니다. 무방향 그래프의 연결된 부분을 효과적으로 식별할 수 있습니다.

방법 1

이 방법에서는 DFS를 사용하여 정점 X와 Y가 동일한 연결된 구성 요소에 있는지 확인하고 정점 X에서 시작하여 DFS를 사용하여 그래프를 탐색할 수 있습니다.

예 1

이 코드는 두 정점 X와 Y가 그래프의 동일한 연결된 구성 요소에 속하는지 확인하기 위해 평가됩니다. DFS(깊이 우선 검색) 알고리즘을 사용하여 그래프를 탐색하고 정점의 연결성을 결정합니다. 그래프는 정점 사이의 가장자리가 각 정점의 이웃 정점 목록으로 저장되는 인접 목록을 사용하여 설명됩니다. 코드는 방문한 배열을 초기화하여 DFS 순회 중에 탐색된 정점을 모니터링합니다. 정점 X에서 DFS 기능을 실행합니다. DFS 프로세스 중에 정점 Y가 방문한 것으로 발견되면 X와 Y가 모두 동일한 연결된 구성 요소의 일부임을 의미합니다. 주요 함수는 인접 목록을 생성하고 여기에 간선을 추가하여 그래프를 설정한 다음 여러 쿼리를 수행하여 두 정점이 동일한 연결된 구성 요소에 있는지 확인합니다.

으아악

출력

으아악

방법 2

이 접근 방식에서는 정점 X와 Y가 동일한 링크 구성 요소에 있는지 확인하기 위해 and find 메서드를 사용하기 위해 먼저 각 정점을 분리된 집합에 할당할 수 있습니다. 그런 다음 그래프의 각 모서리에 대해 모서리 끝점 컬렉션을 결합할 수 있습니다. 마지막으로 정점 X와 Y가 동일한 집합의 구성원인지 여부를 확인하여 이들이 관련된 구성 요소임을 나타낼 수 있습니다.

예 2

이 코드는 두 정점이 그래프의 동일한 연결된 구성 요소에 있는지 확인하는 알고리즘을 구현하고 찾습니다. 입력은 정점 수 n, 가장자리 수 m, 가장자리 배열 Edges[m][2], 쿼리 번호 q 및 쿼리 배열 Queries[q][2]의 형태로 하드코딩됩니다. merge(u, v) 함수는 정점 u를 포함하는 집합을 정점 v를 포함하는 집합과 병합합니다. areVerticesInSameComponentUnionFind(X, Y) 함수는 정점 X와 Y가 부모 노드를 찾아서 동일한 연결된 구성 요소에 있는지 확인하고 동일한지 확인합니다. 동일하면 정점은 동일한 연결된 구성요소에 있고, 그렇지 않으면 그렇지 않습니다. 쿼리 결과가 콘솔에 인쇄됩니다.

으아악

출력

으아악

결론

이 코드에서는 두 개의 방향이 지정되지 않은 그래프 정점 X와 Y가 서로 관련되어 있는지 확인하는 두 가지 방법을 소개합니다. 두 번째 전략은 결합 찾기 알고리즘을 사용하여 분리된 세트를 추적하는 반면, 첫 번째 접근 방식은 깊이 우선 검색(DFS)을 사용하여 그래프를 탐색하여 방문한 정점을 표시합니다.

위 내용은 정점 X와 Y가 무방향 그래프의 동일한 연결 구성요소에 있는지 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!