图之最小生成树Kruskal算法详解（C语言版）-Toy模板网

这篇具有很好参考价值的文章主要介绍了图之最小生成树Kruskal算法详解（C语言版）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、Kruskal算法思想

Kruskal算法（克鲁斯卡尔算法）查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。

举个例子，下图是一个连通网有A、B、C、D、E、F六个顶点，它们的编号依次是0、1、2、3、4、5。使用克鲁斯卡尔算法查找最小生成树的过程如下所示，代价分别为1，2，3，4的 4 条边由于满足上述条件，则先后被加入到组成最小生成树的边中，代价为5的两条边(A，D)和(C，D)被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入最小生成树的边中,则会使最小生成树产生回路，而下一条代价等于5的最小边(B，C)联结两个连通分量，则可加入组成最小生成树的边中。由此，构造成一棵最小生成树。

每当添加一条边<i，j>作为最小生成树的边时，都需要根据father数组判断一下，这条边加入后是否会造成环路，如果不会造成环路就将该边加入到father数组中，进行标记（father[顶点j的最终父顶点] = 顶点i的最终父顶点）。其中father数组判断是否形成环路的方式是：分别将构成边的两个顶点i、j，放到father数组中查找，查找两个顶点的最终父顶点，如果两者的父顶点相同则说明加入后会形成环，如果不同就不会形成环。
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论
将各个边按权值升序排列，并根据图结构初始化father数组father[i] = i（即顶点的父顶点是自己）

father[0] = 0
father[1] = 1
father[2] = 2
father[3] = 3
father[4] = 4
father[5] = 5

取出第 1 条边<A，C>，将A、C两个顶点的编号 i = 0，j = 2放到father数组查找它们的父顶点编号，查找到的编号分别是0、2对应顶点A、C，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[2] = 0）
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 4
father[5] = 5

取出第 2 条边<D，F>，将D、F两个顶点的编号 i = 3，j = 5放到father数组查找它们的父顶点编号，查找到的编号分别是3、5对应顶点D、F，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[5] = 3）
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 4
father[5] = 3

取出第 3 条边<B，E>，将B、E两个顶点的编号 i = 1，j = 4放到father数组查找它们的父顶点编号，查找到的编号分别是1、4对应顶点B、E，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[4] = 1）
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 3
father[4] = 1
father[5] = 3

取出第 4 条边<C，F>，将C、F两个顶点的编号 i = 2，j = 5放到father数组查找它们的父顶点编号，查找到的编号分别是0、3对应顶点A、D，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[3] = 0）
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

father[0] = 0
father[1] = 1
father[2] = 0
father[3] = 0
father[4] = 1
father[5] = 3

取出第 5 条边<A，D>，将A、D两个顶点的编号 i = 0，j = 3放到father数组查找它们的父顶点编号，查找到的编号分别是0、0对应顶点A、A，两个父顶点相同，则说明这条边加入后会形成环，不能将该边作为最小生成树的边，将该边抛弃。

取出第 6 条边<B，C>，将B、C两个顶点的编号 i = 1，j = 2放到father数组查找它们的父顶点编号，查找到的编号分别是1、0对应顶点B、A，两个父顶点不同，则说明这条边加入后不会形成环，所以将边加入更新father数组（father[0] = 1）
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

father[0] = 1
father[1] = 1
father[2] = 0
father[3] = 0
father[4] = 1
father[5] = 3

由于该图有六个顶点，所以其最小生成树有5条边，到此已经找出其最小生成树的五条边，流程结束。

二、数据结构

1、图的存放结构：邻接矩阵
邻接矩阵的实现方式可查看：图之邻接矩阵详解（C语言版）

//设置默认的顶点个数
#define Default_Vertex_Size  10
//数据类型
#define T char
#define E int
#define MAX_COST  0x7FFFFFFF //代表无穷大

