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

데이터 구 조 는 prim 알고리즘 으로 최소 생 성 트 리 를 요구 합 니 다.
  먼저 prim 알고리즘 사상, 즉 그물 모양 그림 N = (V, {E}) 에서 M 이 그림 N 의 최소 생 성 트 리 변 의 집합 이 라 고 가정 해 야 합 니 다.U 와 V 두 개의 점 집합 이 설치 되 어 있 습 니 다. U = {u0} (u0 * 8712 ° V), M = {} 부터 순환 작업 에 들 어 갑 니 다. 점 집합 U 에서 점 집합 V - U 까지 대가 가 가장 작은 변 (u0, v0) u0 * 8712 ° U, v0 * 8712 ° V - U 를 찾 아 변 집합 M 에 병합 하고 v0 도 점 집합 U 에 합 쳐 U = V 까지 합 니 다.이때 M 은 n - 1 개의 변 (n 개의 정점 이 있다 고 가정) 이 있어 야 합 니 다. min = (U, {M}) 은 N 의 최소 생 성 트 리 입 니 다.
  이 알고리즘 은 최소 생 성 트 리 의 MST 성질 을 사 용 했 습 니 다. N = (V, {E}) 은 연결 망 이 고 U 는 점 집합 V 의 비 빈 부분 집합 이 라 고 가정 합 니 다.(u, v) 가 최소 값 변 이 라면 u * 8712 ° U, v * 8712 ° V 는 변 (u, v) 을 포함 하 는 최소 생 성 트 리 가 존재 합 니 다.
  다음은 원본 코드 를 드 립 니 다.

  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 Pnode
 20 {//      U V         
 21     char adjvex;
 22     int lowcost;
 23 }closedge[100];
 24 
 25  typedef struct Node
 26 {//                       
 27     char start;
 28     char end;
 29     double value;
 30 }Node,Dgevalue[100];
 31 
 32 int locatevex(MGraph G,char ch)
 33 {//      ch      
 34     int k;
 35     for(int i=0;i<G.vexnum;i++)
 36     {
 37         if(G.vexs[i]==ch)
 38             k=i;
 39     }
 40     return k;
 41 }
 42 
 43 int creatmatrix(MGraph &G,Dgevalue &dgevalue)
 44 {//      
 45     int i,j,k;
 46     cout<<"           "<<endl;
 47     cin>>G.vexnum>>G.arcnum;
 48     
 49     for(i=0;i<G.vexnum;i++)//    
 50         cin>>G.vexs[i];
 51 
 52     for(i=0;i<G.vexnum;i++)
 53     {//        MAX
 54         for(j=0;j<G.vexnum;j++)
 55         {
 56             G.arcs[i][j].adj=MAX;
 57         }
 58     }
 59     cout<<"                "<<endl;
 60     for(k=0;k<G.arcnum;k++)
 61     {//           value
 62         cin>>dgevalue[k].start>>dgevalue[k].end>>dgevalue[k].value;
 63         i=locatevex(G,dgevalue[k].start);
 64         j=locatevex(G,dgevalue[k].end);
 65         G.arcs[i][j].adj=dgevalue[k].value;
 66         G.arcs[j][i].adj=G.arcs[i][j].adj;
 67     }
 68     return 0;
 69 }
 70 
 71 
 72 int minum(MGraph G,closedge close)
 73 {// U V      
 74         int i,j,k=1000;
 75         for(i=0;i<G.vexnum;i++)
 76         {
 77             if(close[i].lowcost!=0&&close[i].lowcost<k)
 78                 {
 79                     k=close[i].lowcost;    
 80                      j=i;
 81                 }
 82         }
 83         return j;
 84 }
 85 
 86 void creatminitree_prim(MGraph G,char u)
 87 {// prim    u     ，       ,    
 88         int i,j,k;
 89         closedge close;
 90 
 91         k=locatevex(G,u);
 92         for(i=0;i<G.vexnum;i++)
 93         {
 94             if(i!=k)//   close[].adjvex  u
 95             {
 96                 close[i].adjvex=u;
 97                 close[i].lowcost=G.arcs[k][i].adj;
 98             }
 99         }
100         close[k].lowcost=0;
101 
102         
103 
104         for(j=1;j<G.vexnum;j++)
105         {
106             k=minum(G,close);
107             cout<<close[k].adjvex<<","<<G.vexs[k]<<" "<<close[k].lowcost<<endl;
108             
109             close[k].lowcost=0;// k    U
110             for(i=0;i<G.vexnum;i++)
111             {// k  U ，         U V        ，    
112                 if(G.arcs[k][i].adj<close[i].lowcost)
113                 {
114                     close[i].lowcost=G.arcs[k][i].adj;
115                     close[i].adjvex=G.vexs[k];
116                 }
117             }
118     }
119 }
120 
121 int main()
122 {//     
123     char u;
124      MGraph G;
125      Dgevalue dgevalue;
126      creatmatrix(G,dgevalue);
127      cout<<" prim        "<<endl;
128     cout<<"     " <<endl;
129      cin>>u;
130      creatminitree_prim(G,u);
131     
132 
133      return 0;
134 }

 
처음 쓰 는 글, 좋 은 시작 되 길 바래, cheer up ~!    2012-12-09