그림 없 이 두 점 사이 의 가장 짧 은 경 로 를 찾 습 니 다.

5205 단어 데이터 구조
1. 프로필
      무방 향 도 는 도 구조의 일종 이다.이번 프로그램 은 인접 표를 이용 하여 무방 향 도 를 실현 하고 광 도 를 통 해 두 점 사이 의 가장 짧 은 경 로 를 우선적으로 찾 습 니 다.
 
2. 넓이 우선 옮 겨 다 니 기
      폭 우선 스 트 리밍 (BFS) 과 깊이 우선 스 트 리밍 (DFS) 은 그림 구조 에서 가장 많이 사용 되 는 스 트 리밍 방식 이다.그 중에서 넓 은 범위 가 우선 대열 에 맞 춰 두 점 사이 의 가장 짧 은 경 로 를 찾 을 수 있 고 다른 문제 도 해결 할 수 있다 (예 를 들 어 미로 의 가장 짧 은 탈출 로 를 찾 는 것).두 점 사이 의 가장 짧 은 경 로 를 찾 는 작업 은 다음 과 같은 몇 단계 로 나 뉜 다. 
      1. 먼저 시작 점 과 종점 src 와 dst 를 정의 합 니 다.이 어 하나의 배열 distance [] 를 정의 하여 각 점 에서 src 까지 의 거 리 를 저장 합 니 다.초기 화 할 때 각 점 에서 src 까지 의 거 리 는 INF (무한 함 을 표시 합 니 다. 여기 서 스스로 정의 할 수 있 습 니 다. 이 점 에서 src 까지 의 거 리 를 얻 지 못 했다 는 것 을 의미 합 니 다). distance [src] = 0.그리고 src 를 대기 열 에 넣 습 니 다.
      2. 추출 대기 열의 첫 번 째 결점 (처음에 대기 열 은 src 만 있 었 고 여 기 는 src 를 추출 하 는 것) 을 변수 top 에 두 었 습 니 다.
      3. 이 노드 의 모든 인접 점 을 획득 하고 distance [] 배열 의 각 인접 점 이 INF 인지 판단 합 니 다.이 노드 에 아직 접근 하지 않 았 다 는 설명 이 라면 distance [] 의 해당 위 치 를 distance [top] + 1 로 설정 합 니 다.INF 가 아니라면 이미 방문 했다 는 의미 로 건 너 뛰 었 다.
      4. top 변수 가 dst 와 같 을 때 까지 2 - 3 단 계 를 반복 합 니 다.대기 열 이 비어 있 을 때 까지 두 점 사이 에 경로 가 존재 하지 않 는 다 는 것 을 설명 합 니 다.
    요약 하면 노드 를 src 부터 순서대로 대기 열 에 넣 는 것 이 고 이미 대기 열 에 넣 은 노드 는 표 시 될 수 있 기 때문에 dst 를 찾 을 때 까지 반복 적 으로 대기 열 에 넣 지 않 습 니 다.이런 방법 으로 얻 은 경 로 는 반드시 가장 짧 은 길이 다.
 
3. 출력 최 단 경로
      위 에서 광 도 를 우선 사용 하여 두 점 사이 의 가장 짧 은 경로 의 길 이 를 찾 았 고 distance [dst] 에 저장 되 었 으 며 이 가장 짧 은 경 로 를 출력 하려 면 다른 방법 이 있 습 니 다.본인 이 여기 서 사용 하 는 방법 은 먼저 dst 를 창고 에 넣 은 다음 에 dst 의 인접 결점 중 어느 결점 이 distance 수조 에 있 는 값 이 distance [dst] - 1 인지 찾 아서 창고 에 넣 는 것 입 니 다.이 어 앞의 결산 점 을 계속 찾 아 창고 에 넣 었 다.이 동작 을 반복 해서 마지막 으로 src 를 찾 은 다음 스 택 에 있 는 요 소 를 순서대로 pop 합 니 다.창고 가 먼저 들 어간 후에 나 오 는 성질 때문에 이 경 로 를 얻 을 수 있다.
 
4. 코드 구현
      구체 적 인 코드 는 다음 과 같다.
#ifndef _GRAPH_H
#define _GRAPH_H

#include 
#include 
#include 

#define ERROR      -1
#define V_E_INFO    1
#define FIND        1
#define PATH        2
#define MAX         100

using namespace std;



class ArcNode
{
    private:
        int value;
        ArcNode *next;
    
    public:
        ArcNode(int , ArcNode * = nullptr);
        void set_next(ArcNode *);
        ArcNode *get_next() const;
        int get_value() const;
        void set_value(int);
};



class List
{   
    private:
        int value;
        ArcNode *firstnode;
    public:
        List(int = 0,ArcNode * = nullptr);
        ~List();
        ArcNode *Pop();
        void Push(int);
        int get_value() const;
        int is_exist(int) const;
        ArcNode *get_firstnode() const;
        void set_value(int);
        void dfs_find_path() const;
        void set_firstnode(ArcNode *);
        void print() const;
};



class Graph
{       
    private:
        List list[MAX];
        int vertices_num;
        int edge_num;
   
    public:
        Graph(int,int,int []);
        ~Graph();
        int get_vertices_num() const;
        int get_edge_num() const;
        List *get_list(int);
        void print() const;
        void dfs_print_path(int,int) const;
        void dfs_find_path(int,int,int [],stack & ,int &) const;
        void dfs(int src,int visited[],int &count) const;
        void dfs_print(int) const;
        void dfs_non_recursive() const;
        int find_shortest_path(int,int) const;
        void dfs(int,int []) const;
};

#endif

 BFS 최 단 경로 코드 찾기:
int Graph::find_shortest_path(int src,int dst) const
{
    queue myQ;

    int value[vertices_num];/       src   
    int head = 0;
    int output[10];
    for(int i = 0;i < vertices_num;i++)
    {
        value[i] = -1;//-1           
    }

    value[src] = 0;
    myQ.push(src);

    while(myQ.size())
    {
        head = myQ.front();
        myQ.pop();
        if(head == dst)
        {
            int find = dst;
            stack myS;
            myS.push(dst);
            while(find != src)
            {   
                for(int j = 0; j < vertices_num; j++)
                {
                    if((list[j].is_exist(find) == 1) && (value[find] == value[j] + 1))
                    {
                        myS.push(j);
                        find = j;
                        break;
                    }
                }
            }
            int count = myS.size();
            for(int j = 0;j < count;j++)
            {
                if(j == count - 1)
                    cout << myS.top() << endl;
                else
                {
                    cout << myS.top() << "-";
                    myS.pop();
                }
            }
        
            return FIND;
        }
        
        ArcNode *a = list[head].get_firstnode();
        while( a != nullptr)
        {
            if(value[a -> get_value()] == -1)
            {
                value[a -> get_value()] = value[head] + 1;
                myQ.push(a -> get_value());
            }
            a = a -> get_next();
        }
    }
    cout << "Error: no path between " << src << " and " << dst << endl;
    return ERROR;
}

좋은 웹페이지 즐겨찾기