基于C++的图的应用(数据结构)

来总结一下数据结构中图的应用?

 

 


前期工作:

图的基本操作

一些定义:

#define MaxInt 32767    //表示极大值
#define MVNum 100    //最大顶点数
#define ArcNum 100     //边的数量
typedef char VerTexType;  //假设顶点的数据类型是字符型
typedef int ArcType;   //边的权值类型是整型
typedef  int OtherInfo;
enum Status
{
	OK,
	ERROR
};

我利用了邻接矩阵来存储图的信息:

//采用邻接矩阵创建无向网
typedef struct
{
	VerTexType vex[MVNum];   //存放顶点的数组
	ArcType arcs[MVNum][MVNum];  //邻接矩阵
	int vexnum, arcnum;     //顶点数和边数
}AMGraph;
Status CreateUDN(AMGraph &G)
{
	cout << "输入顶点数,总边数\n";
	cin >> G.vexnum >> G.arcnum;   //输入顶点数,总边数
	cout << endl;
	for (int i = 0; i < G.vexnum; i++)   //初始化顶点
	{
		//cout << "第"<<(i+1)<<"个顶点初始化为"<<i+1;
		G.vex[i]=i+1;           //这里就用1,2,3……初始化顶点了
	}
	for (int i = 0; i < G.vexnum; i++)  //初始化邻接矩阵(都设置成最大权值)
	{
		for (int l = 0; l < G.vexnum; l++)
		{
			G.arcs[i][l]= MaxInt;
		}
	}
	cout << endl;
	int v1, v2;
	ArcType w;
	for (int i = 0; i < G.arcnum; i++)   //构造邻接矩阵
	{
		cout << "第" << (i + 1) << "个边的两个顶点,以及权值:";
		cin >> v1 >> v2 >> w;      //输入边的顶点数值(从1开始)以及权值
		v1--;
		v2--;
		G.arcs[v1][v2] = w;       //赋予权值
		G.arcs[v2][v1] = G.arcs[v1][v2];    //无向图对称
	
	}
	cout << endl;
	return OK;
}

最小生成树:

Prim算法:

利用普莱姆算法找最小生成树,原理就是用一个全集V下的集合U来不断分析U与V-U之间的那几条线,记录那个权值最小的,然后收录被指向的顶点,如此往复。

此图中,就在进行Prim算法:

U集合:A、B

V-U集合:D、E、C

U与V-U中间的线:AD、AE、BC(这些线即将被分析权值最小)

代码:

建立一个辅助数组结构体

struct CloseEdge
{
	VerTexType adjvex;        //顶点
	ArcType lowcost;           //边上的权值
}closeedge[MVNum];         //辅助数组,用来记录从点集U到V-U的权值最小的边

实现普莱姆,输出路径边

void MiniSpanTree_Prim(AMGraph G, VerTexType u)            //普利姆算法生成最小生成树
{
	int k=u;
	//利用循环赋值,将U集到V-U集的边先赋值为初始顶点附近的边(U现在只有这个顶点)
	for (int j = 0; j < G.vexnum; ++j)     
	{
		if (j != k)
			closeedge[j] = { u,G.arcs[k][j] };   
	}
	//权值为零,即标志这个k对应的顶点属于U的集合,记住:closeedge的下标是被指向点的下标
	closeedge[k].lowcost = 0;
	int u0, v0;
	for (int i = 1; i < G.vexnum; i++) //循环顶点数减一次
	{
		//在辅助数组中找到一个权值不为零且最小的顶点,即U集合到V-U集合最小的那条边,我们即将连接它,k是被指向的点的下标
		k = Min(closeedge, G.vexnum);
		u0 = closeedge[k].adjvex;        //记录最小边的起始点
		v0 = G.vex[k];                 //记录被指向的点的下标
		cout << "由"<<u0<<"到"<<v0<<endl;      //输出
		closeedge[k].lowcost = 0;    //将刚刚处理的k,归入U集
		for (int j = 0; j < G.vexnum; j++)      //更新closeedge数据,即U集的指向
		{
			//刚才加入的点(k)对某一 V-U 集合的点有更小的权值,则我们将closeedge中对应位置的变更
			//U集合的点在closeedge中对应位置已经被赋值为0,不必担心指向已经属于U的点
			if (G.arcs[k][j] < closeedge[j].lowcost)     
				closeedge[j] = { G.vex[k],G.arcs[k][j] };
		}
	}
}

