(C언어)17.그래프(간단), 깊이우선, 너비우선 탐색

<인접 노드 그래프>

주의 : 매우 간단함

그래프의 구조는 크게 두가지로 나뉘어져 있습니다. 꼭짓점, 변.

동그라미들이 꼭짓점, 선들이 변이라고 생각하면 됩니다.

한 꼭짓점에 대해서 연결된 변들의 개수를 차수라고 하며, 예를 들면, 2의 차수는 3, 3의 차수는 2, 6의 차수는 1입니다.

그래프는 무방향 그래프, 방향 그래프로 나뉘어져있으며, 무방향 그래프는 위의 그래프와 같이 변의 순서가 없는 그래프입니다.

예를 들면, 4번 꼭짓점과 5번 꼭짓점 사이의 변을 부를때 (4,5)로 읽으나 (5,4)로 읽으나 같다는 소리입니다.

방향 그래프는 무방향 그래프와 같이 변의 순서가 있는 그래프입니다. 서로가 서로를 가리키고 있을 때는 둘 사이의 변이 두개이며, 각각 (4,5)와 (5,4)로 읽습니다. 이 두 변은 다른 변입니다.

각각 다른 두 개의 꼭짓점이 변 하나를 두고 이어져 있으면, 우리는 그것을 보고 "인접한다"라고 합니다. 

그래프 표현법에는 인접 리스트, 인접 행렬 이 두개가 있는데, 제가 구현한 코드는 인접 행렬 코드(이긴 한데 뭔가가 많이 생략되어 있는 인접 행렬...)

코드 올립니다.

#include <stdio.h>
#include <stdlib.h>
 
int main(){
    int arr[10][10];
       int node_num, i, j;
       int true_or_false = 0;
       for(i=0; i<10; ++i){
           for(j=0; j<10; ++j){
               arr[i][j]=2;
           }
       }
       printf("노드 몇개?(모두 합쳐서 10개까지 가능) : ");
       scanf("%d", &node_num);
       for (i=0; i<node_num; ++i){
        for (j=0; j<node_num; ++j){
               if(arr[i][j]==1)
                continue;
            if(arr[j][i]==0)
                continue;
            if(i == j)
                continue;
            printf("%d번 노드 : %d번 노드와 인접합니까?(맞으면 1, 틀리면 0) : ", i, j);
            scanf("%d", &true_or_false);
            arr[i][j] = true_or_false;
            arr[j][i] = true_or_false;
          }
       }
       for(i=0; i<node_num; ++i){
        printf("현재 %d번 노드는 ", i);
          for (j=0; j<node_num; ++j){
            if (arr[i][j]==1){
                   printf("[%d번] ", j);
            }
        }
    printf("노드와 인접되어있습니다.\n");
      }
}

노드 하나에 대해서 인접한 노드를 모두 입력받은 다음 연결관계를 표시하는 코드입니다.

<깊이 우선 탐색>

위의 그래프 구현 코드를 이용해서

이런 모양의 그래프를 구현해 보았습니다.

요렇게요!

깊이 우선 탐색 방법은 

<<현재 깊이 우선 탐색 방법 코딩중에 원초적인 방법의 에러, 혹은 실력의 부족으로 에러난 코드만 올리게 되었습니다. 절대 참고하지 말아 주십쇼>>

#include <stdio.h>
#include <stdlib.h>
 
int arr[10][10];
 
 
int dfs(int num){
    int stack[10][2]={0,};
    int i, j;
    int stack_i, stack_j;
    int cnt=0;
    stack_i=0;
    stack_j=0;
    for(i=0; i<10; ++i){
        for(j=0; j<10; ++j){
            if(i==num&&j==num)
                return cnt;
            if(arr[i][j]==1){//문제는 여기있는듯 합니다.
                stack[stack_i][stack_j]=i;
                stack[stack_i][stack_j+1]=j;
                ++stack_i;
                i=j;
                j=j+1;
                break;
            }
            if(j==9){//이 if문을 돈다는것, 그것은 더 깊이 내려갈 수 없다는 것.
                printf("세번째 이프문\n");
                printf("arr[%d][%d]\n", i, j);
                --stack_i;
                i=stack_i;
                j=stack[stack_i][stack_j+1];
                ++cnt;
                break;
            }
            printf("포문돌리기!\n");
        }
    }
    return 0;
}
 
