当前位置：文档之家 › 数据结构最小生成树课程设计

数据结构最小生成树课程设计

  • 格式：pdf
  • 大小：383.04 KB
  • 文档页数：27

下载文档原格式

  / 27

合集下载

最小生成树 实验报告

最小生成树 实验报告

最小生成树实验报告最小生成树实验报告一、引言最小生成树是图论中的一个重要概念，它在实际问题中有着广泛的应用。

本次实验旨在通过编程实现最小生成树算法，并通过实验数据对算法进行分析和评估。

二、算法介绍最小生成树算法的目标是在给定的带权无向图中找到一棵生成树，使得树上所有边的权重之和最小。

本次实验我们选择了两种经典的最小生成树算法：Prim 算法和Kruskal算法。

1. Prim算法Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展生成树的规模，直到包含所有顶点为止。

算法的具体步骤如下：（1）选择一个起始顶点，将其加入生成树中。

（2）从与生成树相邻的顶点中选择一个权重最小的边，将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法Kruskal算法是一种基于并查集的贪心算法，它首先将图中的边按权重从小到大进行排序，然后逐个加入生成树中，直到生成树包含所有顶点为止。

算法的具体步骤如下：（1）将图中的边按权重从小到大进行排序。

（2）逐个加入边，如果该边的两个顶点不在同一个连通分量中，则将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

三、实验过程本次实验我们使用C++语言实现了Prim算法和Kruskal算法，并通过随机生成的图数据进行了测试。

1. Prim算法的实现我们首先使用邻接矩阵表示图的结构，然后利用优先队列来选择权重最小的边。

具体实现过程如下：（1）创建一个优先队列，用于存储生成树的候选边。

（2）选择一个起始顶点，将其加入生成树中。

（3）将与生成树相邻的顶点及其边加入优先队列。

（4）从优先队列中选择权重最小的边，将其加入生成树中，并更新优先队列。

（5）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法的实现我们使用并查集来维护顶点之间的连通关系，通过排序后的边序列来逐个加入生成树中。

具体实现过程如下：（1）将图中的边按权重从小到大进行排序。

数据结构(Java版)图2(最小生成树)

数据结构(Java版)图2(最小生成树)

最小生成树举例
A
50 60 52 65 50
C
45 42 30 50
A
C
45
B
40
D
G
B
40 50
D
42 30
G
E
70
F
E
F
(a) 无向带权连通图G
(b) 无向带权图G 的最小生成树T
从最小生成树的定义可知，构造n个顶点的无向带权连 通图的最小生成树，必须满足如下三个条件： ① 必须包含n个顶点。 ② 有且仅有n-1条边。 ③ 没有回路。
）
将ej边加入到tree中；
}
实践项目

设计一个程序实现Prim和Kruskal算法.
表5-1 lowcost[ ]数组数据变化情况 表5-2 closest[ ]数组数据变化情况
扫描次数
closest[0]
closest[1]
closest[2]
closest[3]
closest[4]
closest[5]
求最小生成树算法

普里姆算法（Prim） (从点着手)

适合于求边稠密的最小生成树 适合于求边稀疏的最小生成树

克鲁斯卡尔算法（Kruskal）（从边着手）

普里姆算法（Prim）思想
1.
2.
3.
4.
令集合U=｛u0｝（即从顶点u0开始构造最小生 成树），集合T=｛｝。 从所有顶点u∈U和顶点v∈V-U的边权中选择最 小权值的边(u,v)，将顶点v加入到集合U中，边 (u,v)加入到集合T中。 如此重复下去，直到U=V时则最小生成树构造完 毕。 此时集合U就是最小生成树的顶点集合，集合T 就是最小生成树的边集。

数据结构课程设计pdf

数据结构课程设计pdf

数据结构课程设计 pdf一、课程目标知识目标：1. 让学生掌握数据结构的基本概念，包括线性表、栈、队列、树、图等；2. 使学生了解不同数据结构的特点，并能运用其解决实际问题；3. 引导学生掌握常见数据结构的相关算法，如排序、查找等。