//邻接矩阵图结构
typedef struct GraphMtx
{
	int MaxVertices; //最大顶点数
	int NumVertices; //真实的顶点数
	int NumEdges;  //边数

	T   *VerticesList; //顶点列表
	int **Edge; //边信息矩阵
}GraphMtx;

kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论
2、Kruskal算法所需的结构

//选取的边
typedef struct Edge
{
	int x; // start 开始点
	int y; // end  结束点
	E   cost;  //边权值
}Edge;

//father数组，用来标记边的两个顶点是否在相同集合
int *father = (int*)malloc(sizeof(int) * n);

三、代码实现

1、领接矩阵实现

图初始化

//图的初始化
void InitGraph(GraphMtx *g)
{
	g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
	g->NumVertices = g->NumEdges = 0; //实际顶点数初始化

	//分配顶点存储列表的空间
	g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
	assert(g->VerticesList != NULL);

	//开辟边信息存储矩阵的空间（二维数组的动态开辟）
	g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
	assert(g->Edge != NULL);
	for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
	{
		g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
	}
	for(i=0; i<g->MaxVertices; ++i)  //初始化
	{
		for(int j=0; j<g->MaxVertices; ++j)
		{
			if(i == j)
			{
				g->Edge[i][j] = 0;
			}
			else
			{
				g->Edge[i][j] = MAX_COST;
			}
		}
	}
}

获取顶点的位置

//获取顶点的位置
int  GetVertexPos(GraphMtx *g, T v)
{
	for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
	{
		//判断是否找到顶点v所在位置
		if(g->VerticesList[i] == v)
			return i;
	}
	return -1;
}

打印图信息

//打印图信息
void ShowGraph(GraphMtx *g)
{
	printf("  ");
	for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
	{
		printf("%c  ",g->VerticesList[i]);
	}
	printf("\n");
	for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
	{
		printf("%c ",g->VerticesList[i]);
		for(int j=0; j<g->NumVertices; ++j)
		{
			if(g->Edge[i][j] == MAX_COST)
			{
				printf("%c  ",'@');
			}
			else
			{
				printf("%d  ",g->Edge[i][j]);
			}
		}
		printf("\n");
	}
	printf("\n");
}

插入顶点

//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
	if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
		return;
	g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}

插入边：在v1和v2顶点间插入边

//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
	int p1 = GetVertexPos(g,v1);  //获取v1顶点位置
	int p2 =  GetVertexPos(g,v2);  //获取v2顶点位置
	if(p1==-1 || p2==-1)
		return;

	//无向图存储 需要双向的
	g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
	g->NumEdges++; //记录实际边数
}

删除边：删除v1和v2顶点间的边

//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
	//求出两个顶点的下标位置
	int p1 = GetVertexPos(g,v1);
	int p2 =  GetVertexPos(g,v2);
	if(p1==-1 || p2==-1)
		return;

	if(g->Edge[p1][p2] == 0)
		return;

	//将边清空
	g->Edge[p1][p2] = g->Edge[p2][1] = 0;
	g->NumEdges--; //更新边数
}

删除顶点

//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
	//获取顶点的位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return;

	
	//释放顶点
	int numedges = 0;

	for(int i=p; i<g->NumVertices-1; ++i)
	{
		//将要释放顶点之后的顶点逐一前移
		g->VerticesList[i] = g->VerticesList[i+1];
	}

	//统计与要删除顶点相连的边条数
	for(i=0; i<g->NumVertices; ++i)
	{
		if(g->Edge[p][i] != 0)
		{
			numedges++;
		}
	}

	//删除与释放顶点相连的边（更改存放边信息的矩阵）
	for(i=p; i<g->NumVertices-1; ++i)
	{
		//将要删除行之后的行逐一向前移动一行
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[i][j] = g->Edge[i+1][j];
		}
	}

	for(i=p; i<g->NumVertices; ++i)//删除列
	{
		//将要删除列之后的列逐一向前移动一列
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[j][i] = g->Edge[j][i+1];
		}
	}
	g->NumVertices--;
	g->NumEdges -= numedges;
}

