《数据结构第08章图ppt课件》由会员分享，可在线阅读，更多相关《数据结构第08章图ppt课件（135页珍藏版）》请在装配图网上搜索。
1、 V0 V0 V4 V4 V3 V3 V1 V1 V2 V2 V0 V0 V1 V1 V2 V2 V3 V3v1v2v3v4v1v2v4v5v3v1v2v3v4v1v2v4v5v3v1v2v3v4v1v2v3v4niivD1)(21v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4V1V2V4V5V3V1V2V4V5V3V0V1V3V234567825V0V2V1455064v0v3v4v2v1v5v6ABCDE商定商定:G=G=是图是图,V=v0,v1,v2,vn-1,V=v0,v1,v2,vn-1,设顶点的设顶点的 角标为它的编号角标为它的编号 如何表示顶点间
2、的关系？V0 V0 V4 V4 V3 V3 V1 V1 V2 V2 V0 V0 V1 V1 V2 V2 V3 V3 ,),(,A 否否则则或或者者如如果果01EjiEjiji,v0v1v3v2v3v1v0v210,njjiA10,njijA10,njjiA10,njijAV0V1V3V234567825V0V2V1455064v0v1v3v21 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 ABD
3、C mark vexi linki vexj linkjvertex FirstedgeV0V1V3V234567825V0V1V2V3 56 0 1 34 0 2 78 0 3 25 2 3 0123 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1 V0 V0 V1 V1 V3 V3 V2 V2 V7 V7 V6 V6 V5 V5 V4 V4由于没有规定访问邻接点的顺序，深度优先序列不是独一的c0c1c3c2c4c5c0c1c3c2c4c5 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1V0V0
4、V1 V1 V3 V3 V2 V2 V7 V7 V6 V6 V5 V5 V4 V4c0c1c3c2c4c5QUEUEV0V0V1V1V2V2V3V3V4V4V5V5V6V6V7V7V1V1V2V2V3V3V0V0V4V4V5V5V6V6V7V7 V0 V0 V7 V7 V6 V6 V5 V5 V4 V4 V3 V3 V2 V2 V1 V1/*/*图的广度优先遍历算法 */*程序名bfs.c 函数名bfs()、bfstraverse()*/*/c0c1c3c2c4c5c0c1c3c2c4c5c0c1c3c2c4c5c6c0c1c3c2c4c5c6c0c1c3c2c4c5c6V0V1V3V4V2V
5、6V8V7V5V9V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V8V7V9V6V5),()(EvuuvwTWABCDEF101015121287665ABCDEF1010151212876655ABCDEF107610ABCDEF1015125ABCDEF1015765ABCDEF1015765ABCDEF1076105ABCDEF1076105ABCDEF5ABCDEF65ABCDEF675ABCDEF67105ABCDEF671010ABDCFE2415288181013始点 终点 最短途径 途径长度A B A，C，B 19 C A，C 4 D A，C，F，D 25 E A
6、，C，B，E 29 F A，C，F 124如何求从某源点如何求从某源点到其他各点的最短途径？到其他各点的最短途径？如何从表中读取源点如何从表中读取源点0到终到终点点v的最短途径？例如顶点的最短途径？例如顶点A到到D的最短间隔是的最短间隔是d3=25,根据根据p3=5 p5=2 p2=0，反，反过来陈列，得到途径过来陈列，得到途径0,2,5,3即即A、C、F、D。ABDCFE241528818101342 弗洛伊德算法的根本思想弗洛伊德算法的根本思想203168359142DD-1D0D1D2D301230123012301230123001 401 401 10 301 10 301931 0
7、92 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 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-1 V5 V5 V3 V3 V2 V2 V0 V0 V1 V1 V4 V4 V6 V6 V5 V5 V3 V3 V2 V2 V0
8、V0 V1 V1 V4 V4 V6 V6课程代号课程称号先修课程C0C1C2C3C4C5C6C7C8高等数学信息技术根底离散数学数据构造程序设计言语编译原理操作系统电子线路根底计算机组成原理无无C0，C1C2，C4C1C3，C4C3，C8C0C7C0C2C1C7C8C6C3C4C5C0C1C2C3C4C5C1C2C5C3C0C2C5C1C3C0C1C2C3C4C5C1C2C5C5C1C5 C0 C1 C2 C3 0 C4 C5 0012345130103 1 adjvex nxet 3 0 5 1 5 0 0 1 5 0C0C1C2C3C4C5条途径上一切活动的继续时间之和。这条途径上一切活动
9、的继续时间之和。这条途径长度最长的途径就叫做关键途径条途径长度最长的途径就叫做关键途径(Critical Path)。V3V1a4=3a4=3a1=3a1=3a2=2a2=2a6=3a6=3a5=4a5=4a3=2a3=2a7=2a7=2a8=1a8=1顶点表示事件顶点表示事件边表示活动边表示活动事件事件VjVj发生表示发生表示 akjakj已终了已终了ak VjVi事件事件ViVi发生表示发生表示 akak可以开场可以开场 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
数据结构第08章图ppt课件
