-
图的最短路径
一、问题描述
最小生成树是一个有<
/p>
n
个结点的连通图的生成树是原图的极小连通子图，
且包含原图中
的所有个结点，
并且有保持图连通的最
小的边，
最小生成树在实际问题中具有一定的应用价
值，如在城
市之间建设网络，要保证网络的连通性，求最经济的设计方法。
求解最小生成树
时，可以采用普里母算法和克鲁斯卡尔算法。
二、基本要求
1
、
选择合适的储存结构，完成网的建立；
2
、
利用普里母算法求网的最少生成树，并输出结果；
3
、
利用克鲁斯卡尔求网的最少生成树，并输出结果；
4
、
采用邻接矩阵和邻接表两种储存结构；
三、测试数据
对右图进行测试
右图是
6
个顶点的
10
个边的连通
图
六个顶点分别是
v1 v2 v3 v4 v5 v6
边和边上的权植分别是
v1 v2
6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
四、算法思想
克鲁斯卡尔算法思想是：假设连通图
N=
（
V
，
{E}
），则令最小生成
树的初始状态为只
有
n
个顶点而无边的
非连通图
T=
（
V
，
{ }
），图中每个顶点自成一个连通分量。在
E
中选
择代价最小的边，
若该边依附的顶点落在
T
中不同的连通分量上，
则将此边加入到
T
中，
否<
/p>
则舍去此边而选择下一条代价最小的边。
以此类推，
直至
T
中所有顶点都在同一连通分量上
为止。
普里母算法
思想是：假设
N=
（Ｖ，｛Ｅ｝）是连通图，ＴＥ是Ｎ上最小生
成树中边的
集合。算法从Ｕ＝｛
u0
｝
（
u0
∈
V
）
，
TE={
}
开始，重复执行下述操
作：在所有
u
∈
U
，
v
∈
V
—
U
的边（
u
，
v
）∈
E
中
找一条代价最小的边（
u0
，
v0
）并入集合
TE
，同时
v0
并入
U
，直至
U=V
为止。此时
TE
中必有
ｎ－１条边，则Ｔ＝（Ｖ，｛ＴＥ｝）为Ｎ的最小生成树。为实
现这个算法需附设辅助数
组
closedge,
以记录从
U
到
V-U
具有最小代价的边。
对每个顶点
vi
∈
V-U<
/p>
，在辅助数组中存在一个相应分量
closedge[i-1]<
/p>
，它包括两个域，其中
lowcost
储
存该边的权。显然，
closedge[i-1].lowco
st=Min{cost(u,vi)|u
∈
U},vex
∈
U},
vex
域存储
该边依附的在
U
中的顶点
。
五、模块
克鲁斯卡尔算法和普里母算法都要用到以下的算法
int LocateVex(Mgraph G,Vertex u)
，矩阵求点
u
所在位置；
void CreateGraph(Mgraph/ ALGraph &G)<
/p>
，建立带权邻接矩阵
/
邻接表的结构；<
/p>
void kruskal2(ALGraph
G)
，邻接链表的克鲁斯卡尔算法；
void kruskal(MGraph
G)
，邻接矩阵的克鲁斯卡尔算法；
int
minimum(ALGraph/
MGraph
G,struct
arry
wq[])
，邻接表
/
邻接矩阵求最小的权值；
void MiniSpanTree_PRIM1(ALGraph
G,VertexType u)
，邻接表的普里姆算法；
void MiniSpanTree_PRIM2(MGraph
G,VertexType u)
，邻接矩阵的普里姆算法。
六、数据结构
//(ADT)
1
、邻接表的储存结构如下
邻接表的结点结构信息
typedef struct
ArcNode{/*
定义边结点
*/
int
adjvex;/*
该弧指向的顶点的位置
*/
int
weight;/*
该弧的权重
*/
struct ArcNode
*nextarc;/*
指向下一条弧的指针
*/
}ArcNode;
邻接表的表头向量的结点结构信息
typedef struct VNode{
VertexType data;
/*
顶点信息
*/
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
ArcNode *firsta
rc;/*
指向第一条依附该顶点的弧的指针
*/
}VNode,AdjList[MAX_VERTEX_NUM];//
定义图结点
邻接表的表头带权图的结构信息
typedef struct{
AdjList
vertices;/*
表头向量
*/
int
vexnum,arcnum;//
顶点数和弧数
}ALGraph;//
定义图
2
、邻接矩阵的储存结构如下
typedef int AdjMatrix[MAX_VERTEX_NU
M][MAX_VERTEX_NUM];/*
邻接距阵
*/
邻接矩阵带权图的结构信息
struct MGraph
{ Vertex v
exs[MAX_VERTEX_NUM];/*
顶点向量
*/
AdjMatrix
arcs;/*
邻接矩阵
*/
int
vexnum,arcnum;/*
顶点数和弧数
*/
};
七、源程序
#include
#include
#include
#define
MAX_NAME 5 /*
顶点值最大字符数
*/
#define MAX_VERTEX_NUM 20
/*
最大顶点数
*/
typedef
char Vertex[MAX_NAME];/*(
邻接矩阵用
)
顶点名字串
*/
typedef char VertexType[MAX_NAME];/*(
邻接链表用
)
顶点名字串
< br>*/
typedef int AdjMatrix[MAX_VER
TEX_NUM][MAX_VERTEX_NUM];/*
邻接距阵
< br>*/
/*
链表的结点结构信息
*/
typedef struct
ArcNode{/*
定义边结点
*/
int
adjvex;/*
该弧指向的顶点的位置
*/
int
weight;/*
该弧的权重
*/
struct ArcNode
*nextarc;/*
指向下一条弧的指针
*/
}ArcNode;
/*
表头向量的结点结构信息
*/
typedef struct VNode{
VertexType
data;/*
顶点信息
*/
ArcNode *firstarc;/*
指向第一条依附该
顶点的弧的指针
*/
}VNode,AdjList[MAX
_VERTEX_NUM];//
定义图结点
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
/*
链表带权图的结构信息
*/
typedef struct{
AdjList
vertices;/*
表头向量
*/
int
vexnum,arcnum;//
顶点数和弧数
}ALGraph;//
定义图
/*
矩阵带权图的结构信息
*/
struct MGraph
{ Vertex v
exs[MAX_VERTEX_NUM];/*
顶点向量
*/
AdjMatrix
arcs;/*
邻接距阵
*/
int
vexnum,arcnum;/*
顶点数和弧数
*/
};
struct arry
{
VertexType adjvex;
int lowcost;
}closedge[MAX_VERTEX_NUM];
int LocateVex(MGraph G,Vertex u)//
矩阵求点
u
所在位置
{ int i;
for(i=0;i<;++i)
if(strcmp(u,[i])==0)
return i;
return
-1;
}
int LocateVe(ALGraph
G,VertexType u)//
链表求出点
u
所在位置
{ int i;
}
/*========================
====================*/
/*===========
邻接矩阵的克鲁斯卡尔算法
=========*/
/*============================================
*/
void CreateGraph(MGraph
&G)//
建立带权邻接矩阵结构
{
int i,j,k,w;
Vertex va,vb;
for(i=0;i<;++i)
if(strcmp(es[i].data,u) == 0)
return i;
return
-1;
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
printf(
请输入
无向网
G
的顶点数和边数
(
分别以空格为分隔
):n
scanf(
printf(
请输入
%d
个顶点的值
:n
for(i=0;i<;++i) /*
读入顶点信息
*/
scanf(
for(i=0;i<;++i)/*
初始化邻接矩阵
*/
for(j=0;j<;++j)
[i][j]=0x7fffffff;
printf(
请输入
%d
条边各自的起点
,
终点
,
权值
(
分别用空格分隔
):n
for(k=0;k<;++k)/*
读入边
*/
{ scanf(
i=LocateVex(G,va);
j=LocateVex(G,vb);
[i][j]=[j][i]=w;/*
对称
*/
}
}
/*
邻接矩阵的克鲁斯卡尔算法
*/
void kruskal(MGraph G)
{
int set[MAX_VERTEX_NUM],i,j;/*set
数组用来判断
两个点是否在同一个集合里
*/
int
k=0,a=0,b=0,min=[a][b];
for(i=0;i<;i++)
set[i]=i;
printf(
最小代价生成树的各条边为<
/p>
:n
while(k<-1)
{ for(i=0;i<;++i)
for(j=i+1;j<;++j)
若 、
if([i][j]
求最小权值的边
*/
{
min=[i][j];
a=i;
b=j;
}
min=[a][b]=0
x7fffffff;//
将最小权值改成最大值
if(set[a]!=set[b])/*
a
、
b
两个点不在同一集合里，
则输出
a
、<
/p>
b
之间的边
*/
{ /*int s1=set[b];*/
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
printf(
k++;
for(i=0;i<;i++)//
将
a
b
放在同一集合里
if(set[i]==set[b]/*s1*/)
set[i]=set[a];
}
}
}
/*
邻接矩阵的克鲁斯卡尔算法
*/
void k1(){
MGraph g;
CreateGraph(g);
kruskal(g);
}
/*============
================================*/
/*==
=========
邻接链表的克鲁斯卡尔算法
=======
==*/
/*================================
============*/
void CreateGraph(ALGraph
&G){ //
邻接链表创建带权图
int i,j,k,w;
VertexType va,vb;
printf(
请输入顶点数
,
边数
(
请用空格分开
):n
输入顶点数、弧
数
*/
scanf(
printf(
请输入各顶点的值
:n
for(i =
0; i < ++i)/*
初始化顶点值
*/
scanf(
for(i = 0;
i < ++i)//
初始化
vertices
数组
es[i].firstarc=NULL;
printf(
请输入各边的起点
,
终点
,
权值
(
分别用空格分开
)
:n
for(k = 0; k < ++k){
scanf(
i = LocateVe(G,va)
;/*
确定
va
、
vb
的位置
*/
j =
LocateVe(G,vb);
ArcNode *p = (ArcNode
*)malloc(sizeof(ArcNode));
//
申请一个结点空间
p->adjvex =
j;//
初始化
p->weight
= w;
wilyes11
收集
<
/p>
博客
(
与学习无关
)
：
/u/1810231802
}
}
p->nextarc =
es[i].firstarc;//
插表头
es[i].firstarc =p;
ArcNode
*q = (ArcNode *)malloc(sizeof(ArcNode));
q->adjvex = i;
q->weight =
w;
q->nextarc = es[j].firstarc;
es[j].firstarc = q;
/*
邻接链表的克鲁斯卡尔算法
*/
void kruskal2(ALGraph G){
int
i,j,min = 0x7fffffff,k =
0;//min
用于记录最小权值
int set[MAX_VERTEX_NUM];//
用于
判断两个点是否在同一集合里
ArcNode
*p,*q,*s;
for(i = 0; i < ++i) set[i]
= i;//
初始化，将每个点自身作为一个集合
while(k < - 1){
for(i = 0; i <
; ++i){
if(es[i].firstarc!=
NULL){//
若第
i+1
个点没有
领边，则下一循环
for(p=es[i].firstar
c;p!=NULL;p=p->nextarc)//
查找最小权值的边
}
if(es[j].firstarc
==
q)
es[j].firstarc
=
q->nextarc;
}
if(p->weight < min){
}
min = p->weight;
q = p;
j = i;
//if-
else
用于删除最小权值的边
else{
}
if(set[j]!=set
[q->adjvex]){//
判断两点是否在同一集合
,<
/p>
若不在，
则输出这条边
for(p =
es[j].firstarc; p != q; p = p->nextarc) s = p;
s->nextarc = q->nextarc;
printf(
k++;
wilyes11
收集
博客
(
与学习无关
)
：
/u/1810231802
-
-
-
-
-
-
-
-
-
上一篇：Fluent网格格式
下一篇：CloudCompare功能概要