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

时间:2022-04-29 13:24:43

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

Code:
  1. /*----------------------------------------------------------------------------  
  2. 蒋轶民制作:E-mail:jiangcaiyang123@163.com  
  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:jiangcaiyang123@163.com  
  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 

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