11.1 너비 우선 탐색(인접 행렬) 구현(디딤돌 자료구조와 알고리즘 with C++)

11.1 너비 우선 탐색(인접 행렬) 구현

제일 먼저 인접 행렬로 너비 우선 탐색을 구현해 보아요.

 

그래프와 Heuristic에 관한 코드는 10.3.3 깊이 우선 탐색(인접 행렬) 코드와 같으니 참고하세요.

 

먼저 깊이 우선 탐색하는 순서를 이해하기 쉽게 구현한 코드를 구현합시다.

너비우선 탐색(인접행렬).zip

int main()

{

먼저 그래프를 생성하고 간선을 추가하세요.

    Graph *graph = new Graph(9);//그래프 동적 생성

    graph->AddEdge(0, 1);//간선 추가

    graph->AddEdge(0, 2);//간선 추가

    graph->AddEdge(1, 2);//간선 추가

    graph->AddEdge(1, 3);//간선 추가

    graph->AddEdge(2, 4);//간선 추가

    graph->AddEdge(3, 6);//간선 추가

    graph->AddEdge(4, 5);//간선 추가

    graph->AddEdge(4, 6);//간선 추가

    graph->AddEdge(4, 7);//간선 추가

    graph->AddEdge(6, 8);//간선 추가

    graph->ViewNeighbors();

 

너비 우선 탐색은 큐를 이용합니다.

    queue<Heuristic *> hq;

초기 경험 정보를 생성하여 큐에 보관하세요.

    Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성

    hq.push(heu);//큐에 보관

 

 

큐가 빌 때까지 반복합니다.

    while(hq.empty() == false) //반복(큐가 비어 있지 않다면)

    {

큐에서 경험 정보를 꺼내오세요.

        heu = hq.front();//큐에서 경험 정보 꺼내옮

        hq.pop();

목적지에 도달하였는지 찾는 중인지 출력하세요.

 

만약 최단 거리를 찾았을 때 더 이상 작업을 진행하기 원하지 않는다면 반복문 탈출하는 구문을 사용하는 형태로 수정하세요. 여기에서는 큐가 빌 때까지 전수 조사하기로 할게요.

        if(heu->IsGoal())//목적지에 도달하면

        {

            cout<<"===== 솔루션 ";           

        }

        else

        {

            cout<<"찾는중 ";

        }

현재까지 방문한 경로를 출력하세요.

        heu->View();

 

현재 경험에서 다음 경험 목록을 조사합니다.

 

EnumNext 메서드에서는 현재 경험의 마지막 방문한 정점에서 경험하지 않은 이웃 정점을 추가 방문하는 다음 경험을 생성하여 반환하는 작업을 수행합니다.

        Heues nheues = heu->EnumNext();//큐에서 꺼내온 경험 정보에서 다음 경험 목록 조사

        HIter seek = nheues.begin();

        HIter last = nheues.end();

        for(  ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)

        {

조사한 다음 경험 목록을 큐에 보관하세요.

           hq.push(*seek);//큐에 보관

        }

더 이상 필요없는 경험을 소멸하세요.

        delete heu;

    }

    return 0;

}

 

▷ 실행 결과

=== 이웃 정점 ===

0의 이웃: 1 2

1의 이웃: 0 2 3

2의 이웃: 0 1 4

3의 이웃: 1 6

4의 이웃: 2 5 6 7

5의 이웃: 4

6의 이웃: 3 4 8

7의 이웃: 4

8의 이웃: 6

 

찾는중 Foots: 0

찾는중 Foots: 0 1

찾는중 Foots: 0 2

찾는중 Foots: 0 1 2

찾는중 Foots: 0 1 3

찾는중 Foots: 0 2 1

찾는중 Foots: 0 2 4

찾는중 Foots: 0 1 2 4

찾는중 Foots: 0 1 3 6

찾는중 Foots: 0 2 1 3

찾는중 Foots: 0 2 4 5

찾는중 Foots: 0 2 4 6

찾는중 Foots: 0 2 4 7

찾는중 Foots: 0 1 2 4 5

찾는중 Foots: 0 1 2 4 6

찾는중 Foots: 0 1 2 4 7

