实验六 图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 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 【题目四】 最短的旅程 描述 在By teland 有n 个城市（编号从1 到n），它们之间通过双向的道路相连。By teland的国王并不大方，所以，那里只有n -1 条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，starhder 到了编号为 k 的城市。他计划从城市k 开始，游遍城市m1，m2，m3… … ，mj（不一定要按这个顺序旅游）。每个城市mi 都是不同的，并且，也与 k 不同。 Starhder — — 就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k 开始...
