数据结构中图结构的最小生成树算法(普里姆算法)
最近有很久都没有露头了,主要是有很多的作业,而且马上就到了期末考试了,所以我没有什么时间来这里发布文章了。今天呢,把我以前写的图结构再次搬了上来。这次的图结构添加了广度优先遍历,和最小生成树的普里姆算法。现在我就把我程序中的普里姆算法贴出来,供大家参考。
- /*----------------------------------------------------------------------------
- 蒋轶民制作:E-mail:jiangcaiyang123@163.com
- ------------------------------------------------------------------------------
- 文件名:JGraph_MiniSpanTree.h
- ------------------------------------------------------------------------------
- 作用:最小生成树的生成
- ------------------------------------------------------------------------------
- 调用规范:无
- /*--------------------------------------------------------------------------*/
- // 条件编译
- #ifndef _JGRAPH_MINISPANTREE_H_
- #define _JGRAPH_MINISPANTREE_H_
- /*--------------------------------------------------------------------------*/
- // 返回顶点在图中的位置
- template <typename CustomType>
- int JMatrixGraph<CustomType>::LocateVex( CustomType u )
- {
- int i;
- for ( i = 0; i < vexnum; i++ )
- {
- if ( vexs[i] == u )
- return i;
- }
- return -1;
- }
- /*--------------------------------------------------------------------------*/
- // 输出最小边的下标
- template <typename CustomType>
- int JMatrixGraph<CustomType>::minimum( CloseEdge<CustomType>* closedge )
- {
- int i, track_i = -1;
- VRType lowestcost = INFINITY;
- for ( i = 0; i < vexnum; i++ )
- {
- if ( lowestcost > closedge[i].lowcost && closedge[i].lowcost > 0 )
- {
- lowestcost = closedge[i].lowcost;
- track_i = i;
- }
- }
- return track_i;
- }
- /*--------------------------------------------------------------------------*/
- // 普里姆算法求最小生成树
- template <typename CustomType>
- void JMatrixGraph<CustomType>::MiniSpanTree_PRIM( CustomType u )
- {
- CloseEdge<CustomType> closedge[MAX_VERTEX_NUM];
- int i, j, k;
- /*-------------------------------------*/
- #ifdef _JDEBUG_// 调试版本的
- cout<<"邻接矩阵为:/n";
- for ( i = 0; i < vexnum; i++ )
- {
- for ( j = 0; j < vexnum; j++ )
- {
- if ( arcs[i][j].adj == INFINITY )
- cout<<"∞ ";
- else cout<<arcs[i][j].adj<<" ";
- }
- cout<<'/n';
- }
- #endif
- /*-------------------------------------*/
- k = LocateVex( u );// 寻找u顶点在邻接矩阵的位置,并让其为k
- if ( k == -1 )
- {
- cout<<"调用LocateVex()函数失败。"<<'/n';
- return;
- }
- for ( j = 0; j < vexnum; j++ )
- {
- if ( j != k )
- {
- closedge[j].adjvex = u;
- closedge[j].lowcost = arcs[k][j].adj;
- }
- }
- /*-------------------------------------*/
- #ifdef _JDEBUG_// 调试版本的
- cout<<"遍历最短边结构体的集合:/n";
- for ( i = 0; i < vexnum; i++ )
- {
- cout<<i+1<<'/n';
- cout<<"adjvex:"<<closedge[i].adjvex<<'/n';
- cout<<"lowcost:"<<closedge[i].lowcost<<'/n';
- }
- #endif
- /*-------------------------------------*/
- closedge[k].lowcost = 0;// 初始化,U = { u }
- for ( i = 1; i < vexnum; i++ )
- {
- k = minimum( closedge );
- if ( k == -1 )
- {
- cout<<"输出最小边的下标(调用minimum()函数)失败。/n";
- return;
- }
- cout<<closedge[k].adjvex<<"→"<<vexs[k]<<' ';
- closedge[k].lowcost = 0;
- for ( j = 0; j < vexnum; j++ )
- {
- if ( arcs[k][j].adj < closedge[j].lowcost )
- {
- closedge[j].adjvex = vexs[k];
- closedge[j].lowcost = arcs[k][j].adj;
- }
- }
- }
- cout<<'/n';
- }
- /*--------------------------------------------------------------------------*/
- #endif
这是我的图结构的主结构。在这里我定义了一个图结构类,并把实现的细节都分散在各个文件中。由于篇幅的原因,就没有列出来了。
- /*----------------------------------------------------------------------------
- 蒋轶民制作:E-mail:jiangcaiyang123@163.com
- ------------------------------------------------------------------------------
- 文件名:JGraph.h
- ------------------------------------------------------------------------------
- 作用:这是使用邻接矩阵制作的图状结构,基本实现了图的创建操作、深度优先搜索和广
- 度优先搜索。
- ------------------------------------------------------------------------------
- 调用规范:
- /*--------------------------------------------------------------------------*/
- // 条件编译
- #ifndef _JGRAPH_H_
- #define _JGRAPH_H_
- /*--------------------------------------------------------------------------*/
- // 头文件
- #include <iostream>
- #include <limits.h>
- using namespace std;
- // 定义的宏
- #define INFINITY INT_MAX
- #define MAX_VERTEX_NUM 20
- /*--------------------------------------------------------------------------*/
- // 定义一系列类型
- enum GraphKind { DG, DN, UDG, UDN };// 图的类型枚举
- typedef unsigned int VRType;
- typedef char InfoType;
- typedef struct
- {
- VRType adj;// 顶点关系类型
- InfoType* info;// 弧的信息
- } AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
- // 求最短路径的辅助结构体
- template <typename CustomType>
- struct CloseEdge
- {
- CustomType adjvex;
- VRType lowcost;// 顶点关系类型
- };
- // 图的定义
- template <typename CustomType>
- class JMatrixGraph
- {
- public:
- JMatrixGraph():vexnum(0),arcnum(0){}// 默认构造函数
- void CreateGraph( GraphKind inputKind );//创建图
- void DFSTraverse( bool (*Visit)(int v) );// 深度优先搜索遍历
- void BFSTraverse( bool (*Visit)(int v) );// 广度优先搜索遍历
- int GetVertexNum( void ){ return vexnum; };//返回顶点个数
- int GetArcNum( void ){ return arcnum; }//返回弧的个数
- CustomType Getvexs( int i ){ return vexs[i]; }// 返回顶点信息
- void SearchNonZeroInMatrix( int& v, int& w );// 从当前下标开始以下三角(◣)方式查找下一个非零矩阵元素
- void MiniSpanTree_PRIM( CustomType u );// 普里姆算法求最小生成树
- /*--------------------------------------*/
- // 临时用来测试输出的示例图结构
- #ifdef _JDEBUG_
- #include "JGraph/JGraph_Debug.h"
- #endif
- /*--------------------------------------*/
- private:
- void CreateDG( void );// 创建有向图
- void CreateDN( void );// 创建有向网
- void CreateUDG( void );// 创建无向图
- void CreateUDN( void );// 创建无向网
- void DepthFirstSearch( int v, bool (*Visit)(int v) );// 深度优先搜索
- int FirstAdjVex( int v );// 返回第v个顶点的第一个邻接点
- int NextAdjVex( int v, int w );// 返回第v个顶点的下一个邻接点
- int LocateVex( CustomType u );// 寻找u顶点在邻接矩阵的位置
- int minimum( CloseEdge<CustomType>* closedge );// 在CloseEdge结构体中寻找最短的边
- CustomType vexs[MAX_VERTEX_NUM];// 顶点向量
- AdjMatrix arcs;// 邻接矩阵
- int vexnum, arcnum;// 图的顶点数和弧数
- GraphKind kind;// 图的种类标志
- bool visited[MAX_VERTEX_NUM];// 访问标志数组
- };
- /*--------------------------------------------------------------------------*/
- // 图各种操作的实现
- #include "JGraph/JGraph_CreateGraph.h"
- #include "JGraph/JGraph_Traverse.h"
- #include "JGraph/JGraph_MiniSpanTree.h"
- #include "JGraph/JGraph_Direct2DGraph.h"
- /*--------------------------------------------------------------------------*/
- #endif
程序的截图是:
这是定义了_JDEBUG_的,能显示更多的信息,大家也可以不定义_JDEBUG_,这样就只显示最短路径的信息了。
如果大家想得到所有源码的话,这里有下载:http://download.csdn.net/source/2914075
我还是希望能够把数据结构的图的所有操作做完。这样我也算是完成了一个任务了。