第七章 图_作业2.doc_第1页
第七章 图_作业2.doc_第2页
第七章 图_作业2.doc_第3页
第七章 图_作业2.doc_第4页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

计算机科学与技术学院 计算机科学与技术专业 3010216001 张三 一班第七章 图2一、应用题1证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。2请回答下列关于图(Graph)的一些问题：（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边? （2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？3有向图的邻接表存储如下：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。4某田径赛中各选手的参赛项目如右表:姓名参赛项ZHAOABEQIANCDSHUNCEFLIDFAZHOUBF设项目A ,B ,，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件)。（1）根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构;（2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。5下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。6用最短路径算法，求如下图中a到z的最短通路。65ced4bfghijza22496142231234598297（1）对于有向无环图，叙述求拓扑有序序列的步骤；（2）对于以下的图，写出它的四个不同的拓扑有序序列。217436588下表给出了某工程各工序之间的优先关系和各工序所需时间（1）画出相应的AOE网。（2）列出各事件的最早发生时间，最迟发生时间。（3）找出关键路径并指明完成该工程所需最短时间。工序代号ABCDEFGHIJKLMN所需时间15105081540300151206015302040先驱工作-A,BBC,DBEG,IEIF,IH,J,KLG二、算法设计题1设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1n或0n-1编号） 2写出从图的邻接表表示转换成邻接矩阵表示的算法。3已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 4试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)5令G=（V，E）为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论