그래프가 주어지면 인접 행렬을 사용하여 깊이 우선 검색(DFS) 순회를 구현하는 C 프로그램

소개

그래프 이론을 통해 객체 또는 엔터티 간의 관계를 연구하고 시각화할 수 있습니다. 현재 컴퓨터 과학 기술에서 그래프 순회는 다양한 유형의 데이터 구조를 탐색하고 분석하는 데 중요한 역할을 합니다. 그래프에서 수행되는 주요 작업 중 하나는 순회(traversal)입니다. 즉, 특정 경로를 따라 모든 정점이나 노드를 방문합니다. 깊이 우선 접근 방식을 기반으로 하는 DFS 탐색을 통해 역추적하고 다른 분기를 탐색하기 전에 그래프의 깊이를 탐색할 수 있습니다. 이 기사에서는 C의 인접 행렬 표현을 사용하여 DFS 탐색을 구현합니다.

DFS 순회를 위해 인접 행렬 사용

그래프는 엔터티나 요소를 나타내는 정점 또는 노드와 이러한 정점을 연결하는 가장자리라는 두 가지 주요 구성 요소로 구성되며 이들 사이의 관계를 설명합니다.

가중 또는 비가중 그래프에서 꼭지점 간의 관계를 표현하는 유일한 방법은 인접 행렬을 이용하는 것입니다. 일반적으로 행은 소스 정점을 나타내고 열은 대상 정점을 나타내며 각 셀에는 해당 쌍 사이의 가장자리 존재 또는 가중치에 대한 정보가 포함되는 정사각 행렬의 형태를 취합니다.

예

입력은 그래프의 4개 정점을 사용하는 특정 요소 세트를 통해 제공됩니다. 입력은 다음과 같습니다

으아아아

그래프의 시작 정점이 2라고 가정합니다. 그래프는 정점 "2"부터 시작하여 탐색됩니다. 정점 "2"의 인접한 정점은 분명히 1과 3입니다. 시작 꼭짓점은 2이므로 순회 중에는 다시 접근할 수 없습니다. 정점 3은 정점 2 다음에 방문되며, 정점 3의 인접한 정점 1과 2를 확인해야 합니다. 정점 1과 정점 2가 방문되었으며 순회가 중지됩니다.

방법 1: 주어진 그래프에서 인접 행렬을 입력으로 사용하여 DFS 순회를 포함하는 C 프로그램

입력은 일부 숫자로 정의되며 for 루프를 사용하여 인접 행렬을 반복하고 DFS 순회를 반환합니다.

알고리즘

1단계: 프로그램은 먼저 주어진 그래프의 최대 노드 수를 나타내는 상수 "MAX"를 정의하고 "visited"라는 배열을 초기화하여 순회 중에 특정 노드를 방문했는지 추적합니다.

2단계: "dfs()" 함수는 정사각형 인접 행렬을 매개변수로 사용하고 그래프를 나타내는 "adjMatrix"를 사용하며 총 정점 수는 "vCount"이고 시작 정점은 `start`입니다. 이 함수는 주어진 그래프의 재귀적인 깊이 우선 탐색 순회를 수행합니다.

3단계: "dfs()" 함수에서 부울 기반 "visited[]" 배열의 인덱스를 사용하여 현재 처리된 각 정점을 "방문"으로 표시하고 그에 따라 값을 인쇄합니다.

4단계: "dfs()" 내부 루프는 연결된 정점을 얻을 수 없을 때까지 현재 노드의 방문하지 않은 모든 이웃을 재귀적으로 반복합니다.

5단계: main()에서는 중첩 루프를 사용하여 "vCount"의 정점 수 및 인접 행렬에 대한 해당 연결과 같은 사용자 입력을 읽습니다.

6단계: 그런 다음 사용자에게 원하는 시작 정점을 묻는 메시지를 표시한 다음 "visited[]" 배열의 각 요소를 0으로 초기화합니다(아직 방문한 노드가 없기 때문입니다).

7단계: 마지막으로 프로그램은 적절한 매개변수와 함께 "dfs()" 함수를 호출하여 깊이 우선 검색 순회를 시작하고 DFS 순회 경로를 인쇄합니다.

예

으아아아

출력

으아아아

결론

인접 행렬을 그래프 표현으로 사용하면 크거나 복잡한 데이터 세트에 대해 효율적으로 DFS를 수행할 수 있습니다. 본 논문에서는 이에 대해 자세히 설명하고 인접 행렬 기반 표현을 이용하여 깊이 우선 탐색 순회를 구현하는 C 프로그램을 제안한다. 깊이 우선 검색은 그래프 구조를 탐색하고 분석하는 강력한 알고리즘입니다.

위 내용은 그래프가 주어지면 인접 행렬을 사용하여 깊이 우선 검색(DFS) 순회를 구현하는 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!