技能目标：1. 培养学生运用数据结构描述问题的能力，提高编程实现复杂问题的技能；2. 培养学生具备分析算法复杂度，选择合适数据结构和算法解决问题的能力；3. 提高学生的团队协作能力，通过小组讨论和项目实践，培养学生的沟通表达能力和协作精神。

情感态度价值观目标：1. 激发学生对计算机科学的兴趣，培养学生主动探索、勇于创新的精神；2. 培养学生具备良好的学习习惯，严谨的学术态度，对待问题敢于质疑、善于思考；3. 引导学生认识到数据结构在实际应用中的重要性，提高学生的专业认同感。

本课程针对高中年级学生，结合数据结构课程性质，注重理论与实践相结合，培养学生解决实际问题的能力。

考虑到学生的年龄特点，课程设计力求生动有趣，以激发学生的学习兴趣。

在教学过程中，注重启发式教学，引导学生主动探索、积极思考，提高学生的综合素质。

通过本课程的学习，期望学生能够达到上述课程目标，为后续计算机科学课程打下坚实基础。

二、教学内容1. 线性表：介绍线性表的定义、特点和基本操作，包括顺序存储和链式存储的实现方法。

教材章节：第一章第一节进度安排：2课时2. 栈和队列：讲解栈和队列的基本概念、性质以及应用场景，实现顺序栈和链栈、循环队列等。

教材章节：第一章第二节进度安排：3课时3. 树和二叉树：阐述树和二叉树的基本概念、性质、存储结构及遍历方法，包括二叉排序树、平衡二叉树等。

教材章节：第二章进度安排：5课时4. 图：介绍图的定义、存储结构、遍历算法以及最短路径、最小生成树等算法。

教材章节：第三章进度安排：5课时5. 排序与查找：讲解常见排序算法（冒泡、选择、插入等）和查找算法（顺序、二分、哈希等），分析其算法复杂度。

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)

算法设计与分析课程设计报告学院计算机科学与技术专业计算机科学与技术年级2011姓名XXX学号2013年5 月19 日题目：最小生成树问题的算法实现及复杂度分析摘要：该程序操作简单，具有一定的应用性。

数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。

而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。

最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。

本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。

构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。

引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。

这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。

n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。

现在要选择这样一棵生成树，也就是使总的代价最小。

这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。

最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。

一棵生成树的代价就是树上各边的代价之和。

而实现这个运算的经典算法就是普利姆算法。

正文普里姆（Prim）算法思想普里姆算法则从另一个角度构造连通网的最小生成树。

最小生成树问题课程设计

最小生成树问题课程设计

最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。

技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。

情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。

课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。

学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。

教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。

通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。

二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。

参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。

《数据结构》课程设计

《数据结构》课程设计

《数据结构》课程设计一、课程目标《数据结构》课程旨在帮助学生掌握计算机科学中基础的数据组织、管理和处理方法，培养其运用数据结构解决实际问题的能力。

课程目标如下：1. 知识目标：（1）理解基本数据结构的概念、原理和应用，如线性表、栈、队列、树、图等；（2）掌握常见算法的设计和分析方法，如排序、查找、递归、贪心、分治等；（3）了解数据结构在实际应用中的使用，如操作系统、数据库、编译器等。

2. 技能目标：（1）能够运用所学数据结构解决实际问题，具备良好的编程实践能力；（2）掌握算法分析方法，能够评价算法优劣，进行算法优化；（3）能够运用数据结构进行问题建模，提高问题解决效率。

3. 情感态度价值观目标：（1）激发学生对计算机科学的兴趣，培养其探索精神和创新意识；（2）培养学生团队合作意识，学会与他人共同解决问题；（3）增强学生的责任感和使命感，使其认识到数据结构在信息技术发展中的重要性。

本课程针对高中年级学生，结合学科特点和教学要求，将目标分解为具体的学习成果，为后续教学设计和评估提供依据。

课程注重理论与实践相结合，旨在提高学生的知识水平、技能素养和情感态度价值观。

二、教学内容《数据结构》教学内容依据课程目标进行选择和组织，确保科学性和系统性。

