《数据结构(C语言版)》-第08章-图.ppt

上传人（卖家）：晟晟文业

文档编号：4105108

上传时间：2022-11-11

格式：PPT

页数：136

大小：527.48KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

29 文币

交易提醒：下载本文档，相应价格的文币将全额进入上传人（卖家）的账号。立即下载优惠套餐（点此详情）

【下载声明】
1. 本站全部试题类文档，若标题没写含答案，则无答案；标题注明含答案的文档，主观题也可能无答案。请谨慎下单，一旦售出，不予退换。
2. 本站全部PPT文档均不含视频和音频，PPT中出现的音频或视频标识（或文字）仅表示流程，实际无音频或视频文件。请谨慎下单，一旦售出，不予退换。
3. 本页资料《《数据结构(C语言版)》-第08章-图.ppt》由用户（晟晟文业）主动上传，其收益全归该用户。163文库仅提供信息存储空间，仅对该用户上传内容的表现方式做保护处理，对上传内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知163文库（点击联系客服），我们立即给予删除！
4. 请根据预览情况，自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器，压缩文件请下载最新的WinRAR软件解压。

配套讲稿：: 如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
特殊限制：: 部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
关键词：: 数据结构C语言版数据结构语言版 08

资源描述：: 1、数据结构(C语言版)-第08章_图8.1 图的基本概念 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3v1v2v3v4v1v2v4v5v3v1v2v3v4v1v2v4v5v3v1v2v3v4v1v2v3v4niivD1)(21v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4V1V2V4V5V3V1V2V4V5V3V0V1V3V234567825V0V2V1455064v0v3v4v2v1v5v6ABCDE8.3图的基本存储结构约定约定:V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3
2、V3 ,),(,A 否则否则或者或者如果如果01EjiEjiji,v0v1v3v2v3v1v0v210,njjiA10,njijA10,njjiA10,njijAV0V1V3V234567825V0V2V14550648.3.2邻接表及其实现 v0v1v3v21 2 3 0 2 0 1 3 0 2 V0V1V2V3v0v1v2v31 0 2 0 1 1 v0v1v2v3 1 2 0 2 1 3 v3v1v0v21 2 3 0 2 0 1 3 0 2 V0V1V2V3v0v1v2v31 0 2 0 1 1 ABDC8.3.3邻接多重表 vertexV0V1V3V234567825V0V1V2V3
3、 56 0 1 34 0 2 78 0 3 25 2 3 01238.4 图的遍历 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4V0,V1,V3,V7,V4,V2,V5,V6V0,V1,V4,V7,V3,V2,V5,V6c0c1c3c2c4c5c0c1c3c2c4c58.4.2广度优先遍历 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4c0c1c3c2c4c5QUEUEV0
4、V0V1V1V2V2V3V3V4V4V5V5V6V6V7V7V1V1V2V2V3V3V0V0V4V4V5V5V6V6V7V7 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1/*/*图的广度优先遍历算法 */*程序名bfs.c 函数名bfs()、bfstraverse()*/*/8.5生成树与最小生成树c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5c6c0c1c3c2c4c5c6c0c1c3c2c4c5c6V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V8V7V9V6V58.5.1最小
5、生成树的定义),()(EvuuvwTWABCDEF1010151212876658.5.2最小生成树的普里姆算法ABCDEF1010151212876655ABCDEF107610ABCDEF1015125ABCDEF1015765ABCDEF1015765ABCDEF1076105ABCDEF1076108.5.3最小生成树的克鲁斯卡尔算法 5ABCDEF5ABCDEF65ABCDEF675ABCDEF67105ABCDEF6710108.6最短路径ABDCFE2415288181013始点终点最短路径路径长度A B （A，C，B）19 C （A，C）4 D （A，C，F，D）25 E
6、（A，C，B，E）29 F （A，C，F）1248.6.1单源最短路径 ABDCFE241528818101348.6.2所有顶点对的最短路径2 弗洛伊德算法的基本思想弗洛伊德算法的基本思想203168359142DD-1D0D1D2D301230123012301230123001 401 401 10 301 10 301931 092 092 092 12 092 11 0822350834073406340634063 60 60 609 10 609 10 60PP-1P0P1P2P301230123012301230123010-1 0-1 0-1 0-1 011-1 011-1
7、 0311-1-1 11-1-1 11-1-1 112-1 113-1 31222-1 220-1 020-1 120-1 120-1 13-1-1 3-1-1-1 3-1-1-1 3-1 223-1 223-18.7 拓扑排序 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6课程代号课程名称先修课程C0C1C2C3C4C5C6C7C8高等数学信息技术基础离散数学数据结构程序设计语言编译原理操作系统电子线路基础计算机组成原理无无C0，C1C2，C4C
8、1C3，C4C3，C8C0C7C0C2C1C7C8C6C3C4C5拓扑排序的过程C0C1C2C3C4C5C1C2C5C3C0C2C5C1C3C0C1C2C3C4C5C1C2C5C5C1C5 C0 C1 C2 C3 0 C4 C5 0012345130103 1 3 0 5 1 5 0 0 1 5 0C0C1C2C3C4C58.8 关键路径要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到关键路径.例如，下图就是一个AOE网。V3V1a a4=34=3a a1=31=3a a2=22=2a a6=36
9、=3a a5=45=4a a3=23=2a a7=27=2a a8=18=1顶点表示事件顶点表示事件边表示活动边表示活动事件事件VjVj发生表示发生表示 akj已结束已结束ak VjVi事件事件ViVi发生表示发生表示 ak可以开始可以开始 V2V4V5V6v0v1v2v4v3v6v7v8v5v9a0=8a1=6a2=7a3=3a4=10a5=9a6=9a7=13a11=2a10=8a9=19a8=4a13=14a12=6a14=10)()11(,)(maxipjnivvjveij持续的时间活动vi)()20)(,()(minisjnivvlenjvjilvi顶点vevl活动ell-e关键活动v0v1v2v3v4v5v6v7v8v9 0861672016203545 013616163127293545 a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14000866771616161620203550913618181627162727293135509501211911011119110

展开阅读全文