实验4,图
实验 4 4 图 一、实验目的 1.熟练掌握图的概念、特点、存储结构及其实现 2.掌握图的两种遍历算法及在相关存储结构上的实现 3.掌握使用文本文件对图进行存取的方法。
二、实验内容 以下题目任选一个完成即可。
1.个人关系网的设计与实现 编写程序，自行设计数据结构，输入/输出/存储微信等社交网络中的个人关系网，如下图所示。
你至少需实现如下功能：
(1)“新增/修改/删除/查询/显示/存储”用户(2)用户登录(3)登录用户可以"新增/删除/查询/显示/存储”好友信息(4)登录用户可以修改选定好友（一个或多个）的状态，例如，可以设置不同的关系（如夫妻、父子、母女、亲戚、朋友、同学、师生等）、不同的亲密度（如陌生、熟悉等）。需注意关系是相互的，但两个人的亲密度相互之间是可以不一致的，因为有单恋呀。
(5)在这个社交网络中验证所谓的六度空间理论，即“你和任何一个陌生人之间所间隔的人不会超过六个”。方法是：任意输入两个人，判断他们之间的关系，如果有关系直接输出；如果没有，则输出他们之间的联系人及关系，最后输出两人之间的层次数。
2.牧场供水问题 牧民阿森决定给他的 N（1≤N≤300）个牧场供水，这些牧场的编号为 1 至 N。他可以在牧场上建一口井，或者通过管道将牧场与另一个已经有水的牧场连接，从而将水引到牧场。
在牧场上挖一口井要花很多钱（1≤w i ≤100000）。用管道连接牧场 i 和牧场 j 的成本为P ij（1≤P ij ≤100000；P ij =P ji ；P ii =0）。
确定牧民阿森为给他的所有牧场供水所需的最低金额。
你至少需实现如下功能：
(1)“输入/存储/显示”牧场的数量 N(2)“输入/修改/存储/显示”各牧场建水井所需费用 w i，允许用户只修改某牧场的建井费用。
(3)“输入/修改/存储/显示”各牧场间建立管道连接所需费用 P ij 为节约时间，你可以只输入所有那些满足 i>j 的 P ij，剩余元素自动赋定。
允许用户只对某两个牧场间的管道费用进行修改(4)计算最低金额，输出此金额以及相应的建设方案，即输出哪些牧场要建井，哪些牧场间要建管道。
提示：你可以虚设一个起点 0，它到各牧场的管道费用就是各牧场的建井费用。然后使用最小生成树求解。
3.最短路径问题 有九个城市 v 1 ,v 2 ,...,v 9，其高速公路网如图所示，弧旁数字是该公路的长度。有一批货物从 v 1 运到 v 9，问走哪条路最短？ 编程求解上面问题，你至少需实现以下功能：
(1)“输入/存储/显示”城市的数量 N(2)“输入/修改/存储/显示”各城市之间的公路长度 p ij，如果不输入，则认为两城市之间无直接连接，即公路长度为无穷大。两城市之间默认有长度相同的往返路径，但允许往返路径长度不同。修改功能，应允许只对某城市间的公路长度进行修改。
(3)计算输入的两城市间的最短路径长度，并输出最短路径。
(4)分析最短路径上某两点间路径变化对最短路径的影响，即计算出最短路径上各点间长度最多增加多少时，最短路径不变。
4.关键路径问题 已知建设一个汽车库及引道的作业明细表如表所示。
工序代号 工序名称 工序时间/d 紧前工序 a b c d e f g h i j k l m n 清理场地，准备施工 备料 车库地面施工 预制墙及房顶的桁架 车库混凝土地面保养 立墙架 立房顶桁架 装窗及边墙 装门 装天花板 油漆 引道混凝土施工 引道混凝土保养 清理场地，交工验收 10 8 6 16 24 4 4 10 4 12 16 8 24 4 一 一 a,b b c d,e f f f g h,i,j c l k,m 编程求解上面问题，你至少需实现以下功能：
(1)“输入/存储/显示”作业明细；(2)根据工序代号，修改工序信息，包括其名称、时间及紧前工序；(3)计算并显示工程的关键路径、关键工序及总时间；(4)输出工序代号，计算并显示该工序压缩时间或延迟完工对总工期的影响。
三、实验报告要求 1.根据程序要求对运行结果进行分析。如果程序未能调试通过，分析其原因。
2.根据实验步骤，说明未能编译通过的原因，并正确进行修改。
3.总结实验中遇到的问题，并谈谈本次实验的收获与经验。
4.实验报告内容及评分标准参见实验 1。
5.实验报告必须 2019 年 12 月 31 日以前提交到课程中心。
