(C/C++)-最小生成树算法(Prim&Kruskal)和单源最短路径算法(Dijkstra)

落日映苍穹つ 2022-12-27 15:29 90阅读 0赞

## (C/C++)-最小生成树算法(Prim&Kruskal)和单源最短路径算法(Dijkstra) ##

### 1、什么是最小生成树 ###

对于一个带权连通无向图G=(V,E)，图G的不同的生成树，其所对应的生成树的权值可能不同。设R是G所有生成树的集合，T是R中权值最小的那棵生成树，则称**T为G的最小生成树**

**最小生成树的性质**

*  最小生成树可能不唯一，但其对应的边的权值之和总是唯一的，且是最小的；
 *  最小生成树的边数为顶点数-1；

--------------------

### 2、Prim算法的实现(选点) ###

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合  
用辅助集合s，来描述被选中的顶点

**思路：**

*  首先将第一个顶点放入集合s中，即s=\{1\}；
 *  做如下贪心选择，**当s是v的真子集时**，选取i属于s，j属于V-S，且c\[i\]\[j\]是最小的边，并将顶点j加入到集合s中；
 *  当S=V时选取结束，此时就生成了一棵最小生成树；

如图所示，描述了Prim算法选取顶点的过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]  
具体实现过程：

void prim(int c[N][N], int n)
    {
        
    	int lowcost[N];//存储非集合s顶点到集合s中顶点最小边的权值
    	int closest[N];//存储非集合s顶点到集合s中权值最小边的顶点
    	int s[N];
    
    	s[1] = 1;
    	printf("1 ");
    
    	//lowcost[]和closest[]的初始化
    	for (int i = 2; i < N; i++)
    	{
        
    		closest[i] = 1;
    		lowcost[i] = c[1][i];
    		s[i] = 0;
    	}
    
    	//每次循环箱集合s中添加一个顶点
    	for (int i = 2; i < N; i++)
    	{
        
    		int min = maxint;
    		int temp = 1;//用来记录选择的顶点
    
    		//做贪心选择，选择非集合s中顶点到s中顶点最小的权值边的顶点
    		for (int j = 2; j < N; j++)
    			if (!s[j] && min > lowcost[j])
    			{
        
    				//更新值,并记录
    				min = lowcost[j];
    				temp = j;
    			}
    
    		s[temp] = 1;//顶点加入到集合s
    		printf("%d ", temp);
    
    		//更新lowcost[]和closest[]
    		for(int j=2;j<N;j++)
    			if (!s[j] && lowcost[j] > c[j][temp])
    			{
        
    				lowcost[j] = c[j][temp];
    				closest[j] = temp;
    			}
    	}
    }

在main()函数中测试一下Prim算法：

int main()
    {
        
    	int c[N][N] = {
        //0号下标不用
    		{
        maxint,maxint,maxint,maxint,maxint,maxint,maxint},//0
    		{
        maxint,maxint,6,1,5,maxint,maxint},//1
    		{
        maxint,6,maxint,5,maxint,3,maxint},//2
    		{
        maxint,1,5,maxint,5,6,4},//3
    		{
        maxint,5,maxint,5,maxint,maxint,2},//4
    		{
        maxint,maxint,3,6,maxint,maxint,6},//5
    		{
        maxint,maxint,maxint,4,2,6,maxint}//6
    	};
    
    	printf("Prim点选取顺序为:\n");
    	prim(c, N);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 1]

--------------------

### 3、Kruskal算法的实现(选边) ###

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合

采用Kruskal算法时，采用了**并查集作为辅助的数据结构**  
并查集中两个重要的实现函数：

*  int find\_root(int x)：查找以结点x的根结点；
 *  int union\_set(int x,int y):合并x，y所在的两个子集，若两个子集存在回路返回0，不存在回路返回1；

思路：

*  将图G的边集按照权值大大小升序排列
 *  每次选取未被选取过，且权值最小的边，若选取该边构成回路，则舍弃该边，选择下一条权值最小的边；
 *  直到图G所有的顶点在一个连通分量上；

如图所示，描述了Kruskal算法选取顶点的过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 2]  
具体实现过程：

**边的结构体**

typedef struct edge
    {
        
    	int x;
    	int y;
    	int weight;
    	char name;
    	int selected;
    }Edge;

并查集的函数