int main(){
    
       int node_num, i, j, input, num;
       int true_or_false = 0;
       for(i=0; i<10; ++i){
           for(j=0; j<10; ++j){
               arr[i][j]=2;
           }
       }
       printf("노드 몇개?(모두 합쳐서 10개까지 가능) : ");
       scanf("%d", &node_num);
       for (i=0; i<node_num; ++i){
        for (j=0; j<node_num; ++j){
               if(arr[i][j]==1)
                continue;
            if(arr[j][i]==0)
                continue;
            if(i == j)
                continue;
            printf("%d번 노드 : %d번 노드와 인접합니까?(맞으면 1, 틀리면 0) : ", i, j);
            scanf("%d", &true_or_false);
            arr[i][j] = true_or_false;
            arr[j][i] = true_or_false;
          }
       }
       for(i=0; i<node_num; ++i){
        printf("현재 %d번 노드는 ", i);
          for (j=0; j<node_num; ++j){
            if (arr[i][j]==1){
                   printf("[%d번] ", j);
            }
        }
        printf("노드와 인접되어있습니다.\n");
    }
    printf("\n\n0 : 종료\n");
    printf("1 : 깊이 우선 탐색\n");
    printf("2 : 너비 우선 탐색\n");
      scanf("%d", &input);
      if(input==0)
          return 0;
      else if(input==1){
          printf("값 입력 : ");
          scanf("%d", &input);
          num=dfs(input);
          if(num==0){
              printf("값을 찾지 못하였습니다.\n");
          }
          else
              printf("%d번 찾았습니다\n", num);
      }
      else if(input==2){
 
      }
      return 0;
}
 

<너비 우선 탐색>

1년 4개월이 지난 지금 수정을 합니다 ㅎ.. 너비우선탐색, 즉 BFS알고리즘은 깊이우선탐색(DFS)와는 다르게 큐(queue)를 사용합니다.

이 그래프를 다시 이용해보죠. 0부터 탐색을 시작한다고 했을 때, 다음과 같은 규칙으로 탐색합니다.

1. 큐가 비어있으면 탐색을 종료합니다.

2. 현재 큐에 가장 앞에 있는 값과 찾고싶은 값을 비교합니다. 두개가 일치하면 탐색을 종료합니다.

3. 현재 큐에 가장 앞에 있는 값과 연결된 모든 값을 큐에 넣어줍니다. (단, 한번 방문한 곳은 넣지 않습니다.)

4. 현재 큐에 가장 앞에 있는 값을 큐에서 뺍니다.

그럼 구현을 해볼까요?

#include <stdio.h>

int N, E;//N=총 노드 개수, E=총 간선 개수

int arr[101][101];

int queue[1001];

int visit[101];

int target;

int front=-1, rear=0;

int cnt=0;

void BFS(){

if(front==rear) return; //1번조건

else if(queue[front]==target) return; //2번조건

else{

cnt++;//탐색 횟수 ++

int cur_front=queue[front];//현재 큐에 가장 앞에 있는 값

for(int i=0; i<=N; ++i){

if(visit[i]) continue;

if(arr[cur_front][i]==1){

visit[cur_front]=1;

queue[rear++]=i;

}

}

}

front++;//4번째 조건.

BFS();

return;

}

int main(){

scanf("%d %d", &N, &E);

for(int i=0; i<E; ++i){

int a, b;

scanf("%d %d", &a, &b);//무향그래프라고 하겠습니다.

arr[a][b]=1;

arr[b][a]=1;//인접행렬의 값을 채워줍니다. a에서 b까지 도달할 수 있고, 반대도 가능합니다.

}

printf("want to find : ");

scanf("%d", &target);

printf("start : ");//시작할 곳을 지정해줍니다.

int start;

scanf("%d", &start);

front++;

rear++;

queue[front]=start;

BFS();

printf("total search : %d\n", cnt);

}

정확하죠?