数据结构 图的应用及其实现

实验六 图的应用及其实现

（相关知识点：拓扑排序、关键路径、最小生成树和最短路径）

一、实验目的

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 3

1 2 100 2 3 100 1 3 50 2 1 3 2 3

样例输出 100 100

【题目四】 最短的旅程 描述

在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 2 1 2 1 4 2 2 2 3 3 2 1 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 3 1 2 1 3 2 3 5

Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出

C C D

【题目六】 Sort Problem

An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used 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 Output

4 6 Sorted sequence determined: A B C D. A

A

设计要求：（上述题目可任选一个）

1、上机前，认真学习教材，熟练掌握AOV网、AOE网的构造和拓扑排序算法。

2、上机前，认真独立地写出本次程序清单，流程图，该程序包括图类型以及每一种操作的具体的函数定义和主函数。有关算法分别参阅讲义和参考教材事例

图的存储结构定义

#define INFINITY INT_MAX //定义无穷大∞ #define MAX_VERTEX_NUM 20

typedef struct ArcNode // 表结点定义

{ int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *nextarc; //链域，指示依附于vi的下一条边或弧的结点，

}ArcNode

typedef 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、程序清单

（程序过长，可附主要部分）