数据结构图之二（最小生成树--普里姆算法）

  1 #include <iostream>
  2 #include "SeqList.h"
  3 #include <iomanip>
  4 using namespace std;
  5 
  6 #define  INFINITY  65535
  7 
  8 template<class NameType, class DistType>
  9 class Graph
 10 {
 11 private:
 12     SeqList<NameType> Vertices;
 13     DistType **Edges;
 14     int nVer, nEdges;
 15 
 16 public:
 17     Graph() 
 18         : Edges(NULL)
 19         , nEdges(0)
 20         , nVer(0)
 21     {}
 22     ~Graph()
 23     {}
 24 
 25 public:
 26 
 27     istream & operator>>(istream &in)
 28     {
 29         int v, u, value;
 30         int i, j;
 31         NameType item;
 32         cout << "请输入顶点的个数: " << endl;
 33         in >> nVer;
 34         cout << "请输入顶点的数据信息: " << endl;
 35         for (i = 0; i < nVer; ++i)
 36         {
 37             in >> item;
 38             Vertices.push_back(item);    // 保存全部顶点
 39         }
 40         /////二维数组的创建并初始化
 41         Edges = new DistType*[nVer]; // DistType *ar[10];
 42         for (i = 0; i < nVer; ++i)
 43         {
 44             Edges[i] = new DistType[nVer];
 45             for (j = 0; j < nVer; ++j)
 46             {
 47                 Edges[i][j] = 0;
 48             }
 49         }
 50         cout << "请输入边的个数: " << endl;
 51         in >> nEdges;
 52         cout << "请输入边的信息：" << endl;
 53         for (i = 0; i < nEdges; ++i)
 54         {
 55             in >> v >> u >> value;
 56             Edges[v][u] = value;
 57             Edges[u][v] = value;
 58         }
 59         return in;
 60     }
 61     ostream & operator<<(ostream &out) const
 62     {
 63         int i, j;
 64         out << "顶点信息 " << endl;
 65         for (i = 1; i <= nVer; ++i)
 66         {
 67             out << Vertices[i] << setw(5);
 68         }
 69         out << endl;
 70         out << "矩阵信息：" << endl;
 71         out << setw(10);
 72         for (i = 1; i <= nVer; ++i)
 73         {
 74             out << Vertices[i] << setw(5);
 75         }
 76         out << endl;
 77         for (i = 0; i < nVer; ++i)
 78         {
 79             out << Vertices[i+1] << setw(5);
 80             for (j = 0; j < nVer; ++j)
 81             {
 82                 if (0 == Edges[i][j] && i != j)
 83                     Edges[i][j] = INFINITY;
 84                 cout << Edges[i][j] << setw(5);
 85             }
 86             out << endl;
 87         }
 88         out << endl;
 89 
 90         return out;
 91     }
 92     //  图采用邻接矩阵存储  最小生成树 普里姆算法
 93     void MiniSpanTree()  
 94     {  
 95         int min = 0, i = 0, j = 0, k = 0;
 96         int* adjvex = new  int[nVer];    // 保存相关顶点下标  
 97         int* lowcost = new int[nVer];    // 保存相关顶点间边的权值  
 98         lowcost[0] = 0;         // 初始化第一个权值为0，即V0已加入生成树
 99         //lowcost的值为0，在这里就是此下标的顶点已经加入生成树    
100         adjvex[0] = 0;          // 初始化第一个顶点下标为0  
101 
102         for (i = 1; i < nVer; ++i)  //循环除过下标为0外的全部顶点
103         {  
104             lowcost[i] = Edges[0][i];  // 将v0顶点与之有边的权值存入数组 
105             adjvex[i] = 0;             // 并初始化都为v0的下标
106         }  
107 
108         for (i = 1; i < nVer; ++i) 
109         {  
110             min = INFINITY;  // 初始化最小权值为常数，通常设置为不可能到达的数值
111             k = 0;    // 复位
112 
113             for (j = 1; j < nVer; ++j)  
114             {  
115                 // 如果两个顶点之间存在边有权值，不为0并且小于min  
116                 if (lowcost[j] != 0 && lowcost[j] < min)  
117                 {  
118                     min = lowcost[j];  // 缓存最小值
119                     k = j;    // 将当前最小值的下标缓存入k
120                 }
121             }  
122             cout << "("<< adjvex[k] << "," << k << ")" << endl;   //打印当前顶点边中权值最小的边  
123             lowcost[k] = 0;                     // 将当前顶点的权值设为0，表示此顶点已经完成任务  
124 
125             for (j = 1; j < nVer; ++j)  // 循环所有节点
126             {  
127                 if (lowcost[j] != 0 && Edges[k][j] < lowcost[j])  
128                 {  // 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
129                     lowcost[j] = Edges[k][j]; // 用较小者替换  
130                     adjvex[j] = k;  // 将下标为k的顶点存入adjvex
131                 }  
132             }  
133         }
134 
135         delete []adjvex;
136         delete []lowcost;
137         adjvex = NULL;
138         lowcost = NULL;
139     }
140 };
141 
142 template<class NameType, class DistType>
143 istream & operator>>(istream &in, Graph<NameType,DistType> &g)
144 {
145     g >> in;
146     return in;
147 }
148 
149 template<class NameType, class DistType>
150 ostream & operator<<(ostream &out, const Graph<NameType,DistType> &g)
151 {
152     g << out;
153     return out;
154 }
155 
156 void main()
157 {
158     Graph<char, int> myg;
159     cin >> myg;
160     cout << "打印所有输入信息：" << endl;
161     cout << myg << endl;
162     cout << "最小生成树边信息如下：" << endl;
163     myg.MiniSpanTree();
164     cout << endl;
165 }