Prim 알고리즘 (최소 생 성 트 리)

문제 도입: 우리 가 전자 회 로 를 설계 하려 면 여러 구성 요소 의 바늘 과 발 을 연결 해 야 한다 고 가정 합 니 다.n 개의 바늘 을 연결 하려 면 n - 1 개의 연결선 으로 연결 할 수 있 으 며, 연결 할 때마다 두 개의 바늘 을 연결 할 수 있다.우리 가 원 하 는 연결선 의 길이 가 가장 짧 은 것 은 분명 하 다.위 와 같은 연결선 문 제 를 연결 되 지 않 은 방향 그림 으로 G = (V, E) 을 표시 할 수 있 습 니 다. V 는 바늘땀 즉 점 의 집합 입 니 다. E 는 바늘땀 간 에 가능 한 연결 (변 의 집합) 이 고 각 변 (u, v) 8712 ° E 에 대해 우 리 는 그것 에 권한 을 부여 합 니 다. w (u, v) 는 바늘땀 u 와 바늘땀 v 를 연결 하 는 대가 (연결선 의 길이) 입 니 다. 우 리 는 고리 가 없 는 부분 집합 T * 8838 ° E 를 찾 고 싶 습 니 다.모든 노드 (바늘땀) 를 연결 할 수 있 고 가장 작은 가중치 도 가진다. 즉,
w(T)=∑(u,v)∈Tw(u,v)
의 값 이 가장 작다.그림 은 고리 가 없 는 것 이 고 모든 정점 을 연결 하기 때문에 T 는 반드시 나무 일 것 이다. 이런 나 무 는 우리 가 가장 작은 생 성 나무 가 된다.
Prim 알고리즘 은 최소 생 성 트 리 를 해결 하 는 방법 으로 욕심 알고리즘 에 속한다.구체 적 인 사상 은 1 개의 노드 R 에서 출발 (
R * 8712 ° A) 는 V 의 모든 정점 을 덮 을 때 까지 자 랐 습 니 다. 알고리즘 은 한 걸음 한 걸음 집합 A 와 A 를 제외 한 모든 변 에 경량급 변 을 선택 하여 A 에 넣 었 습 니 다. 알고리즘 이 종 료 될 때 A 의 변 은 최소 생 성 트 리 를 만 듭 니 다.
다음은 저 개인의 실현 코드 를 드 리 겠 습 니 다.

#include <iostream>
#define INIFY 65533
#define ROW 9
#define COL 9
class Prim{
    private:
        int Array[ROW][COL];    
    public:
        void CreateGraphy(){
            int i,j,k,EdgeNumbers;
            std::cout<<"      : "<<std::endl;
            std::cin>>EdgeNumbers;
            //    
            for(int i=0;i<ROW;i++)
                for(int j=0;j<COL;j++)
                    Array[i][j]=INIFY;
            //       
            std::cout<<"             : "<<std::endl;
            while(EdgeNumbers--){
                std::cin>>i>>j>>k;
                //    
                Array[i][j]=k;
                Array[j][i]=k;
            }
        }
        void PrimAlgorithm(){
            int VertexNumber=ROW;
            int i,j,k,Min;
            int lowcost[VertexNumber],Adj[VertexNumber];
            //       
            lowcost[0]=0,Adj[0]=0;
            std::cout<<"        : "<<std::endl;

            for(int i=1;i<VertexNumber;i++){
                lowcost[i]=Array[0][i];
                Adj[i]=0;
            }
            for (i = 1; i <VertexNumber; i++){
                Min =INIFY; /*         ∞， */

                j = 1;
                k = 0;

            //               
            while(j<VertexNumber){
                if (lowcost[j] != 0 && lowcost[j] < Min){
                    Min = lowcost[j];
                    k = j;
                }

                j++;
            }

            std::cout << "(" <<Adj[k] << ", " << k << ")" << " "; /*            ，     */
            lowcost[k] = 0;/*   0        */

            for(j=1; j<VertexNumber; j++){
                if (lowcost[j] != 0 && Array[k][j]<lowcost[j]){
                    lowcost[j]=Array[k][j];/*         lowcost     */
                    Adj[j]=k;/*     k     Adj */
                }
            }
        }   
        std::cout<<std::endl;
}

};
int main(void){
    Prim ivec;
    ivec.CreateGraphy();
    ivec.PrimAlgorithm();
    return 0;
}

테스트 용례 는 알고리즘 서론 에서 prim 알고리즘 을 말 할 때의 테스트 용례 이다.그 중 a b c d e f g h i 는 1, 2, 3, 4, 5, 6, 7, 8 로 대체 합 니 다.실행 결과: - - - - - - - - - - - - - 참고 자료: 알고리즘 서론 제3 판http://blog.csdn.net/jnu_simba/article/details/8869876