圖 圖的基本概念PPT教案

1、圖圖 圖的基本概念圖的基本概念第1頁/共135頁 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第2頁/共135頁第3頁/共135頁v1v2v3v4v1v2v4v5v3第4頁/共135頁v1v2v3v4v1v2v4v5v3第5頁/共135頁第6頁/共135頁第7頁/共135頁v1v2v3v4v1v2v3v4第8頁/共135頁第9頁/共135頁niivD1)(21第10頁/共135頁v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4第11頁/共135頁第12頁/共135頁第13頁/共135頁V1V2V4V5V3V1V2V4V

2、5V3第14頁/共135頁第15頁/共135頁V0V1V3V234567825V0V2V1455064第16頁/共135頁v0v3v4v2v1v5v6第17頁/共135頁ABCDE第18頁/共135頁第19頁/共135頁第20頁/共135頁第21頁/共135頁約定約定: : V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3第22頁/共135頁 , ),( , ,A 否則否則或者或者如果如果01EjiEjiji,第23頁/共135頁v0v1v3v2v3v1v0v2第24頁/共135頁10,njjiA10,njijA10,njjiA10,njijA第25頁/

3、共135頁第26頁/共135頁V0V1V3V234567825V0V2V1455064第27頁/共135頁第28頁/共135頁第29頁/共135頁第30頁/共135頁第31頁/共135頁第32頁/共135頁v0v1v3v21 2 3 0 2 0 1 3 0 2 V0V1V2V3第33頁/共135頁v0v1v2v31 0 2 0 1 1 v0v1v2v3 1 2 0 2 1 3 v3v1v0v2第34頁/共135頁1 2 3 0 2 0 1 3 0 2 V0V1V2V3v0v1v2v31 0 2 0 1 1 第35頁/共135頁第36頁/共135頁第37頁/共135頁第38頁/共135頁第39頁

4、/共135頁第40頁/共135頁ABDC第41頁/共135頁 第42頁/共135頁vertex第43頁/共135頁V0V1V3V234567825V0V1V2V3 56 0 1 34 0 2 78 0 3 25 2 3 0123第44頁/共135頁第45頁/共135頁第46頁/共135頁 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,V6第47頁/共135頁c0c1c3c2c4c5c0c1c3c2

5、c4c5第48頁/共135頁第49頁/共135頁第50頁/共135頁第51頁/共135頁第52頁/共135頁 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4第53頁/共135頁c0c1c3c2c4c5第54頁/共135頁第55頁/共135頁QUEUEV V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 7V V1 1V V2 2V V3 3V V0 0V V4 4V V5 5V V6 6V V7 7 V0V0 V7V7 V6V6 V5V5 V4V

6、4 V3V3 V2V2 V1V1第56頁/共135頁/*/* 圖的廣度優(yōu)先遍歷算法 */* 程序名bfs.c 函數(shù)名bfs()、bfstraverse() */*/第57頁/共135頁第58頁/共135頁第59頁/共135頁第60頁/共135頁第61頁/共135頁c0c1c3c2c4c5c0c1c3c2c4c5第62頁/共135頁c0c1c3c2c4c5c6c0c1c3c2c4c5c6c0c1c3c2c4c5c6第63頁/共135頁V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V6V8V7V5V9V0V1V3V4V2V8V7V9V6V5第64頁/共135頁),()(EvuuvwT

7、WABCDEF101015121287665第65頁/共135頁第66頁/共135頁第67頁/共135頁第68頁/共135頁第69頁/共135頁ABCDEF1010151212876655ABCDEF107610ABCDEF1015125ABCDEF1015765ABCDEF1015765ABCDEF1076105ABCDEF107610第70頁/共135頁第71頁/共135頁第72頁/共135頁第73頁/共135頁第74頁/共135頁第75頁/共135頁第76頁/共135頁第77頁/共135頁第78頁/共135頁第79頁/共135頁第80頁/共135頁第81頁/共135頁5ABCDEF5AB

8、CDEF65ABCDEF675ABCDEF67105ABCDEF671010第82頁/共135頁第83頁/共135頁第84頁/共135頁第85頁/共135頁ABDCFE2415288181013始點(diǎn) 終點(diǎn) 最短路徑 路徑長(zhǎng)度A B （A，C，B） 19 C （A，C） 4 D （A，C，F(xiàn)，D） 25 E （A，C，B，E） 29 F （A，C，F(xiàn)） 124第86頁/共135頁第87頁/共135頁第88頁/共135頁第89頁/共135頁第90頁/共135頁第91頁/共135頁第92頁/共135頁 ABDCFE24152881810134第93頁/共135頁第94頁/共135頁第95頁/共135

9、頁第96頁/共135頁第97頁/共135頁第98頁/共135頁第99頁/共135頁2 弗洛伊德算法的基本思想弗洛伊德算法的基本思想第100頁/共135頁第101頁/共135頁第102頁/共135頁第103頁/共135頁第104頁/共135頁203168359142第105頁/共135頁DD-1D0D1D2D301230123012301230123001 401 401 10 301 10 301931 092 092 092 12 092 11 0822350834073406340634063 60 60 609 10 609 10 60PP-1P0P1P2P301230123012301

10、230123010 -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頁 第107頁/共135頁 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V6 6第108頁/共135頁 V V5 5 V V3 3 V V2 2 V V0 0 V V1 1 V V4 4 V V

11、6 6第109頁/共135頁課程代號(hào)課程名稱先修課程C0C1C2C3C4C5C6C7C8高等數(shù)學(xué)信息技術(shù)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)語言編譯原理操作系統(tǒng)電子線路基礎(chǔ)計(jì)算機(jī)組成原理無無C0，C1C2，C4C1C3，C4C3，C8C0C7C0C2C1C7C8C6C3C4C5第110頁/共135頁第111頁/共135頁第112頁/共135頁第113頁/共135頁C0C1C2C3C4C5C1C2C5C3C0C2C5C1C3C0C1C2C3C4C5第114頁/共135頁C1C2C5C5C1C5第115頁/共135頁 C0 C1 C2 C3 0 C4 C5 0012345130103 1 3 0 5 1

12、5 0 0 1 5 0C0C1C2C3C4C5第116頁/共135頁第117頁/共135頁第118頁/共135頁第119頁/共135頁第120頁/共135頁第121頁/共135頁第122頁/共135頁V3V1a4=a4=3 3a1=a1=3 3a2=a2=2 2a6=a6=3 3a5=a5=4 4a3=a3=2 2a7=a7=2 2a8=a8=1 1頂點(diǎn)表示事件頂點(diǎn)表示事件邊表示活動(dòng)邊表示活動(dòng)事件事件VjVj發(fā)生表示發(fā)生表示 akj已結(jié)束已結(jié)束ak VjVi事件事件ViVi發(fā)生表示發(fā)生表示 ak可以開始可以開始 V2V4V5V6第123頁/共135頁v0v1v2v4v3v6v7v8v5v9a0=8a1=6a2=7a3=3a4=10a5=9a6=9a7=13a11=2a10=8a9=19a8=4a13=14a12=6a14=10第124頁/共135頁第125頁/共135頁)() 11(,)(maxipjnivvjveij持續(xù)的時(shí)間活動(dòng)vi第126頁/共135頁第127頁/共135頁)()20)(,()(minisjnivvlenjvjilvi第128頁/共135頁第129頁/共135頁第130頁/共135頁頂點(diǎn)vevl活動(dòng)ell-e關(guān)鍵活動(dòng)v0v1v