图论实验指导书范文.doc

《图论实验指导书范文.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图论实验指导书范文　　图与网络实验指导书（信息与计算科学本科）福建工程学院数理系专业数学教研室陈翠编xx年6月1目录实验一最短道路2实验二最小树3实验三中国邮路问题4实验四最大流52实验一最短道路实验学时2学时　　一、背景知识:最短道路的定义及Dijkstra算法。　　二、目的要求1．掌握图的存储思想及其存储实现。　　2．掌握用图论的知识解决优化问题。　　3．会用Dijkstra算法的思想及其编程实现最短路问题。　　三、实验内容1．输入一组整型元素序列，建立图的存储实现表，图中各边),(jivv有权ijl（ijl=∞表示iv，jv之间没有边

2、）。　　2．实现该表的遍历。　　3．实现把某点作为起点1，搜索由1出发的可达顶点的最小道路，并把其长度记为)1(L=???),(jivvijl。　　4.在该顺序表中进行顺序查找，最后求一条道路?，使它是从sv到tv的所有路中总权最小的路。　　终止。　　四、实验要求1．认真预习，实验前做好准备工作。　　2．上机调试、运行程序。　　3．保存程序的运行结果，并结合程序进行分析。　　4．提交纸质实验报告（使用学校统一实验报告封面）(包括源程序和运行结果)。　　3实验二最小树实验学时2学时　　一、背景知识树、生成树的概念及生成树的求法。　　二、目的要

3、求1．掌握图的存储思想及其存储实现。　　2．掌握最小生成树的两个经典算法Kruskal(克鲁斯卡尔)和Prim(普里姆)算法的思想。　　2．掌握应用算法的程序实现。　　三、实验内容图论中最小生成树问题的算法在现实中有着非常广泛的应用，本实验项目要求学生掌握关于最小生成树的两个经典算法Kruskal(克鲁斯卡尔)和Prim(普里姆)，画出两个算法的流程图，使用C语言、Matlab软件或lingo软件编程实现。　　1．确定有向图的点数、边数、及各边的权；2．把各边的权按从小到大排序，搜索最小的二边；3．依次序加边，不构成圈，留下，继续找下一边。

4、　　4．若不存在不构成圈的边，则终止。　　四、实验要求1．认真预习，实验前做好准备工作。　　2．上机调试、运行程序。　　3．保存程序的运行结果，并结合程序进行分析。　　4．提交纸质实验报告（使用学校统一实验报告封面）(包括源程序和运行结果)。　　4*实验三中国邮路问题实验学时2学时(选做)　　一、背景知识图的存储、建立、遍历及其应用。　　二、目的要求1．掌握图的存储思想及其存储实现。　　2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。　　3．掌握用指针类型描述、访问和处理二叉树的运算4．掌握二叉树的常见算法的程序实现。　　三、实

5、验内容1．输入一组整型元素序列，建立图的存储表(点、边、权，度)。　　2．实现该存储表的遍历。　　3．在该存储表中进行顺序查找某一元素(度),查找成功返回1,否则返回0。　　4．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。　　5．每对奇数点找最短路(实验一)，搜索所有奇数点对的路长和最小的配对，加同权的边。　　6．实现无向图的深度遍历。　　四、实验要求1．认真预习，实验前做好准备工作。　　2．上机调试、运行程序。　　3．保存程序的运行结果，并结合程序进行分析。　　4．提交纸质实验报告（使用学校统一实验报告封面）(包括源程

6、序和运行结果)。　　5实验四最大流实验学时2学时　　一、背景知识网络的流的定义、最大流最小割定理及其应用。　　二、目的要求1．掌握图的存储思想及其存储实现。　　2．掌握用网络的工具解决最大流问题。　　3．掌握最大流的标号法算法的思想及其程序实现。　　三、实验内容1．确定原始网络点数、边数、运行网络容量和网络初始零流；2．取出可行边，搜索由1出发的可达顶点，若n可达，找可增广路；3．确定增广路上的边，修改流和容量，继续找可增广路。　　4．若不存在可增广路，则终止。　　五、实验要求1．认真预习，实验前做好准备工作。　　2．上机调试、运行程序。　

7、　3．保存程序的运行结果，并结合程序进行分析。　　4．提交纸质实验报告（使用学校统一实验报告封面）和(包括源程序和运行结果)。　　　　内容仅供参考