图图的基本概念学习教案

1、图图 图的基本概念图的基本概念第一页，共135页。第1页/共135页第二页，共135页。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第2页/共135页第三页，共135页。第3页/共135页第四页，共135页。v1v2v3v4v1v2v4v5v3第4页/共135页第五页，共135页。v1v2v3v4v1v2v4v5v3第5页/共135页第六页，共135页。第6页/共135页第七页，共135页。第7页/共135页第八页，共135页。v1v2v3v4v1v2v3v4第8页/共135页第九页，共135页。第9页/共135页第十页，共135页。niivD1)

2、(21第10页/共135页第十一页，共135页。v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4第11页/共135页第十二页，共135页。第12页/共135页第十三页，共135页。第13页/共135页第十四页，共135页。V1V2V4V5V3V1V2V4V5V3第14页/共135页第十五页，共135页。第15页/共135页第十六页，共135页。V0V1V3V234567825V0V2V1455064第16页/共135页第十七页，共135页。v0v3v4v2v1v5v6第17页/共135页第十八页，共135页。ABCDE第18页/共135页第十九页，共135页。第

3、19页/共135页第二十页，共135页。第20页/共135页第二十一页，共135页。第21页/共135页第二十二页，共135页。约定约定(yudng):(yudng): G= G=是图是图, V=v0,v1,v2, vn-1 , V=v0,v1,v2, vn-1 ,设顶点的设顶点的 角标为它的编号角标为它的编号 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第22页/共135页第二十三页，共135页。 , ),( , ,A 否则否则或者或者如果如果01EjiEjiji,第23页/共135页第二十四页，共135页。v0v1v3v2v3v1v0v2第24页

4、/共135页第二十五页，共135页。10,njjiA10,njijA10,njjiA10,njijA第25页/共135页第二十六页，共135页。第26页/共135页第二十七页，共135页。V0V1V3V234567825V0V2V1455064第27页/共135页第二十八页，共135页。第28页/共135页第二十九页，共135页。第29页/共135页第三十页，共135页。第30页/共135页第三十一页，共135页。第31页/共135页第三十二页，共135页。第32页/共135页第三十三页，共135页。v0v1v3v21 2 3 0 2 0 1 3 0 2 V0V1V2V3第33页/共135页第

5、三十四页，共135页。v0v1v2v31 0 2 0 1 1 v0v1v2v3 1 2 0 2 1 3 v3v1v0v2第34页/共135页第三十五页，共135页。1 2 3 0 2 0 1 3 0 2 V0V1V2V3v0v1v2v31 0 2 0 1 1 第35页/共135页第三十六页，共135页。第36页/共135页第三十七页，共135页。第37页/共135页第三十八页，共135页。第38页/共135页第三十九页，共135页。第39页/共135页第四十页，共135页。第40页/共135页第四十一页，共135页。ABDC第41页/共135页第四十二页，共135页。 第42页/共135页第四

6、十三页，共135页。vertex第43页/共135页第四十四页，共135页。V0V1V3V234567825V0V1V2V3 56 0 1 34 0 2 78 0 3 25 2 3 0123第44页/共135页第四十五页，共135页。第45页/共135页第四十六页，共135页。第46页/共135页第四十七页，共135页。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4由于没有规定访问邻接点的顺序，深度优先(yuxin)序列不是唯一的V0,V1,V4,V7,V3,V2,V5,V6第47

7、页/共135页第四十八页，共135页。c0c1c3c2c4c5c0c1c3c2c4c5第48页/共135页第四十九页，共135页。第49页/共135页第五十页，共135页。第50页/共135页第五十一页，共135页。第51页/共135页第五十二页，共135页。第52页/共135页第五十三页，共135页。 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第53页/共135页第五十四页，共135页。c0c1c3c2c4c5第54页/共135页第五十五页，共135页。第55页/共135页第五十

8、六页，共135页。QUEUEV V0 0V V1 1V V2 2V V3 3V4V4V5V5V6V6V V7 7V V1 1V V2 2V3V3V V0 0V4V4V V5 5V V6 6V V7 7 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1第56页/共135页第五十七页，共135页。/*/* 图的广度优先遍历算法(sun f) */* 程序名bfs.c 函数名bfs()、bfstraverse() */*/第57页/共135页第五十八页，共135页。第58页/共135页第五十九页，共135页。第59页/共135页第六十页，共135页。第60页/共135页

9、第六十一页，共135页。第61页/共135页第六十二页，共135页。c0c1c3c2c4c5c0c1c3c2c4c5第62页/共135页第六十三页，共135页。c0c1c3c2c4c5c6c0c1c3c2c4c5c6c0c1c3c2c4c5c6第63页/共135页第六十四页，共135页。V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V8V7V9V6V5第64页/共135页第六十五页，共135页。),()(EvuuvwTWABCDEF101015121287665第65页/共135页第六十六页，共135页。第66页/共135页第六十七页，共1

10、35页。第67页/共135页第六十八页，共135页。第68页/共135页第六十九页，共135页。第69页/共135页第七十页，共135页。ABCDEF1010151212876655ABCDEF107610ABCDEF1015125ABCDEF1015765ABCDEF1015765ABCDEF1076105ABCDEF107610第70页/共135页第七十一页，共135页。第71页/共135页第七十二页，共135页。第72页/共135页第七十三页，共135页。第73页/共135页第七十四页，共135页。第74页/共135页第七十五页，共135页。第75页/共135页第七十六页，共135页。第

11、76页/共135页第七十七页，共135页。第77页/共135页第七十八页，共135页。第78页/共135页第七十九页，共135页。第79页/共135页第八十页，共135页。第80页/共135页第八十一页，共135页。第81页/共135页第八十二页，共135页。5ABCDEF5ABCDEF65ABCDEF675ABCDEF67105ABCDEF671010第82页/共135页第八十三页，共135页。第83页/共135页第八十四页，共135页。第84页/共135页第八十五页，共135页。第85页/共135页第八十六页，共135页。ABDCFE2415288181013始点 终点 最短路径(ljng

12、) 路径(ljng)长度A B （A，C，B） 19 C （A，C） 4 D （A，C，F，D） 25 E （A，C，B，E） 29 F （A，C，F） 124如何求从某源点如何求从某源点到其余到其余(qy)各点的最短路径？各点的最短路径？第86页/共135页第八十七页，共135页。第87页/共135页第八十八页，共135页。第88页/共135页第八十九页，共135页。第89页/共135页第九十页，共135页。第90页/共135页第九十一页，共135页。第91页/共135页第九十二页，共135页。第92页/共135页第九十三页，共135页。 如何从表中读取源点如何从表中读取源点0到终点到终点v

13、的最短路径？例如顶点的最短路径？例如顶点A到到D的最短距离是的最短距离是d3=25,根据根据(gnj)p3 =5 p5 =2 p2=0，反过来排列，得到路，反过来排列，得到路径径0, 2, 5,3（即（即A、C、F、D）。ABDCFE24152881810134第93页/共135页第九十四页，共135页。第94页/共135页第九十五页，共135页。第95页/共135页第九十六页，共135页。第96页/共135页第九十七页，共135页。第97页/共135页第九十八页，共135页。第98页/共135页第九十九页，共135页。第99页/共135页第一百页，共135页。2 弗洛伊德算法的基本弗洛伊德算

14、法的基本(jbn)思想思想第100页/共135页第一百零一页，共135页。第101页/共135页第一百零二页，共135页。第102页/共135页第一百零三页，共135页。第103页/共135页第一百零四页，共135页。第104页/共135页第一百零五页，共135页。203168359142第105页/共135页第一百零六页，共135页。DD-1D0D1D2D301230123012301230123001 401 401 10 301 10 301931 092 092 092 12 092 11 0822350834073406340634063 60 60 609 10 609 10 60

15、PP-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第106页/共135页第一百零七页，共135页。第107页/共135页第一百零八页，共135页。 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6第108页/

16、共135页第一百零九页，共135页。 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6第109页/共135页第一百一十页，共135页。课程代号课程名称先修课程C0C1C2C3C4C5C6C7C8高等数学信息技术基础离散数学数据结构程序设计语言编译原理操作系统电子线路基础计算机组成原理无无C0，C1C2，C4C1C3，C4C3，C8C0C7C0C2C1C7C8C6C3C4C5第110页/共135页第一百一十一页，共135页。第111页/共135页第一百一十二页，共135页。第112页/共135页第一百一十三页，共135页。第113页/共135页第一

17、百一十四页，共135页。C0C1C2C3C4C5C1C2C5C3C0C2C5C1C3C0C1C2C3C4C5第114页/共135页第一百一十五页，共135页。C1C2C5C5C1C5第115页/共135页第一百一十六页，共135页。 C0 C1 C2 C3 0 C4 C5 0012345130103 1 3 0 5 1 5 0 0 1 5 0C0C1C2C3C4C5第116页/共135页第一百一十七页，共135页。第117页/共135页第一百一十八页，共135页。第118页/共135页第一百一十九页，共135页。第119页/共135页第一百二十页，共135页。第120页/共135页第一百二十一

18、页，共135页。第121页/共135页第一百二十二页，共135页。键路径键路径(Critical Path)。第122页/共135页第一百二十三页，共135页。V3V1a4=3a4=3a1=3a1=3a2=2a2=2a6=3a6=3a5=a5=4 4a3=a3=2 2a7=2a7=2a8=1a8=1顶点顶点(dngdin)(dngdin)表示事件表示事件边表示边表示(biosh)(biosh)活动活动事件事件VjVj发生表示发生表示 akj已结束已结束ak VjVi事件事件ViVi发生表示发生表示 ak可以开始可以开始 V2V4V5V6第123页/共135页第一百二十四页，共135页。v0v1v2v4