찾는중 Foots: 0 1 3 6 4

===== 솔루션 Foots: 0 1 3 6 8

찾는중 Foots: 0 2 1 3 6

찾는중 Foots: 0 2 4 6 3

===== 솔루션 Foots: 0 2 4 6 8

찾는중 Foots: 0 1 2 4 6 3

===== 솔루션 Foots: 0 1 2 4 6 8

찾는중 Foots: 0 1 3 6 4 2

찾는중 Foots: 0 1 3 6 4 5

찾는중 Foots: 0 1 3 6 4 7

찾는중 Foots: 0 2 1 3 6 4

===== 솔루션 Foots: 0 2 1 3 6 8

찾는중 Foots: 0 2 4 6 3 1

찾는중 Foots: 0 2 1 3 6 4 5

찾는중 Foots: 0 2 1 3 6 4 7

다음은 현재 경험에서 다음 경험을 조사한 후에 바로 목적지에 도달하였는지 확인하는 형태로 코드를 수행한 예제입니다.

int main()

{

    Graph *graph = new Graph(9);//그래프 동적 생성

    graph->AddEdge(0, 1);//간선 추가

    ...중략...

    graph->ViewNeighbors();

   

    queue<Heuristic *> hq;

   

    Heuristic *heu = new Heuristic(graph,0,8);//초기 경험 정보를 생성

    hq.push(heu);//큐에 보관

    while(hq.empty() == false) //반복(큐가 비어 있지 않다면)

    {

        heu = hq.front();//큐에서 경험 정보 꺼내옮

        hq.pop();

        cout<<"찾는중 ";

        heu->View();

        Heues nheues = heu->EnumNext();//큐에서 꺼내온 경험 정보에서 다음 경험 목록 조사

        HIter seek = nheues.begin();

        HIter last = nheues.end();

        for(  ;seek != last; ++seek)//반복(다음 경험 목록을 순차적으로 반복)

        {

다음 경험 목록을 순차적으로 순회하며 목적지에 도달하였는지 확인합니다.

            if((*seek)->IsGoal())//목적지에 도달하면

            {

                cout<<"===== 솔루션 ";           

                (*seek)->View();

                delete (*seek);

            }

            else

            {

                hq.push(*seek);//큐에 보관

            }

        }

        delete heu;

    }

    return 0;

}

 

 

▷ 실행 결과

=== 이웃 정점 ===

0의 이웃: 1 2

1의 이웃: 0 2 3

2의 이웃: 0 1 4

3의 이웃: 1 6

4의 이웃: 2 5 6 7

5의 이웃: 4

6의 이웃: 3 4 8

7의 이웃: 4

8의 이웃: 6

 

찾는중 Foots: 0

찾는중 Foots: 0 1

찾는중 Foots: 0 2

찾는중 Foots: 0 1 2

찾는중 Foots: 0 1 3

찾는중 Foots: 0 2 1

찾는중 Foots: 0 2 4

찾는중 Foots: 0 1 2 4

찾는중 Foots: 0 1 3 6

===== 솔루션 Foots: 0 1 3 6 8

찾는중 Foots: 0 2 1 3

찾는중 Foots: 0 2 4 5

찾는중 Foots: 0 2 4 6

===== 솔루션 Foots: 0 2 4 6 8

찾는중 Foots: 0 2 4 7

찾는중 Foots: 0 1 2 4 5

찾는중 Foots: 0 1 2 4 6

===== 솔루션 Foots: 0 1 2 4 6 8

찾는중 Foots: 0 1 2 4 7

찾는중 Foots: 0 1 3 6 4

찾는중 Foots: 0 2 1 3 6

===== 솔루션 Foots: 0 2 1 3 6 8

찾는중 Foots: 0 2 4 6 3

찾는중 Foots: 0 1 2 4 6 3

찾는중 Foots: 0 1 3 6 4 2

찾는중 Foots: 0 1 3 6 4 5

찾는중 Foots: 0 1 3 6 4 7

찾는중 Foots: 0 2 1 3 6 4

찾는중 Foots: 0 2 4 6 3 1

찾는중 Foots: 0 2 1 3 6 4 5

찾는중 Foots: 0 2 1 3 6 4 7