데이터 구조 - kruskal 알고리즘 - 최소 생 성 트 리

먼저 kruskal 알고리즘 사상 을 이해 해 야 합 니 다. 연통 도 N = (V, {E}) 에 서 는 n 개의 정점 을 포함 하고 끝 이 없 는 비 연통 분 도 T = (V, {}) 를 초기 상태 로 만 들 고 변 집합 E 에서 가중치 가 가장 작은 변 을 찾 습 니 다. 이 변 의 두 정점 이 T 의 서로 다른 연 결 량 에 떨 어 지면 T 에 넣 습 니 다. 그렇지 않 으 면 버 리 고 다음 대가 가 작은 변 을 선택 하 십시오.이 를 통 해 모든 정점 이 같은 연결 분량 에 떨 어 질 때 까지 유추 하면 된다.
원본 코드 드 리 기:

  1 #include"iostream"
  2 using namespace std;
  3 
  4 #define MAX 1000
  5 
  6 typedef struct ArcCell
  7 {
  8     double adj;
  9     int *info;
 10 }ArcCell,adjmatrix[100][100];//adj        
 11 
 12 typedef struct 
 13 {
 14     char vexs[100];
 15     adjmatrix arcs;
 16     int vexnum,arcnum;//          
 17 }MGraph;//                
 18 
 19 typedef struct Node
 20 {//                       
 21     char start;
 22     char end;
 23     double value;
 24 }Node,Dgevalue[100];
 25 
 26 int locatevex(MGraph G,char ch)
 27 {//      ch      
 28     int k;
 29     for(int i=0;i<G.vexnum;i++)
 30     {
 31         if(G.vexs[i]==ch)
 32             k=i;
 33     }
 34     return k;
 35 }
 36 
 37 int creatmatrix(MGraph &G,Dgevalue &dgevalue)
 38 {//      
 39     int i,j,k;
 40     cout<<"           "<<endl;
 41     cin>>G.vexnum>>G.arcnum;
 42     
 43     for(i=0;i<G.vexnum;i++)//    
 44         cin>>G.vexs[i];
 45 
 46     for(i=0;i<G.vexnum;i++)
 47     {//        MAX
 48         for(j=0;j<G.vexnum;j++)
 49         {
 50             G.arcs[i][j].adj=MAX;
 51         }
 52     }
 53     cout<<"                "<<endl;
 54     for(k=0;k<G.arcnum;k++)
 55     {//           value
 56         cin>>dgevalue[k].start>>dgevalue[k].end>>dgevalue[k].value;
 57         i=locatevex(G,dgevalue[k].start);
 58         j=locatevex(G,dgevalue[k].end);
 59         G.arcs[i][j].adj=dgevalue[k].value;
 60         G.arcs[j][i].adj=G.arcs[i][j].adj;
 61     }
 62     return 0;
 63 }
 64 
 65 void sort(MGraph G,Dgevalue &dgevalue)
 66 {//    
 67     char p1,p2;
 68     int i,j,temp;
 69     for(i=0;i<G.arcnum;i++)
 70     {//    
 71         for(j=i;j<G.arcnum;j++)
 72         {
 73             if(dgevalue[i].value>dgevalue[j].value)
 74             {
 75                 temp=dgevalue[i].value;
 76                 dgevalue[i].value=dgevalue[j].value;
 77                 dgevalue[j].value=temp;
 78 
 79                 p1=dgevalue[i].start;
 80                 dgevalue[i].start=dgevalue[j].start;
 81                 dgevalue[j].start=p1;
 82 
 83                 p2=dgevalue[i].end;
 84                 dgevalue[i].end=dgevalue[j].end;
 85                 dgevalue[j].end=p2;
 86             }
 87         }
 88     }
 89 }
 90 
 91 void creatminitree_kruskal(MGraph G,Dgevalue &dgevalue)
 92 {//kruskal   
 93     int i,j,p[100];
 94     char pa,pb;
 95     for(i=0;i<G.vexnum;i++)
 96              p[i]=i;
 97 
 98     sort(G,dgevalue);
 99     cout<<endl;
100     for(i=0;i<G.arcnum;i++)
101     {
102         pa=p[locatevex(G,dgevalue[i].start)];
103         pb=p[locatevex(G,dgevalue[i].end)];
104 
105         if(pa!=pb)
106         {    //  a、b         
107             cout<<dgevalue[i].start<<" "<<dgevalue[i].end<<" "<<dgevalue[i].value<<endl;
108 
109         for(j=0;j<G.vexnum;j++)
110          {// a、b         
111             if(p[j]==pb)
112                 p[j]=pa;
113         
114          }
115         }
116     }
117 }
118 
119 int main()
120 {
121     char u;
122      MGraph G;
123      Dgevalue dgevalue;
124      creatmatrix(G,dgevalue);
125       cout<<" kruskal        ";
126       creatminitree_kruskal(G,dgevalue);
127 
128      return 0;
129 }