主要包括以下部分：1. 线性表：- 线性表的定义、特点和基本操作；- 顺序存储结构、链式存储结构及其应用；- 线性表的相关算法，如插入、删除、查找等。

2. 栈和队列：- 栈和队列的定义、特点及基本操作；- 栈和队列的存储结构及其应用；- 栈和队列相关算法，如进制转换、括号匹配等。

3. 树和二叉树：- 树的定义、基本术语和性质；- 二叉树的定义、性质、存储结构及遍历算法；- 线索二叉树、哈夫曼树及其应用。

4. 图：- 图的定义、基本术语和存储结构；- 图的遍历算法，如深度优先搜索、广度优先搜索；- 最短路径、最小生成树等算法。

5. 排序和查找：- 常见排序算法，如冒泡、选择、插入、快速等；- 常见查找算法，如顺序、二分、哈希等。

最小生成树问题

榆林学院12届课程设计《最小生成树问题》课程设计说明书学生姓名：赵佳学号：1412210112院系：信息工程学院专业：计算机科学与技术班级：计14本1指导教师：答辩时间：年月日最小生成树问题一、问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

二、需求分析1.在n个城市之间建设网络，只需保证连通即可。

2.求城市之间最经济的架设方法。

3.采用多种存储结构，求解算法也采用多种。

三、概要设计1、功能模块图2、功能描述（1)CreateUDG()创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。

（2)Switch()功能选择：给用户提示信息，让用户选择相应功能。

（3)Adjacency_Matrix()建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。

（4)Adjacency_List()建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。

（5)MiniSpanTree_KRSL()kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。

（6)MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。

四、详细设计本次课程设计采用两种存储结构以及两种求解算法。