销毁图

//销毁图
void DestroyGraph(GraphMtx *g)
{
	//释放顶点
	free(g->VerticesList);
	g->VerticesList = NULL;
	//释放边存储结构的列
	for(int i=0; i<g->NumVertices; ++i)
	{
		free(g->Edge[i]);
	}
	free(g->Edge);//释放存放行指针的空间
	g->Edge = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

获取v第一个邻接顶点

//获取v第一个邻接顶点
int  GetFirstNeighbor(GraphMtx *g, T v)
{
	//获取顶点v所在位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return -1;

	//对顶点进行搜索，看那个顶点与v相连
	for(int i=0; i<g->NumVertices; ++i)
	{
		//判断是否，找到
		if(g->Edge[p][i] == 1)
			return i; //找到即返回
	}
	return -1;
}

获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）

//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int  GetNextNeighbor(GraphMtx *g, T v, T w)
{
	//获取v和w所在位置
	int pv = GetVertexPos(g,v);
	int pw = GetVertexPos(g,w);
	if(pv==-1 || pw==-1)
		return -1;

	//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
	for(int i=pw+1; i<g->NumVertices; ++i)
	{
		
		if(g->Edge[pv][i] == 1)
			return i; 
	}
	return -1;
}

获取边的权重

//获取边的权重
E    GetWeight(GraphMtx *g, int v1, int v2)
{
	if(v1==-1 || v2==-1)
		return MAX_COST;
	return g->Edge[v1][v2];
}

2、Kruskal算法实现

Kruskal算法获取最小生成树

//使用Kruskal算法获取最小生成树
void MinSpanTree_Kruskal(GraphMtx *g)
{
	//申请存放边的空间（根据无向图的对称性只要存放邻接矩阵上三角就可以）
	int n = g->NumVertices;
	Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
	assert(edge != NULL);

	//获取邻接矩阵中的边（查找邻接矩阵上三角就可以）
	int k = 0;
	for(int i=0; i<n; ++i)
	{
		for(int j=i; j<n; ++j)
		{
			if(g->Edge[i][j]!=0 && g->Edge[i][j]!=MAX_COST)
			{
				edge[k].x = i;
				edge[k].y = j;
				edge[k].cost = g->Edge[i][j];
				k++;
			}
		}
	}

	int v1,v2;
	//将各个边根据边的排序规则（权值越大边越大）排序，升序
	qsort(edge,k,sizeof(Edge),cmp);
	
	//初始化father数组，用来标记边的两个顶点是否在相同集合
	int *father = (int*)malloc(sizeof(int) * n);
	assert(father != NULL);
	for(i=0; i<n; ++i)
	{
		father[i] = i;//顶点i的父顶点为i
	}

	for(i=0; i<n; ++i)
	{
		//判断边的两个顶点是否在相同集合，如果在相同集合说明该边不能进行连接，会形成闭环
		if(!Is_same(father,edge[i].x,edge[i].y))
		{
			//不在同一集合，将边加入，并将边在father中进行标注
			//由于边根据权值进行升序排列，所以只需要按照顺序取出就可以
			v1 = edge[i].x;
			v2 = edge[i].y;
			printf("%c-->%c : %d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
			Mark_same(father,edge[i].x,edge[i].y);
		}
	}
}

边的比较规则：权值大就代表边大

//边的比较规则：权值大就代表边大
int cmp(const void*a, const void *b)
{
	return (*(Edge*)a).cost - (*(Edge*)b).cost;
}

判断两个顶点在father中是否记录有相同父顶点

//判断编号为i、j对应的顶点是否同在father集合中(就是查找i、j顶点在father中是否有相同父顶点)
bool Is_same(int *father, int i, int j)
{
	//查找顶点i的父顶点
	while(father[i] != i)
	{
		i = father[i];
	}
	//查找顶点j的父顶点
	while(father[j] != j)
	{
		j = father[j];
	}
	//判断i、j两个顶点的父顶点是否相同
	return i==j;
}

将边的两个顶点i、j在father中进行标注

//将边的两个顶点i、j在father中进行标注
void Mark_same(int *father, int i, int j)
{
	//查找顶点i的父顶点
	while(father[i] != i)
	{
		i = father[i];
	}
	//查找顶点j的父顶点
	while(father[j] != j)
	{
		j = father[j];
	}
	//合并：
	father[j] = i;
}

3、运行结果

#include"GraphMtx.h"

void main()
{
	GraphMtx gm;
	InitGraph(&gm);
	//插入顶点
	InsertVertex(&gm,'A');
	InsertVertex(&gm,'B');
	InsertVertex(&gm,'C');
	InsertVertex(&gm,'D');
	InsertVertex(&gm,'E');
	InsertVertex(&gm,'F');
	//插入边
	InsertEdge(&gm,'A','B',6);
	InsertEdge(&gm,'A','C',1);
	InsertEdge(&gm,'A','D',5);
	InsertEdge(&gm,'B','C',5);
	InsertEdge(&gm,'B','E',3);
	InsertEdge(&gm,'C','D',5);
	InsertEdge(&gm,'C','E',6);
	InsertEdge(&gm,'C','F',4);
	InsertEdge(&gm,'D','F',2);
	InsertEdge(&gm,'E','F',6);
	ShowGraph(&gm);

	//MinSpanTree_Prim(&gm,'E');
	//使用克鲁斯卡尔算法获取最小生成树
	MinSpanTree_Kruskal(&gm);
}

运行结果
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

测试的图结构
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

获取的最小生成树
kruskal 新增删除边代码 c,数据结构与算法,算法,c语言,图论

附录

Main.cpp

#include"GraphMtx.h"

void main()
{
	GraphMtx gm;
	InitGraph(&gm);
	//插入顶点
	InsertVertex(&gm,'A');
	InsertVertex(&gm,'B');
	InsertVertex(&gm,'C');
	InsertVertex(&gm,'D');
	InsertVertex(&gm,'E');
	InsertVertex(&gm,'F');
	//插入边
	InsertEdge(&gm,'A','B',6);
	InsertEdge(&gm,'A','C',1);
	InsertEdge(&gm,'A','D',5);
	InsertEdge(&gm,'B','C',5);
	InsertEdge(&gm,'B','E',3);
	InsertEdge(&gm,'C','D',5);
	InsertEdge(&gm,'C','E',6);
	InsertEdge(&gm,'C','F',4);
	InsertEdge(&gm,'D','F',2);
	InsertEdge(&gm,'E','F',6);
	ShowGraph(&gm);

	//MinSpanTree_Prim(&gm,'E');
	//使用克鲁斯卡尔算法获取最小生成树
	MinSpanTree_Kruskal(&gm);
}

GraphMtx.h

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdlib.h>

#define Default_Vertex_Size  10 

#define T char
#define E int
#define MAX_COST  0x7FFFFFFF

typedef struct GraphMtx
{
	int MaxVertices;
	int NumVertices;
	int NumEdges;

	T   *VerticesList;
	int **Edge;
}GraphMtx;

void InitGraph(GraphMtx *g);
int  GetVertexPos(GraphMtx *g, T v);
void ShowGraph(GraphMtx *g);
void InsertVertex(GraphMtx *g, T v);
void InsertEdge(GraphMtx *g, T v1, T v2, E cost);
void RemoveVertex(GraphMtx *g, T v);
void RemoveEdge(GraphMtx *g, T v1, T v2);
void DestroyGraph(GraphMtx *g);
int  GetFirstNeighbor(GraphMtx *g, T v);
int  GetNextNeighbor(GraphMtx *g, T v, T w);

E    GetWeight(GraphMtx *g, int v1, int v2);

//
//选取的边
typedef struct Edge
{
	int x; // start 开始点
	int y; // end  结束点
	E   cost;  //边权值
}Edge;

void MinSpanTree_Kruskal(GraphMtx *g);

GraphMtx.cpp文章来源地址https://www.toymoban.com/news/detail-698729.html

#include"GraphMtx.h"

//图的初始化
void InitGraph(GraphMtx *g)
{
	g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
	g->NumVertices = g->NumEdges = 0; //实际顶点数初始化

	//分配顶点存储列表的空间
	g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
	assert(g->VerticesList != NULL);

	//开辟边信息存储矩阵的空间（二维数组的动态开辟）
	g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
	assert(g->Edge != NULL);
	for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
	{
		g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
	}
	for(i=0; i<g->MaxVertices; ++i)  //初始化
	{
		for(int j=0; j<g->MaxVertices; ++j)
		{
			if(i == j)
			{
				g->Edge[i][j] = 0;
			}
			else
			{
				g->Edge[i][j] = MAX_COST;
			}
		}
	}
}

//获取顶点的位置
int  GetVertexPos(GraphMtx *g, T v)
{
	for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
	{
		//判断是否找到顶点v所在位置
		if(g->VerticesList[i] == v)
			return i;
	}
	return -1;
}

//打印图信息
void ShowGraph(GraphMtx *g)
{
	printf("  ");
	for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
	{
		printf("%c  ",g->VerticesList[i]);
	}
	printf("\n");
	for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
	{
		printf("%c ",g->VerticesList[i]);
		for(int j=0; j<g->NumVertices; ++j)
		{
			if(g->Edge[i][j] == MAX_COST)
			{
				printf("%c  ",'@');
			}
			else
			{
				printf("%d  ",g->Edge[i][j]);
			}
		}
		printf("\n");
	}
	printf("\n");
}

//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
	if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
		return;
	g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}

//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
	int p1 = GetVertexPos(g,v1);  //获取v1顶点位置
	int p2 =  GetVertexPos(g,v2);  //获取v2顶点位置
	if(p1==-1 || p2==-1)
		return;

	//无向图存储 需要双向的
	g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
	g->NumEdges++; //记录实际边数
}

