자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이)

자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이)

문제

Graph와 Edge를 주어주고 

특정 두 vertex를 지정하면 두 vertex 사이의 "모든 경로"를 탐색하여 출력합니다.

해결 알고리즘

알고리즘의 핵심은 dfs입니다.

0. 재귀함수로 구성합니다 void checkPath(int start, int end)

1. 함수에서 들어오면 visit 배열을 통해 방문 true 값 주고, start 값을 stack에 push합니다.

2. 만약 인자 start == end가 된다면 경로를 한 가지 발견한 것입니다.

3. 이 때 stack에 들어온 경로 따라서 출력 후에 도착한 지점(end)를 pop한 후에 함수를 return합니다.

4. 발견 못했을 시, 다음 경로를 탐색합니다 (조건 두가지 - 간선이 연결되어있고, 방문하지않은곳)

5. 다음 경로 탐색 후에 빠져나올 때는 visit 배열에 방문 값을 false 처리합니다(빠져나왔으므로)

6. 만약 for문으로 다음 경로도 탐색 못했을 경우에는 stack에 pop 후 빠져나옵니다.(찾지 못한 것이므로)

//연결되었는지 체크하는 함수
int checkEdge(int from, int to) {
    
    nodePointer search = adjacent[from];
    
    // NULL 일 때 까지 돌기
    while (search) {
        // 찾았으면
        if (search->data == to)
            return 1; // 1반환
        search = search->link;
    }
 
    return -1; // 연결안되어있으면 -1 반환
}
 
// 경로 찾기
void checkPath(int start, int end) {
 
    // 방문표시
    visit[start] = 1;
    push(start); // 넣기
 
    // 도착 체크하기
    if (start == end) {
        //출력
        fprintf(fp2, "%c ", stack[0]+ 'A');
        for (int i = 1; i <= top; i++)
            fprintf(fp2, "-> %c ", stack[i]+'A');//경로출력
        fprintf(fp2, "\n"); //줄바꿈
        
        pathCount++;
        pop(); // 도착지점 빼고 종료
 
        return; //종료
    }
 
    for (int i = 0; i < MAX; i++) {
        // 연결되어있고 방문하지 않은 곳이면 들어가기
        if (checkEdge(start, i) == 1 && visit[i] == 0) {
            checkPath(i, end); // 재귀 호출
            visit[i] = 0; // 빠져나오면 방문 취소
        }
    }
 
    pop(); // 위에서 들어왔더니 아무곳도 갈 수 없을 떄 탈출
 
}