数据结构中图结构的最小生成树算法（普里姆算法）

数据结构中图结构的最小生成树算法（普里姆算法）
 最近有很久都没有露头了，主要是有很多的作业，而且马上就到了期末考试了，所以我没有什么时间来这里发布文章了。今天呢，把我以前写的图结构再次搬了上来。这次的图结构添加了广度优先遍历，和最小生成树的普里姆算法。现在我就把我程序中的普里姆算法贴出来，供大家参考。

Code:

1. /*----------------------------------------------------------------------------  
2. 蒋轶民制作：E-mail：[e-mail]  
3. ------------------------------------------------------------------------------  
4. 文件名：JGraph_MiniSpanTree.h  
5. ------------------------------------------------------------------------------  
6. 作用：最小生成树的生成  
7. ------------------------------------------------------------------------------  
8. 调用规范：无  
9. /*--------------------------------------------------------------------------*/  
10. // 条件编译   
11. #ifndef _JGRAPH_MINISPANTREE_H_   
12. #define _JGRAPH_MINISPANTREE_H_   
13. /*--------------------------------------------------------------------------*/  
14. // 返回顶点在图中的位置   
15. template <typename CustomType>   
16. int JMatrixGraph<CustomType>::LocateVex( CustomType u )   
17. {   
18.  int i;   
19.  for ( i = 0; i < vexnum; i++ )   
20.  {   
21.   if ( vexs[i] == u )   
22.    return i;   
23.  }   
24.  return -1;   
25. }   
26. /*--------------------------------------------------------------------------*/  
27. // 输出最小边的下标   
28. template <typename CustomType>   
29. int JMatrixGraph<CustomType>::minimum( CloseEdge<CustomType>* closedge )   
30. {   
31.  int i, track_i = -1;   
32.  VRType lowestcost = INFINITY;   
33.  for ( i = 0; i < vexnum; i++ )   
34.  {   
35.   if ( lowestcost > closedge[i].lowcost && closedge[i].lowcost > 0 )   
36.   {   
37.    lowestcost = closedge[i].lowcost;   
38.    track_i = i;   
39.   }   
40.  }   
41.  return track_i;   
42. }   
43. /*--------------------------------------------------------------------------*/  
44. // 普里姆算法求最小生成树   
45. template <typename CustomType>   
46. void JMatrixGraph<CustomType>::MiniSpanTree_PRIM( CustomType u )   
47. {   
48.  CloseEdge<CustomType> closedge[MAX_VERTEX_NUM];   
49.  int i, j, k;   
50.  /*-------------------------------------*/  
51. #ifdef _JDEBUG_// 调试版本的   
52.  cout<<"邻接矩阵为：/n";   
53.  for ( i = 0; i < vexnum; i++ )   
54.  {   
55.   for ( j = 0; j < vexnum; j++ )   
56.   {   
57.    if ( arcs[i][j].adj == INFINITY )   
58.     cout<<"∞ ";   
59.    else cout<<arcs[i][j].adj<<"  ";   
60.   }   
61.   cout<<'/n';   
62.  }   
63. #endif   
64.  /*-------------------------------------*/  
65.  k = LocateVex( u );// 寻找u顶点在邻接矩阵的位置，并让其为k   
66.  if ( k == -1 )   
67.  {   
68.   cout<<"调用LocateVex()函数失败。"<<'/n';   
69.   return;   
70.  }   
71.  for ( j = 0; j < vexnum; j++ )   
72.  {   
73.   if ( j != k )   
74.   {   
75.    closedge[j].adjvex = u;   
76.    closedge[j].lowcost = arcs[k][j].adj;   
77.   }   
78.  }   
79.  /*-------------------------------------*/  
80. #ifdef _JDEBUG_// 调试版本的   
81.  cout<<"遍历最短边结构体的集合：/n";   
82.  for ( i = 0; i < vexnum; i++ )   
83.  {   
84.   cout<<i+1<<'/n';   
85.   cout<<"adjvex："<<closedge[i].adjvex<<'/n';   
86.   cout<<"lowcost："<<closedge[i].lowcost<<'/n';   
87.  }   
88. #endif   
89.  /*-------------------------------------*/  
90.  closedge[k].lowcost = 0;// 初始化，U = { u }   
91.  for ( i = 1; i < vexnum; i++ )   
92.  {   
93.   k = minimum( closedge );   
94.   if ( k == -1 )   
95.   {   
96.    cout<<"输出最小边的下标（调用minimum()函数）失败。/n";   
97.    return;   
98.   }   
99.   cout<<closedge[k].adjvex<<"→"<<vexs[k]<<' ';   
100.   closedge[k].lowcost = 0;   
101.   for ( j = 0; j < vexnum; j++ )   
102.   {   
103.    if ( arcs[k][j].adj < closedge[j].lowcost )   
104.    {   
105.     closedge[j].adjvex = vexs[k];   
106.     closedge[j].lowcost = arcs[k][j].adj;   
107.    }   
108.   }   
109.  }   
110.  cout<<'/n';   
111. }   
112. /*--------------------------------------------------------------------------*/  
113. #endif  

 这是我的图结构的主结构。在这里我定义了一个图结构类，并把实现的细节都分散在各个文件中。由于篇幅的原因，就没有列出来了。