//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
	//求出两个顶点的下标位置
	int p1 = GetVertexPos(g,v1);
	int p2 =  GetVertexPos(g,v2);
	if(p1==-1 || p2==-1)
		return;

	if(g->Edge[p1][p2] == 0)
		return;

	//将边清空
	g->Edge[p1][p2] = g->Edge[p2][1] = 0;
	g->NumEdges--; //更新边数
}

//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
	//获取顶点的位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return;

	
	//释放顶点
	int numedges = 0;

	for(int i=p; i<g->NumVertices-1; ++i)
	{
		//将要释放顶点之后的顶点逐一前移
		g->VerticesList[i] = g->VerticesList[i+1];
	}

	//统计与要删除顶点相连的边条数
	for(i=0; i<g->NumVertices; ++i)
	{
		if(g->Edge[p][i] != 0)
		{
			numedges++;
		}
	}

	//删除与释放顶点相连的边（更改存放边信息的矩阵）
	for(i=p; i<g->NumVertices-1; ++i)
	{
		//将要删除行之后的行逐一向前移动一行
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[i][j] = g->Edge[i+1][j];
		}
	}

	for(i=p; i<g->NumVertices; ++i)//删除列
	{
		//将要删除列之后的列逐一向前移动一列
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[j][i] = g->Edge[j][i+1];
		}
	}
	g->NumVertices--;
	g->NumEdges -= numedges;
}

