Graph DFS with Recursion

<C언어로 쉽게 풀어쓴 자료구조 > 내용

구현은 앞에서 만든 내용을 가지고 오자.

 

1. 개념

깊이 우선 탐색( DFS )은 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가

더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시

탐색을 진행하는 방법과 유사하다.

 

깊이 우선 탐색은 그래프의 시작 정점에서 출발하여

먼저, 시작 정점StartVertex를 방문하고 방문하였다고 표시를 한다.

StartVertex에 인접한 정점들 중에서 아직 방문 하지 않은 정점u가 있다면

u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다.

이 탐색이 끝나게 되면,

다시 StartVertex에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다.

만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다.

깊이 우선 탐색도 자기 자신을 다시 호출하는 재귀 알고리즘의 형태를 가지고 있음을 알 수 있다.

 

밑에서 보다시피 enum으로 정의한 A를 시작 정점으로 선택할 것이다.

 

방문 여부를 긹하기 위해 배열 pVisit를 사용할 것이며,

pVisit배열은 Graph구조체에 정의하고, pVisit배열값은 모두 0으로 초기화한다.

pVisit배열의 길이는 정점의 개수이다.

정점이 방문될 때마다 해당 정점에 대한 방문 기록이 pVisit배열에 1로 변경할 것이다.

즉, 0(A)번 정점이 방문이 되면, pVisit[0] = 1로 세팅하는 것으로 방문을 기록한다.

 

위의 과정을 진행할 함수이름을 SearchDFSByRecur라 하겠다.

 

DFS탐색의 그림을 그려서 이해를 해보자.

아래에 임의의 그래프가 있다고 하자.

[그림 1]

위의 [그림 1]에 있는 그래프를 시작정점을 A라 두고, 깊이 우선 탐색을 진행해보자.

 

[그림 2]

[그림3]

[그림 4]

[그림 5]

[그림 6]

[그림 7]

[그림 8]

 

2. 깊이 우선 탐색 알고리즘

깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저 시작 정점v를 방문하고

방문하였다는 표시를 한다.

v에 인접한 정점들 중에서 아직 방문하지 않은 정점u를 선택한다.

만약 그러한 정점이 없다면 탐색은 종료한다.

만약 아직 방문하지 않은 정점u가 있다면, u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다.

방문 기록 여부는 배열을 이용해서 하자. 방문을 하였으면 1로 기록한다.

 

3. 구현

< Graph.h >

< Graph.c >

< main.c >

프로그램 결과

4. 헤더 파일 & 소스 파일

common.h

0.00MB

Graph.c

0.00MB

Graph.h

0.00MB

main.c

0.00MB