数据结构kruskal算法求最小生成树Word格式文档下载.docx

资源描述

数据结构kruskal算法求最小生成树Word格式文档下载.docx

《数据结构kruskal算法求最小生成树Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构kruskal算法求最小生成树Word格式文档下载.docx（13页珍藏版）》请在冰点文库上搜索。

数据结构kruskal算法求最小生成树Word格式文档下载.docx

;

③标记起源点s，记k=s,其他所有点设为未标记的。

2）检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：

dj=min[dj,dk+lkj]

dj中最小的一个i：

式中，lkj是从点k到j的直接连接距离。

3）选取下一个点。

从所有未标记的结点中，选取

di=min[dj,所有未标记的点j]

点i就被选为最短路径中的一点，并设为已标记的。

4）找到点i的前一点。

从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：

i=j*

5）标记点i。

如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。

而程序中求两点间最短路径算法。

其主要步骤是：

①调用dijkstra算法。

②将path中的第“终点”元素向上回溯至起点，并显示出来。

程序结构框图为：

三、程序具体实现

1、kruskal函数：

因为kruskal需要一个有序的边集数组，所以要先对边集数组排序。

其次，在执行中需要判断是否构成回路，因此还另有一个判断函数seeks，在kruskal中调用seeks。

2、dijkstra函数：

因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。

该函数的关键在于dist数组的重新置数。

该置数条件是：

该顶点示被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。

因此第一次将其设为：

if（s[w]==0&

cost[u][w]+dist[u]<

dist[w]）。

但是在实

际运行中，发现有些路径的权值为负。

经过分析发现，因为在程序中∞由32767代替。

若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。

但是如果cost[u][w]==32767，那么dist[w]肯定不需重新置数。

所以将条件改为：

dist[w]&

cost[u][w]!

=32767）。

修改之后，问题果然解决。

3、printpath1函数：

该函数主要用来输出源点到其余各点的最短路径。

因为在主函数调用该函数前，已经调用了dijkstra函数，所以所需的dist、path、s数组已经由dijkstra函数生成，因此在该函数中，只需用一变量控制循环，一一将path数组中的每一元素回溯至起点即可。

其关键在于不同情况下输出形式的不同。

4、printpath2函数：

该函数主要用来输出两点间的最短路径。

其主要部份与printpath1函数相同，只是无需由循环将所有顶点一一输出，只需将path数组中下标为v1的元素回溯至起点并显示出来。

四、源程序

#defineMAXE100

structedges

{intbv;

inttv;

intw;

};

typedefstructedgesedgeset;

intseeks（intset[],intv）

{inti;

i=v;

while（set[i]>

0）i=set[i];

returni;

}

kruskal（edgesetge[],intn,inte）

{intset[MAXE],v1,v2,i,j;

for（i=1;

n+1;

i++）set[i]=0;

i=1;

j=1;

while（j<

=e&

=n-1）

{v1=seeks（set,ge[j].bv）;

v2=seeks（set,ge[j].tv）;

if（v1!

=v2）

{printf（"

（%d,%d）:

%d\n"

ge[j].bv,ge[j].tv,ge[j].w）;

set[v1]=v2;

i++;

j++;

voidinsertsort（edgesetge[],inte）

{inti,j;

for（i=2;

=e;

i++）

if（ge[i].w<

ge[i-1].w）

{ge[0]=ge[i];

j=i-1;

while（ge[0].w<

ge[j].w）

{ge[j+1]=ge[j];

j--;

ge[j+1]=ge[0];

voiddijkstra（intcost[MAXE][MAXE],intdist[MAXE],intpath[MAXE],ints[MAXE],intn,intv0）

{intu,vnum,w,wm;

for（w=1;

=n;

w++）

{dist[w]=cost[v0][w];

if（cost[v0][w]<

32767）

path[w]=v0;

vnum=1;

while（vnum<

{wm=32767;

u=v0;

if（s[w]==0&

dist[w]<

wm）

{u=w;

wm=dist[w];

s[u]=1;

vnum++;

dist[u]+cost[u][w]<

=32767）{dist[w]=dist[u]+cost[u][w];

path[w]=u;

voidprintpath1（intdist[],intpath[],ints[],intn,intv0）

{inti,k;

i++）if（s[i]==1）{k=i;

while（k!

=v0）

%d<

k）;

k=path[k];

printf（"

%d:

k,dist[i]）;

else

-%d:

32767\n"

i,v0）;

voidprintpath2（intdist[],intpath[],intv0,intv1）

{intk;

k=v1;

while（k!

k,dist[v1]）;

main（）

{edgesetge[MAXE];

intcost[MAXE][MAXE],dist[MAXE],path[MAXE],s[MAXE],a,n,e,i,j,k,v0,v1;

printf（"

inputthenumberofpoint:

）;

scanf（"

%d"

n）;

inputthenumberofedges:

e）;

inputtheedges:

\n"

%d,%d,%d"

ge[i].bv,&

ge[i].tv,&

ge[i].w）;

pleasechoise\n"

1.kruskal\n"

printf（“2.shortpath\n”）;

printf（“3.shortpathbetweentwopoint\n”）;

printf（“4.exit\n”）;

a）;

while（a!

=4）

{switch（a）

{case1:

insertsort（ge,e）;

kruskal（ge,n,e）;

break;

case2:

inputthestartpoint:

v0）;

for（j=1;

j++）

cost[i][j]=32767;

for（k=1;

k++）

{i=ge[k].bv;

j=ge[k].tv;

cost[i][j]=ge[k].w;

s[i]=0;

s[v0]=1;

dijkstra（cost,dist,path,s,n,v0）;

printpath1（dist,path,s,n,v0）;

case3:

inputtheendpoint:

v1）;

printpath2（dist,path,v0,v1）;

五、程序调试

将如下图输入：

依次输入：

6（六个顶点）

10（十条边）

1，2，6

1，3，1

1，4，5

2，3，5

2，5，3

3，4，5

3，5，6

3，6，4

4，6，2

5，6，6

显示菜单。

选择1输出：

（1，3）：

4，

6）：

2，

5）：

3，

3）：

选择2

输入1（起点）输出：

1：

327672<

-1:

63<

14<

55<

-3<

76<

选择3

输入1（起点）

5（终点）

输出:

7选择4退出。

六、附录

3阶B_树中，画

将序列3，7，2，1，4，6，8，9，10，5插入到初始为空的平衡树和出插入过程，然后依次删除每个元素，画出删除过程。

平衡树插入过程如下所示：

710

RL38

2479

1510

平衡树删除过程如下所示：

删3

删76

2479

510

删

RR29

14810

4810

15810

删16

删65

5810

删8

RL59

1010

删95删105删510

B-树的插入过程如下所示：

插入33插入737插入23插入1327127

插入

插入636

插入836

471

71247

106

12479

插入56

12457910

展开阅读全文