//销毁图
void DestroyGraph(GraphMtx *g)
{
	//释放顶点
	free(g->VerticesList);
	g->VerticesList = NULL;
	//释放边存储结构的列
	for(int i=0; i<g->NumVertices; ++i)
	{
		free(g->Edge[i]);
	}
	free(g->Edge);//释放存放行指针的空间
	g->Edge = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

//获取v第一个邻接顶点
int  GetFirstNeighbor(GraphMtx *g, T v)
{
	//获取顶点v所在位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return -1;

	//对顶点进行搜索，看那个顶点与v相连
	for(int i=0; i<g->NumVertices; ++i)
	{
		//判断是否，找到
		if(g->Edge[p][i] == 1)
			return i; //找到即返回
	}
	return -1;
}

//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int  GetNextNeighbor(GraphMtx *g, T v, T w)
{
	//获取v和w所在位置
	int pv = GetVertexPos(g,v);
	int pw = GetVertexPos(g,w);
	if(pv==-1 || pw==-1)
		return -1;

	//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
	for(int i=pw+1; i<g->NumVertices; ++i)
	{
		
		if(g->Edge[pv][i] == 1)
			return i; 
	}
	return -1;
}

//获取边的权重
E    GetWeight(GraphMtx *g, int v1, int v2)
{
	if(v1==-1 || v2==-1)
		return MAX_COST;
	return g->Edge[v1][v2];
}



///
//Kruskal

//边的比较规则：权值大就代表边大
int cmp(const void*a, const void *b)
{
	return (*(Edge*)a).cost - (*(Edge*)b).cost;
}

//判断编号为i、j对应的顶点是否同在father集合中(就是查找i、j顶点在father中是否有相同父顶点)
bool Is_same(int *father, int i, int j)
{
	//查找顶点i的父顶点
	while(father[i] != i)
	{
		i = father[i];
	}
	//查找顶点j的父顶点
	while(father[j] != j)
	{
		j = father[j];
	}
	//判断i、j两个顶点的父顶点是否相同
	return i==j;
}

//将边的两个顶点i、j在father中进行标注
void Mark_same(int *father, int i, int j)
{
	//查找顶点i的父顶点
	while(father[i] != i)
	{
		i = father[i];
	}
	//查找顶点j的父顶点
	while(father[j] != j)
	{
		j = father[j];
	}
	//合并：
	father[j] = i;
}

//使用Kruskal算法获取最小生成树
void MinSpanTree_Kruskal(GraphMtx *g)
{
	//申请存放边的空间（根据无向图的对称性只要存放邻接矩阵上三角就可以）
	int n = g->NumVertices;
	Edge *edge = (Edge *)malloc(sizeof(Edge) * (n*(n-1)/2));
	assert(edge != NULL);

	//获取邻接矩阵中的边（查找邻接矩阵上三角就可以）
	int k = 0;
	for(int i=0; i<n; ++i)
	{
		for(int j=i; j<n; ++j)
		{
			if(g->Edge[i][j]!=0 && g->Edge[i][j]!=MAX_COST)
			{
				edge[k].x = i;
				edge[k].y = j;
				edge[k].cost = g->Edge[i][j];
				k++;
			}
		}
	}

	int v1,v2;
	//将各个边根据边的排序规则（权值越大边越大）排序，升序
	qsort(edge,k,sizeof(Edge),cmp);
	
	//初始化father数组，用来标记边的两个顶点是否在相同集合
	int *father = (int*)malloc(sizeof(int) * n);
	assert(father != NULL);
	for(i=0; i<n; ++i)
	{
		father[i] = i;//顶点i的父顶点为i
	}

	for(i=0; i<n; ++i)
	{
		//判断边的两个顶点是否在相同集合，如果在相同集合说明该边不能进行连接，会形成闭环
		if(!Is_same(father,edge[i].x,edge[i].y))
		{
			//不在同一集合，将边加入，并将边在father中进行标注
			//由于边根据权值进行升序排列，所以只需要按照顺序取出就可以
			v1 = edge[i].x;
			v2 = edge[i].y;
			printf("%c-->%c : %d\n",g->VerticesList[v1],g->VerticesList[v2],edge[i].cost);
			Mark_same(father,edge[i].x,edge[i].y);
		}
	}
}