首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


邻接边 (4,5) (3,4) (1,4) (1,3) (1,2) (2,4) (2,5) (3,5) (1,5) (2,3) 权值 2 3 5 6 7 8 8 9 12 14

step

1:首先从上表中选择最小权值的边(4,5)加到生成树中。

图 7-7

(1)

图 7-7

(2)

Step2:依次取出第二条边(3,4)加到生成树中。

图 7-7

(3)

图 7-7

(4)

Step

3

将(1,4)边加入到生成树中。

Step 4 因加入(1,3)边,会产生回路,因此加入(1,2)边。有 5 个结点,而有 4 条边,因此整个生 成树建立过程结束。 这两种算法的角度不同,适合于针对不同的图,对稀疏图来说,顶点多而边少,采用克鲁斯卡尔 算法较好;而对稠密图来说,顶点少而边多,最好用普里姆算法。 我们以克鲁斯卡尔算法为例讨论最小生成树的算法。 【数据描述】 1. 先将所有邻接边依加权值递增用链表链接起来。节点结构: Vertex1 Vertex2 Weight Next 2. 定义一个一维数组 Tree,用于当前存贮生成树集合的顶点是否产生回路。且用 1 表示生成树的顶点, 0 表示非生成树的顶点,若新加入的邻接边中两个顶点都在生成树集合中,表示会产生回路,这样该边落 在同一个连通分量上,应该舍去。 3. 在利用克鲁斯卡尔算法之前建立的链表来加入生成树的邻接边,直到产生 N-1 条边。 【C 源程序】 #include<stdlib.h> #define max 10 5

#define vertexnum struct {

list /*结构定义*/

int vertex1; int vertex2; int weight; struct }; typedef struct list Node; /*定义邻接边的结点*/ type Node *edge; list *next;

int edges[10][3]={{1,2,7},{1,3,6},{1,4,5},{1,5,12},{2,3,14},{2,4,8},{2,5,8}, {3,4,3}{3,5,9 },{4,5,2}}; /*针对图 G3 的结点数据以及权值*/ int visited[vertexnum]; void kruskal(edge head)

{edge pointer; int edgenum=0; /*已连结边的数目*/ int weight=0; pointer=head; while(edgenum!=(vertexnum-1))/*当边的数目为顶点数少 1 时,结束循环*/ {if (visited[pointer->vertex1]==0||visited[pointer->vertex2]==0) {printf("==>[%d,%d] ",pointer->vertex1,pointer->vertex2);

printf("(%d)",pointer->weight); weight+=pointer->weight; edgenum++; visited[pointer->vertex1]=1; /*设为已访问*/ visited[pointer->vertex2]=1; } pointer=pointer->next; /*下一个结点*/ if(pointer==NULL) {printf("no treen"); break; } }

printf("ntotal weight is %d",weight);/*输出加权值总和*/ } void print_edge(edge head) /*输出链表数据*/

