实验六图的应用及其实现(相关知识点:拓扑排序、关键路径、最小生成树和最短路径)一、实验目的1.进一步功固图常用的存储结构。
2.熟练掌握在图的邻接表实现图的基本操作。
3.理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。
二、实验内容一>.基础题目:(本类题目属于验证性的,要求学生独立完成)[题目一]:从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。
测试数据:教材图7.28[题目二]:从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。
试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。
测试数据:教材图7.29二>.简单应用题目:(ACM/ICPC训练题,本类题目属于设计性的,要求学生三人为一个团队,分工协作完成))【题目三】高速公路描述某国共有n个城市(n不超过200),有些城市之间直接有一条高速公路相连,高速公路都是双向的,总共有m条。
每条高速公路都有自己的载重限制,即载重最大值。
通过车辆的载重不能超过公路的载重限制。
如今我们想了解的是,从某一起点城市出发,到达目标城市,车辆最多能带多重的货物。
输入输入的第一行为两个整数n和m。
以下有m行,每行三个整数描述一条公路,分别是首尾相连的城市以及载重限制。
然后是一个整数k,即问题个数。
接下来k行描述k个问题,每行两个整数表示起点城市和目标城市。
问题数不超过一百。
输出输出包括k行,每行对应一个问题,输出从起点到目标的最大载重量。
如果两城市间无路径则输出-1。
样例输入3 31 2 1002 3 1001 3 5021 32 3样例输出100100【题目四】最短的旅程描述在Byteland有n个城市(编号从1到n),它们之间通过双向的道路相连。
Byteland 的国王并不大方,所以,那里只有n -1条道路,但是,它们的连接方式使得从任意城市都可以走到其他的任何城市。
一天,starhder到了编号为k的城市。
他计划从城市k开始,游遍城市m1,m2,m3……,mj(不一定要按这个顺序旅游)。
每个城市mi都是不同的,并且,也与k不同。
Starhder ——就像每一个旅行家一样,携带的钱总是有限的,所以,他要以最短的路程旅行完所有的城市(从城市k开始)。
于是,他请你帮助计算一下,旅游完上述的城市最短需要多少路程。
输入第一行包含两个整数,上文中的n和k,以一个空格隔开。
(2<= n <=50000,1 <= k <=n),下面的n- 1行每行描述一条路,第i + 1行包含3个整数ai,bi,di,相邻两个数用一个空格隔开(1<= ai,bi <= n,1<= di <= 1000),ai和bi是用道路直接相连的城市编号,di是这条道路的长度。
第n + 1行包含一个整数j,是starhder要旅游的城市数(1<= j <= n - 1),接下来一行包含j个不同的整数m1,m2,……,mj,每两个相邻的整数用一个空格隔开,表示starhder想要去的城市。
(1<= mt<=n,mt <> k)。
输出输出只有一行,包含一个整数:starhder旅游的最短路程。
样例输入4 21 2 14 2 22 3 321 3样例输出5【题目五】连通OR 不连通描述:给定一个无向图,一共n个点,请编写一个程序实现两种操作:D x y 从原图中删除连接x,y节点的边。
Q x y 询问x,y节点是否连通输入第一行两个数n,m(5<=n<=40000,1<=m<=100000)接下来m行,每行一对整数x y (x,y<=n),表示x,y之间有边相连。
保证没有重复的边。
接下来一行一个整数q(q<=100000)以下q行每行一种操作,保证不会有非法删除。
输出按询问次序输出所有Q操作的回答,连通的回答C,不连通的回答D样例输入3 31 21 32 35Q 1 2D 1 2Q 1 2D 3 2Q 1 2样例输出CCD【题目六】Sort ProblemAn ascending sorted sequence of distinct values is one in which some form of a less-than operator isused to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.【Input】Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.【Output】For each problem instance, output consists of one line. This line should be one of the following three:Sorted sequence determined: y y y… y.Sorted sequence cannot be determined.Inconsistency found.y y y… y is the sorted, ascending sequence.Sample Input Sample Output4 6 Sorted sequence determined: A B C D.A<B Inconsistency found.A<C Sorted sequence cannot be determined.B<CC<DB<DA<B3 2A<BB<A26 2A<ZD<S0 0设计要求:(上述题目可任选一个)1、上机前,认真学习教材,熟练掌握AOV网、AOE网的构造和拓扑排序算法。
2、上机前,认真独立地写出本次程序清单,流程图,该程序包括图类型以及每一种操作的具体的函数定义和主函数。
有关算法分别参阅讲义和参考教材事例图的存储结构定义#define INFINITY INT_MAX //定义无穷大∞#define MAX_VERTEX_NUM 20typedef struct ArcNode // 表结点定义{ int adjvex; //邻接点域,存放与Vi邻接的点在表头数组中的位置struct node *nextarc;//链域,指示依附于vi的下一条边或弧的结点,}ArcNodetypedef struct VNode //表头结点{ int vexdata; //存放顶点信息struct ArcNode *firstarc; //指示第一个邻接点}VNode,AdjList[MAX_VERTEX_NUM];typedef struct { //图的结构定义AdjList vertices; //顶点向量int vexnum, arcnum;GraphKind kind; // 图的种类标志} MGraph;Int indegree[MAX_VERTEX_NUM];相关函数声明:1、/* 输入图的顶点和边的信息,建立图*/void CreateGraph(MGraph &G)2、/* 其他相关函数*/三、实验步骤㈠、数据结构与核心算法的设计描述㈡、函数调用及主函数设计(可用函数的调用关系图说明)㈢程序调试及运行结果分析㈣实验总结四、主要算法流程图及程序清单1、主要算法流程图:2、程序清单(程序过长,可附主要部分)。