1、两种存储结构的存储定义如下：typedef struct Arcell{double adj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{char vexs[MAX_VERTEX_NUM]; //节点数组AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前节点数和弧数}MGraph;typedef struct Pnode //用于普利姆算法{ char adjvex; //节点double lowcost; //权值}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{char ch1; //节点1char ch2; //节点2double value;//权值}Knode,Dgevalue[MAX_VERTEX_NUM];2、求解算法采用Prim算法和Kruskal算法。

《数据结构》课程设计 普里姆算法 最小生成树

printf("(%d %d %d)\n",lge[i].start_vex,lge
[i].stop_vex,lge[i].weight); /*输出N-1条最小边的信息*/
for(i=0;i<12;i++)
{
line(vex[lge[i].start_vex][0],vex[lge[i].start_vex][1],vex[lge
lge[min]=lge[i];
lge[i]=edge;
vx=lge[i].stop_vex;
for(j=i+1; j<pgraph->n-1; j++)
{
vy=lge[j].stop_vex;
weight=pgraph->arcs[vx][vy];
if(weight<lge[j].weight)
{
{550,250},{520,330},{430,400},{350,450},{270,400},{200,330}};
/*初始化个顶点的坐标*/
int info[12][12];
char *text;
void initalGraph(int vec[][2]) /*画出顶点函数*/
{
int gd=DETECT,gm;
[i].stop_vex][0],vex[lge[i].stop_vex][1]);
}
/*根据生成的最小边数组连线*/
printf("---It is done!---");
getch();
exit(1);
}
此程序再TURBOC2.0环境中编译通过运行.TURBOC2.0下载的地址

数据结构：第7章 图3-最小生成树


• 按照生成树的定义，n 个顶点的连通网络的生成树有 n
个顶点、n-1 条边。
即有权图
目标：
在网络的多个生成树中，寻找一个各边权值之和最小的
生成树。
构造最小生成树的准则 ❖ 必须只使用该网络中的边来构造最小生成树；
❖ 必须使用且仅使用n-1条边来联结网络中的n个顶点；
❖ 不能使用产生回路的边。
典型用途：
(b) u={1} w={2,3,4,5,6}
0 6 1 5
6
0
5
3
1 5 0 7 5 4
5
7
0
2
3 5 0 6
4 2 6 0
i
1234
closest[i] 1 1 1 1
lowcost[i] 0 6 1 5
56 11 ∞∞
closest用于存放顶点序号 lowest存放权值
15 4 6
1 25
3
54
5
6
(c ) u={1,3} w={2,4,5,6}
1
1
4
25
6
32
54
5
6
(d) u={1,3,6} w={2,4,5}
i
1234 5 6
closest[i] 1 3 1 1 3 3
lowcost[i] 0 5 0 5 5 4
i
1234 5 6
closest[i] 1 3 1 6 3 3
生
v3 v1
成
树 v4 v2
v1
0^ 1^ 0^ 1^
2．生成森林
若一个图是非连通图或非强连通图，但有若 干个连通分量或若干个强连通分量，则通过 深度优先搜索遍历或广度优先搜索遍历，不 可以得到生成树，但可以得到生成森林，且 若非连通图有 n 个顶点，m 个连通分量或强 连通分量，则可以遍历得到m棵生成树，合 起来为生成森林，森林中包含n-m条树边。

2012级计科专业《算法与数据结构》课程设计题

2012级计科专业《算法与数据结构》课程设计题指导教师:宗瑜指导题目:题目 1、最小生成树问题问题描述:给定一个地区的 n 个城市间的距离网,用 Prim 算法或 Kruskal 算法建立最小生成树,并计算得到的最小生成树的代价。

基本要求:(1城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。

(2表示城市间距离网的邻接矩阵(要求至少 6个城市, 10条边(3要求在屏幕上显示得到的最小生成树中包括哪些城市间的道路及其权值,并显示得到的最小生成树的代价。

题目 2、哈希表的设计与实现问题描述:设计哈希表实现电话号码查询系统。

基本要求:(1设每个记录有下列数据项:电话号码、用户名;(2从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;(3采用线性探测再散列处理冲突;(4查找并显示给定电话号码的记录;(5查找并显示给定用户名的记录。

选做内容:在哈希函数确定的前提下, 尝试各种不同类型处理冲突的方法 (至少两种 , 考察平均查找长度的变化。

题目 3、排序算法包的实现问题描述:用程序实现快速排序、堆排序和归并排序将一组随机数列按非递减的顺序排列。

基本要求:(1待排序列为由随机函数生成的一组整数数列。

(2程序以用户和计算机的对话方式执行,即在屏幕上显示所能进行的操作,用户根据提示输入相应命令,计算机处理完毕将运算结果在屏幕上显示,并等待用户的后续操作。

选做内容:实现希尔排序和基数排序。

要求:图形界面设计题目 4、任意长的整数加减器问题描述:设计一个程序实现两个任意长的整数的求和运算。

基本要求:利用双向循环链表,设计一个实现任意长的整数进行加法运算的演示程序。

要求输入和输出每四位一组,组间用逗号隔开。

如:1, 0000, 0000, 0000, 0000。

指导教师:金萍指导题目:题目 1、迷宫求解问题描述:以一个 m ×n 的长方形表示迷宫, 0和 1分别表示迷宫中的通路和障碍。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
目录
一、课题描述： 二、需求分析 三、总体结构设计 四、各子模块设计 五、编程设计 六、测试结果 七、总结 八、参考文献 附 录
一、课题描述：
设计一张城市地图，图中的顶点为城市，无向边代表两个城市间的 连通关系，边上的权代表公路造价。图中任一对城市都是连通的，用公 路把所有城市联系起来，设计可使得工程的总造价最少。
n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("<< %s, %s >> %d\n", vex[edges[i].begin].name, vex[edges[i].end].name, edges[i].weight); Mincost+=edges[i].weight; } } printf("使各城市间公路总造价的最小费用为： Mincost=%d\n",Mincost); } int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; } 3．用冒泡法对公路造价按从小到大的顺序排列 void sort(edge edges[] ,MGraph *G) { int i, j; int temp; for ( i = 1; i < G->arcnum; i++) { for ( j = i+1; j &3;) { if (edges[i].weight > edges[j].weight) { temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end;
typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph;
时间复杂度0(n^2)
算法描述 该算法是建立一个带权的无向图，并用Kruskal算法求该图的最小生成 树，用父结点和子女结点集的形式输出最小生成树。 1.无向带权图的建立 图的存储结构如上所示，;用adj是否为1判断两城市间是否有公路，adj 为1时表示有公路，反之没有公路，vexnum和arcnum分别表示城市数和 公路数，name和num分别表示城市信息和城市序号，建图的算法如下所 示： void CreatGraph(MGraph *G) { int i, j,n,h,m,k; char u[MAX],v[MAX]; printf("请输入公路数和城市数:"); scanf("%d %d",&G->arcnum,&G->vexnum) for (i = 1; i <= G->vexnum; i++)//初始化图 { for ( j = 1; j <= G->vexnum; j++) {
edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } } }
六、测试结果
城市间公路及其造价的输出结果
N N
Y Y
N N Y Y
N N i<=G->vexnum printf(“<%s,%s> %d\n”,vex…); i++ i<=G->vexnum printf(“<%s,%s> %d\n”,vex…); i++ Y Y
五、编程设计
存储结构 该函数包含三个结构体，即存储城市、存储公路和存储图的结构体，其 结构体分别如下所示： 1.顶点和边的存储表示 用字符串name表示城市信息，num表示城市的序号。 struct node{ char name[10]; int num; }vex[20]; 用整型begin和end表示公路的起点和终点，weight表示公路的造价。 typedef struct { int begin; int end; int weight; }edge; 2.图的邻接矩阵存储表示 用整型adj表示城市间的关系，weight表示公路的造价。 typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; 用arc表示邻接矩阵，vexnum和arcnum表示图当前的城市数和公路数。
G->arc[i][j].adj = G->arc[j][i].adj = 0; } } printf("\n请输入城市的信息:"); for(n=1;n<=G->vexnum;n++) { scanf("%s",vex[n].name); vex[n].num=n; } for ( i = 1; i <= G->arcnum; i++) { printf("\n请输入有公路的2个城市:"); scanf("%s",v); scanf("%s",u); for ( k= 1; k <= G->vexnum; k++) { if(strcmp(v,vex[k].name)==0) {m=vex[k].num;} if(strcmp(u,vex[k].name)==0) {h=vex[k].num;} } G->arc[m][h].adj = G->arc[h][m].adj = 1; getchar(); printf("\n请输入%s与%s之间的公路造价:",vex[m].name, vex[h].name); scanf("%d",&G->arc[m][h].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); }
N N Y Y
N N Y Y
n<=G->vexnum scanf(“%s”,vex[n].name); n++ n<=G->vexnum scanf(“%s”,vex[n].name); n++ N N Y Y
2.用kruskal算法求最小生成树 sort(edges,G) i=1 找公路和公路的造价 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum Int i,j,n,m i=1 sort(edges,G) i=1 找公路和公路的造价 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum Int i,j,n,m i=1
N N Y Y Y N
N
Y Y Y
i<=G->vexnum parent[i]=0; i++ i<=G->vexnum parent[i]=0; i++ N N Y Y
3.用冒泡法排序 printf(“\n公路造价排序为：”) i=1 公路造价排序 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum int i,j; i=1 printf(“\n公路造价排序为：”) i=1 公路造价排序 j++ i++ j=i+1 j<=G->vexnum i<G->vexnum int i,j; i=1
附 录
程序代码 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #define M 20 #define MAX 20 struct node{ char name[10]; int num; }vex[20]; typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc;
三、总体结构设计
功能模块图
无 向 图 的 建 立
最 小 生 成 树 的 求 解
按父 结点 和子 女结 点集 的形 式输 出， 求最 小值,
四、各子模块设计
1.无向图的建立（初始化） printf(“\n请输入城市的信息”) n=1 G->arc[i][j].adj=G->arc[j][i].adj=0 j++ i++ j=1 j<=G->vexnum i<=G->vexnum Int i,j,n,h,m,k i=1 printf(“\n请输入城市的信息”) n=1 G->arc[i][j].adj=G->arc[j][i].adj=0 j++ i++ j=1 j<=G->vexnum i<=G->vexnum Int i,j,n,h,m,k i=1