{edge pointer; pointer=head; while( pointer!=NULL) /*当结点为 NULL 时结束循环*/ ",pointer->vertex1,pointer->vertex2);

{printf("[%d,%d] printf("(%d)

",pointer->weight);/*输出权值*/

pointer=pointer->next; } printf("n"); } edge insert_edge(edge head,edge new)/*插入邻接边到链表内*/

{edge pointer; pointer=head; /*pointer 设为首结点*/ while(1) { if (new->weight<head->weight)/*新的加权值比首结点值小*/

{new->next=head; /*插入在首结点之前*/ head=new; break; } if(new->weight>=pointer->weight&&new->weight<pointer->next->weight) {new->next=pointer->next; pointer->next=new; break; } pointer=pointer->next; } return } head;

void

free_edge(edge

head)

{edge pointer; while(head!=NULL) { pointer=head;

head=head->next; free(pointer); } } edge create_edge(edge head) /*建立链表*/

{edge new,pointer; int i; head=(edge)malloc(sizeof(Node)); if (head==NULL) printf("memory else {head->vertex1=edge[0][0]; head->vertex2=edge[0][1]; head->next=NULL; for(I=1;I<10;I++) {new=(edge)malloc(sizeof(Node)); if (new!=NULL) {new->vertex1=edges[i][0]; /*定义结点加权值*/ new->vertex2=edges[i][1]; new->weight=edges[i][2]; new->next=NULL; head=insert_edge(head,new); /*插入新结点*/ } } } return head; failure! ");

} void { edge head; main()

int i; for (I=0;i<vertexnum;i++) /*对所有的访问顶点清 0*/ visited[i]=0; head=create_edge(head); /*调用建立链表*/ if { (head!=NULL) printf("first step:sortingn");

print_edge(head); printf("second step:find the lest treen");

kruskal(head); /*调用克鲁期卡尔算法*/ free_edge(head); } } 【实验题】 1. 参考上述算法,编程实现利用 Prim 算法构造最小生成树的程序。 2. 现在市政府计划在某个区域内的城市之间建立高速公路,以使得其中任意两个城市之间都有直接的或 间接的高速公路相连。当然,从经济的角度出发,政府希望所有的修路费用之和最小,其中修路费与公路 长度成正比,不妨设为每千米一个单位费用。 输入文件: 第一行是一个整数 N(N<=100),表示区域内城市的数目; 第二行到 N+1 行每行是两个数 Xi,Yi(都大于等于 0)表示第 i 个城市的坐标。 输出文件:只有 1 个数,表示最小费用。

第四节 拓扑排序实验
【问题描述】 有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况外,几乎所有的工程都可分为 若干个活动,而这些活动之间,通常受着一些条件的约束,若其中某些活动的开始必须在另外一些活动完

成之后。对整个工程或系统,人们关心两个方面的问题:一是工程能否顺利进行;二是估算整个工程或系 统所必须的最短时间,对应于有向图,则为进行拓扑排序和关键路径的操作。下面首先讨论拓扑排序问题, 所谓拓扑排序是指由集合上一个偏序得到该集合上的一个全序的运算。 一、拓扑排序算法思想: 1. 在有向图中任选一个没有前趋的顶点输出; 2. 从图中删除该顶点和所有以它为尾的弧; 3. 重复上述1、2,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到图中 没有无前趋的顶点为止,此情形表明有向图中存在环。 该算法的时间复杂度为O(n+e)。

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 

数据结构实验指导书 - 数据结构 实验指导书 院别 专业 班级 姓名 计算机学院编 实验一 线性表的顺序存储实验 一、实验目的及要求 1、掌握在TC环境下调试顺序表...

数据结构与算法实验指导书90969 - 数据结构与算法实验指导书 计算机与信息学院 实验一 【实验目的】 顺序表 熟练掌握线性表在顺序存储结构上的基本操作。 【实验...

数据结构实验指导书02 很好!很好!隐藏&gt;&gt; 实验二 2.1 实验目的: 线性表 (1)掌握线性表的顺序存储结构的定义及 C 语言实现。 (2)掌握线性表在顺序存储结构即...

数据结构实验说明书新版 - the principl e of simplified E IA of constr uction pr oject s in the regi on. In te...

数据结构实验指导书 - 数据结构实验指导(C语言版)... 数据结构实验指导书_IT/计算机_专业资料。数据结构实验指导(C语言版) 数据结构实验指导书 江西农业大学计算机与...

数据结构试验指导书V2[1].0 - V 2.0 数据结构与算法 实验指导书 编写: 编写:陆绍飞 校核: 校核:___ 湖南大学软件学院 2011 年 9 月 湖南大学软件学...

数据结构实验指导书(2012.9) - 1.2 实验报告(文档)书写规范 实验报告(文档)应包括以下 7 个方面的内容: 1、问题分析 根据对实验任务的理解, 以无歧义的陈述...

09级《数据结构》实验指导书 - 《数据结构实验指导书》 潘向辉/吴学毅编写 印包学院数字媒体技术专业 2011 年 3 月 实验说明 实验说明 【实验环境】 操作系统:...

空间数据结构基础实验指导书 隐藏&gt;&gt; 《空间数据结构基础》 课程实习指导书实习周数:2 周 学分数:2 一、实习目的 数据结构是一门重要的专业基础课,其特点是理论...

《数据结构(C 语言版) 》实验指导书(非计算机专业适用) 广州大学 2013.1 目 录 实验一 线性表的顺序存储及其操作... 1 实验二 线性表的链式存储及其操作......


 

热点推荐