Kruskal算法:

利用克鲁斯凯尔算法来生成最小生成树,原理是将图中的边都先收起来,通过权值进行排序,然后配合连通分量(一个一维数组,用来标识顶点是否被连接过,一开始会初始化成0,1,2,3……,每连接一个边,后者的连通分量就会变为前者)来将这些边筛选出最小生成树的路。

代码:

建立一个保存边信息的结构体,以及记录对应顶点连通分量的一维数组:

struct Ed
{
	VerTexType Head;      //边的初始位置
	VerTexType Tail;      //边的末尾位置
	ArcType lowcost;      //边上的权值
}Edge[ArcNum];                        //记录边的信息的数组
int Vexset[MVNum];          //标识各个顶点的连通分量

实现克鲁斯凯尔算法,输出边:

void MiniSpanTree_Kruskal(AMGraph G)    
{
	int v1, v2, vs1, vs2;
	Sort(Edge);           //将这些边根据权值进行排序
	for (int i = 0; i < G.vexnum; i++)  //初始化连通分量
		Vexset[i] = i;
	for (int i = 0; i < G.arcnum; ++i)
	{
		v1 = LocateVex(Edge[i].Head);    //v1为边的起始点的下标
		v2 = LocateVex(Edge[i].Tail);     //v2为边的终点的下标
		vs1 = Vexset[v1];                   //根据下标找对应的连通分量
		vs2 = Vexset[v2];
		if (vs1 != vs2)
		{
			cout << Edge[i].Head << Edge[i].Tail;       //输出这条边
			for (int j = 0; j < G.vexnum; j++)        //遍历vexset数组
			{
				if (Vexset[j] == vs2)        //找到刚才输出的边
					Vexset[j] = vs1;         //改变它的连通分量,让它加入大部队
			}
		}
	}
}



最短路径:

Dijkstra:

利用迪杰斯特拉算法来记录一个源点到其他各个点的最短路径,利用布尔数组S来记录已经经过的顶点,用数组D来记录对应顶点到源点的权值。

如图,顶点A、B即属于S集合,B顶点对应的D数组的数据是2

再往下一步,因为C到源点A的权值是3(目前最小),所以C也归入了S集合

如此往复,D数组中就记录了其他顶点到源点的最短路径

代码,先建立这些数组:

bool S[MVNum];           //判断顶点是否属于S的布尔数组
VerTexType Path[MVNum];         //记录对应顶点的前驱
ArcType D[ArcNum];             //记录源点到对应顶点的权值

迪杰斯特拉算法实现最短路径

void ShortestPath_DIJ(AMGraph G, int v0)   
{
	int n = G.vexnum;     //n为G中顶点的个数
	for (int v=0;v<n;v++)
	{
		S[v] = false;            //初始化S集合为空集
		D[v] = G.arcs[v0][v];         //将v0到各个终点的最短路径长度初始化为弧上的权值
		if (D[v] < MaxInt)           //如果v0和v之间有弧,则将v的前驱置为v0
			Path[v] = v0;
		else                        //没有弧,则将v的前驱置为-1
			Path[v] = -1;            
	}
	S[v0] = true;               //将v0加入S
	D[v0] = 0;                    //源点到源点的距离为0
	//开始主循环
	for (int i = 1; i < n; i++)
	{
		int v;
		int min = MaxInt;          
		for (int w=0; w < n; ++w)
		{
			if (!S[w] && D[w] < min)             //这个顶点不属于S集合且它对应的权值小于min
			{
				v = w;               //保留下标
				min = D[w];         //更新临时最小值
			}
		}
		S[v] = true;                    //将刚才记录的最小的下标对应的顶点归属于S
		for (int w = 0; w < n; w++)      //更新从v0出发到集合V-S上所有顶点的最短路径长度
		{
			//w顶点不属于S且刚才记录的顶点的权值加上这个点到它的指向的权值小于源点到w的值
			if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))  
			{
				D[w] = D[v] + G.arcs[v][w];   //改变w顶点的权
				Path[w] = v;       //改变w顶点的前驱
			}
		}

	}
}

 

 

 


 

 

 

 

商业转载 请联系作者获得授权,非商业转载 请标明出处

发表评论