int parent[N];//记录顶点的父结点
    int rank[N];//记录以顶点为根的树的深度(压缩路径)
    
    //初始化parent[]和rank[]
    void init()
    {
        
    	for (int i = 1; i < N; i++)
    	{
        
    		parent[i] = -1;//初始时，每个顶点的父结点默认为-1
    		rank[i] = 1;
    	}
    }
    
    //查找顶点x的根结点
    int find_root(int x)
    {
        
    	int x_root = x;
    	while (parent[x_root] != -1)
    		x_root = parent[x_root];
    	return x_root;
    }
    
    //合并两个顶点所在的子集，合并成功返回1，失败返回0
    int union_set(int i, int j)
    {
        
    	int i_root = find_root(i);
    	int j_root = find_root(j);
    
    	if (i_root == j_root)
    		return 0;//i,j在同一个子集中，合并失败
    
    	//i,j不在同一个子集中，合并两个子集
    	if (rank[i_root] > rank[j_root])
    		parent[j_root] = i_root;
    	else if (rank[i_root] < rank[j_root])
    		parent[i_root] = parent[j_root];
    	else
    	{
        
    		//i,j深度相同的情况下
    		parent[i_root] = j_root;
    		rank[j_root]++;
    	}
    	return 1;
    }

**Kruskal实现**

//n是边的个数
    void kruskal(Edge e[], int n)
    {
        
    	init();
    	qsort(e, 11, sizeof(e[1]), cmp);//升序
    
    	for (int i = 1; i <= n; i++)
    	{
        
    		int x = find_root(e[i].x);
    		int y = find_root(e[i].y);
    
    		if (x != y)
    		{
        
    			//无回路，选中此边
    			e[i].selected = 1;
    			union_set(e[i].x, e[i].y);
    			printf("%c ", e[i].name);
    		}
    	}
    	/*
    	for (int i = 1; i <= n; i++)
    		if (e[i].selected)
    			printf("%c ", e[i].name);*/
    }

测试函数

int main()
    {
        
    	Edge e[11] = {
        //10条边
    		{
        0},//此条数据不用
    		{
        1,4,5,'a',0},{
        4,6,2,'b',0},{
        6,5,6,'c',0},{
        5,2,3,'d',0},{
        2,1,6,'e',0},
    		{
        1,3,1,'f',0},{
        3,4,5,'g',0},{
        3,6,4,'h',0},{
        3,5,6,'i',0},{
        3,2,5,'j',0}
    	};
    
    	int n = 10;
    
    	kruskal(e, n);
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 3]

--------------------

### 4、Dijkstra算法的实现(选点) ###

图G=(V,E)，其中V为所有结点的集合，E为图G的边的集合

采用辅助数组dist\[i\]，来存储从源点到i的最短距离

**思路：**

*  从集合V-S中选取顶点j，满足dist\[j\]=min\{dist\[i\]|i属于V-S\}，并将顶点j加入到集合s中
 *  集合s扩充后，修改源点出发到V-S上任一顶点k的最短路径，**dist\[j\]+c\[j\]\[k\]<dist\[k\]**(这里是Dijkstra区别于Prim的最重要一点)
 *  重复上述步骤，知道所有顶点都在集合S中

如图示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 4]  
具体实现：

//dist[i]存储从源点到i的最短路径
    void dijkstra(int c[][N], int dist[], int start)
    {
        
    	int s[N];
    
    	//初始化参数
    	for (int i = 1; i < N; i++)
    	{
        
    		dist[i] = c[start][i];
    		s[i] = 0;
    	}
    	s[start] = 1;
    
    	//每次循环箱集合s中添加一个顶点
    	for (int i = 2; i < N; i++)
    	{
        
    		int tmp = maxint;
    		int u = start;
    
    		//做贪心选择，选择非集合s中顶点到源点最小的权值边的顶点
    		for (int j = 1; j < N; j++)
    		{
        
    			if (!s[j] && dist[j] < tmp)
    			{
        
    				//记录
    				u = j;
    				tmp = dist[j];
    			}
    		}
    
    		s[u] = 1;
    
    		//更新dist[]的值
    		for (int j = 1; j < N; j++)
    			if (!s[j] && (dist[u] + c[u][j] < dist[j]))
    				dist[j] = dist[u] + c[u][j];
    
    	}
    }

main函数中的测试：

int main()
    {
        
    	int c[N][N] = {
        
    		{
        0},//0号下标不使用
    		{
        0,0,10,maxint,maxint,5},
    		{
        0,maxint,0,1,maxint,2},
    		{
        0,maxint,maxint,0,4,maxint},
    		{
        0,7,maxint,6,0,maxint},
    		{
        0,maxint,3,9,2,0}
    	};//5个顶点,0号下标不使用
    
    	int dist[N], start = 1;
    
    	dijkstra(c, dist, start);
    
    	for (int i = 1; i < N; i++)
    		printf("dist[%d]=%d\t", i, dist[i]);
    	printf("\n");
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 5]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70]: /images/20221120/caba9b5213074982925c026d6766b24c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 1]: /images/20221120/31b9b0682cd84f898efddeb84c446d99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 2]: /images/20221120/6013afa1477642198ddfe28c211fdf37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 3]: /images/20221120/10d784ad9d3d490fb8bda63f06c410a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 4]: /images/20221120/fa3c5bd9a0d149219267b15df7104832.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dybG92ZXNtaWxl_size_16_color_FFFFFF_t_70 5]: /images/20221120/2847a8f320fb403a9d3e90a1e7e87db5.png