Code:

1. /*----------------------------------------------------------------------------  
2. 蒋轶民制作：E-mail：[e-mail]  
3. ------------------------------------------------------------------------------  
4. 文件名：JGraph.h  
5. ------------------------------------------------------------------------------  
6. 作用：这是使用邻接矩阵制作的图状结构，基本实现了图的创建操作、深度优先搜索和广  
7. 度优先搜索。  
8. ------------------------------------------------------------------------------  
9. 调用规范：  
10. /*--------------------------------------------------------------------------*/  
11. // 条件编译   
12. #ifndef _JGRAPH_H_   
13. #define _JGRAPH_H_   
14. /*--------------------------------------------------------------------------*/  
15. // 头文件   
16. #include <iostream>   
17. #include <limits.h>   
18.   
19. using namespace std;   
20.   
21. // 定义的宏   
22. #define INFINITY  INT_MAX   
23. #define MAX_VERTEX_NUM 20   
24.   
25. /*--------------------------------------------------------------------------*/  
26. // 定义一系列类型   
27. enum GraphKind { DG, DN, UDG, UDN };// 图的类型枚举   
28. typedef unsigned int VRType;   
29. typedef char InfoType;   
30. typedef struct  
31. {   
32.  VRType adj;// 顶点关系类型   
33.  InfoType* info;// 弧的信息   
34. } AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   
35.   
36. // 求最短路径的辅助结构体   
37. template <typename CustomType>   
38. struct CloseEdge   
39. {   
40.  CustomType adjvex;   
41.  VRType lowcost;// 顶点关系类型   
42. };   
43.   
44. // 图的定义   
45. template <typename CustomType>   
46. class JMatrixGraph   
47. {   
48. public:   
49.  JMatrixGraph():vexnum(0),arcnum(0){}// 默认构造函数   
50.  void CreateGraph( GraphKind inputKind );//创建图   
51.  void DFSTraverse( bool (*Visit)(int v) );// 深度优先搜索遍历   
52.  void BFSTraverse( bool (*Visit)(int v) );// 广度优先搜索遍历   
53.  int GetVertexNum( void ){ return vexnum; };//返回顶点个数   
54.  int GetArcNum( void ){ return arcnum; }//返回弧的个数   
55.  CustomType Getvexs( int i ){ return vexs[i]; }// 返回顶点信息   
56.  void SearchNonZeroInMatrix( int& v, int& w );// 从当前下标开始以下三角（◣）方式查找下一个非零矩阵元素   
57.  void MiniSpanTree_PRIM( CustomType u );// 普里姆算法求最小生成树   
58.  /*--------------------------------------*/  
59.  // 临时用来测试输出的示例图结构   
60. #ifdef _JDEBUG_   
61. #include "JGraph/JGraph_Debug.h"   
62. #endif   
63.  /*--------------------------------------*/  
64. private:   
65.  void CreateDG( void );// 创建有向图   
66.  void CreateDN( void );// 创建有向网   
67.  void CreateUDG( void );// 创建无向图   
68.  void CreateUDN( void );// 创建无向网   
69.  void DepthFirstSearch( int v, bool (*Visit)(int v) );// 深度优先搜索   
70.  int FirstAdjVex( int v );// 返回第v个顶点的第一个邻接点   
71.  int NextAdjVex( int v, int w );// 返回第v个顶点的下一个邻接点   
72.  int LocateVex( CustomType u );// 寻找u顶点在邻接矩阵的位置   
73.  int minimum( CloseEdge<CustomType>* closedge );// 在CloseEdge结构体中寻找最短的边   
74.   
75.  CustomType vexs[MAX_VERTEX_NUM];// 顶点向量   
76.  AdjMatrix arcs;// 邻接矩阵   
77.  int vexnum, arcnum;// 图的顶点数和弧数   
78.  GraphKind kind;// 图的种类标志   
79.  bool visited[MAX_VERTEX_NUM];// 访问标志数组   
80. };   
81. /*--------------------------------------------------------------------------*/  
82. // 图各种操作的实现   
83. #include "JGraph/JGraph_CreateGraph.h"   
84. #include "JGraph/JGraph_Traverse.h"   
85. #include "JGraph/JGraph_MiniSpanTree.h"   
86. #include "JGraph/JGraph_Direct2DGraph.h"   
87. /*--------------------------------------------------------------------------*/  
88. #endif  

 

程序的截图是：
 这是定义了_JDEBUG_的，能显示更多的信息，大家也可以不定义_JDEBUG_，这样就只显示最短路径的信息了。

如果大家想得到所有源码的话，这里有下载：http://download.csdn.net/source/2914075 

我还是希望能够把数据结构的图的所有操作做完。这样我也算是完成了一个任务了。