kruscal algorithm 크루스칼 알고리즘

//
//  main.cpp
//  kruskal_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};

int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight>edge2.weight;
    }
};
int rep_check(int v){
    if(represent[v]==-1)
        return -1;
    else if(represent[v]==v)
        return v;
    else
        return rep_check(represent[v]);
}
int main(int argc, const char * argv[]) {
    priority_queue,comp> q;
    int i,j,c,p,w,v1,v2,d=0;
    memset(represent,-1,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        if(represent[v1]==-1&&represent[v2]==-1){
            represent[v1]=v1;represent[v2]=v1;
        }
        else if(rep_check(v1)==rep_check(v2))
            continue;
        else{
            if(represent[v1]==-1)
                represent[v1]=rep_check(v2);
            else if(represent[v2]==-1)
                represent[v2]=rep_check(v1);
            else
                represent[rep_check(v2)]=v1;
        }
        d+=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}

+inverse

//
//  main.cpp
//  kruskal_inverse_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};
int ch;
int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight,comp> q;
    int i,j,w,v1,v2,d=0,temp;
    memset(represent,0,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
                d+=G[i][j];
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        temp=G[v1][v2];
        G[v1][v2]=max;G[v2][v1]=max;
        memset(check,0,7*sizeof(int));
        ch=0;
        cir(v1,v2);
        if(!ch){
            G[v1][v2]=temp;
            G[v2][v1]=temp;
            continue;
        }
        d-=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}