11.2 너비 우선 탐색(정점과 간선 그래프) [디딤돌 자료구조와 알고리즘 with C++]

11.2 너비 우선 탐색(정점과 간선 그래프)

이번에는 정점과 간선 집합 그래프에서 너비 우선 탐색 코드를 구현합시다.

 

그래프와 Heuristic, Edge에 관한 코드는 10.4 깊이 우선 탐색(정점과 간선 그래프) 코드와 같으니 참고하세요.

 

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

너비우선탐색(정점과 간선 집합).zip

int main()

{

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

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

    for(int i = 0; i<8; i++)

    {

        graph->AddVertex(i);

    }

    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;

}