數(shù)據(jù)結(jié)構(gòu)教案第七章

課程名稱數(shù)據(jù)結(jié)構(gòu)教學(xué)對(duì)象新華軟工專業(yè)教材數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）講課內(nèi)容第七章圖課時(shí)3教學(xué)目標(biāo)與要求1、了解圖各種存放結(jié)構(gòu)及其結(jié)構(gòu)算法，了解實(shí)際問(wèn)題求解效率和采取何種存放結(jié)構(gòu)和算法有親密聯(lián)絡(luò)2.了解圖兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法，在學(xué)習(xí)中應(yīng)注意圖遍歷算法和樹(shù)遍歷算法之間類似和差異，樹(shù)先根遍歷是一個(gè)深度優(yōu)先搜索策略，樹(shù)層次遍歷是一個(gè)廣度優(yōu)先搜索策略3.了解課件中討論各種圖算法重點(diǎn)、難點(diǎn)重點(diǎn)：圖概念，存放，遍歷，拓樸排序，最小生成樹(shù)難點(diǎn)：算法實(shí)現(xiàn)、遍歷有生成樹(shù)和拓樸排序課型電腦應(yīng)用課教學(xué)方法講授、投影、板書(shū)教學(xué)過(guò)程設(shè)計(jì)（包含講授知識(shí)、演示內(nèi)容及案例、提問(wèn)及學(xué)生演示內(nèi)容）課程導(dǎo)入：前面所學(xué)數(shù)據(jù)結(jié)構(gòu)中有線性結(jié)構(gòu)和非線性結(jié)構(gòu)，其中線性表，棧和隊(duì)列及串、數(shù)組均為線性結(jié)構(gòu)，而上章所講樹(shù)是非線性結(jié)構(gòu)。樹(shù)結(jié)構(gòu)特點(diǎn)是任一結(jié)點(diǎn)除根有且僅有一個(gè)直接前驅(qū)含有一個(gè)或多個(gè)直接后繼。本章將學(xué)習(xí)另一個(gè)非常主要非線性結(jié)構(gòu)圖，它特點(diǎn)是：任意兩個(gè)結(jié)點(diǎn)都有可能相關(guān)聯(lián)，即任一結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼，結(jié)點(diǎn)間鄰接關(guān)系能夠是任意。（10分鐘）任務(wù)一、圖基本概念1．圖定義安徽新華電腦專修學(xué)院課堂教學(xué)教案（軟工專業(yè)課使用）

教學(xué)過(guò)程設(shè)計(jì)(續(xù)表)圖G是集合V和集合E組成，記G=（V，E），其中V是G中頂點(diǎn)非空有限集，E是G中邊集合，面邊是V中頂點(diǎn)偶對(duì)。若頂點(diǎn)偶是有序，剛稱為有向圖，用尖括號(hào)括起，若為無(wú)序，則稱為無(wú)向圖。有向邊又稱為弧。圖中E（G）能夠?yàn)榭?。任?wù)二、圖基本述語(yǔ)無(wú)向圖邊是無(wú)向有向圖每條邊是有向端點(diǎn)和鄰接點(diǎn)起點(diǎn)和鄰接點(diǎn)度、入度、出度子圖G=（V，E）和G`=（V`，E`），若V`是V子集且E`是E子集，并使得E`中邊僅與V`中頂點(diǎn)相關(guān)聯(lián)，則G`是G子圖。無(wú)向完全圖和在向完全圖設(shè)一無(wú)向圖有N個(gè)頂點(diǎn)，且有n(n-1)/2條邊，即任何兩頂點(diǎn)都有邊相關(guān)聯(lián)，這么無(wú)向圖稱為無(wú)向完全圖。有向圖中基有n(n-1)條邊，即任何兩頂點(diǎn)都有一對(duì)反向弧，則此有向圖稱為有向完全圖。路徑和路徑長(zhǎng)度及簡(jiǎn)單路徑路徑是頂點(diǎn)序列。路徑長(zhǎng)度是路徑所含邊。若一條路徑頂點(diǎn)序列中不出現(xiàn)重復(fù)頂點(diǎn)，稱為簡(jiǎn)單路徑回路或環(huán)連通、連通圖和連通分圖強(qiáng)連通圖和強(qiáng)連通分圖賦權(quán)圖

任務(wù)三、圖存放結(jié)構(gòu)1.圖鄰接矩陣存放它是用二維數(shù)組來(lái)表示圖中頂點(diǎn)之間鄰接關(guān)系，可將G鄰接矩陣定義為一個(gè)n階方陣。#defineMAVX50Voidcreatadjmatrix(intcost[MAXV][MAXV],intvexnum,intenum){intI,j,k,v1,v2;For(i=1;i<=vexnum;i++)For(j=1;j<=vexnum;j++)Cost[i][j]=0;For(k=1;k<=enum;k++){scanf(“%d%d”,&v1,&v2);Cost[v1][v2]=1;Cost[v2][v1]=1;}}2、鄰接鏈表一個(gè)圖鄰接鏈表存放結(jié)構(gòu)類型定義：#definemaxvertex50Typedefstructarcnode{intadjvex;Structarnode*nextarc;}arcnodetyp;Typestructvexnode{intvertex;Arcnodetp*firstarc;}adjlist[maxvertex];Typedefstructgraph{adjlistadjlist;Intvexnum,arcnum;}graphtp;復(fù)習(xí)思索題作業(yè)上機(jī)任務(wù)搞清圖基本概念含義描述圖存放實(shí)現(xiàn)參考文件晉良穎數(shù)據(jù)結(jié)構(gòu)人民郵電大學(xué)出版社課后記（或歸納小結(jié)）此次課程就介紹這里結(jié)束，總結(jié)此次內(nèi)容；課程名稱數(shù)據(jù)結(jié)構(gòu)教學(xué)對(duì)象新華軟工專業(yè)教材數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）講課內(nèi)容第七章圖課時(shí)3教學(xué)目標(biāo)與要求1、了解圖各種存放結(jié)構(gòu)及其結(jié)構(gòu)算法，了解實(shí)際問(wèn)題求解效率和采取何種存放結(jié)構(gòu)和算法有親密聯(lián)絡(luò)2.了解圖兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法，在學(xué)習(xí)中應(yīng)注意圖遍歷算法和樹(shù)遍歷算法之間類似和差異，樹(shù)先根遍歷是一個(gè)深度優(yōu)先搜索策略，樹(shù)層次遍歷是一個(gè)廣度優(yōu)先搜索策略3.了解課件中討論各種圖算法重點(diǎn)、難點(diǎn)重點(diǎn)：圖概念，存放，遍歷，拓樸排序，最小生成樹(shù)難點(diǎn)：算法實(shí)現(xiàn)、遍歷有生成樹(shù)和拓樸排序課型電腦應(yīng)用課教學(xué)方法講授、投影、板書(shū)教學(xué)過(guò)程設(shè)計(jì)（包含講授知識(shí)、演示內(nèi)容及案例、提問(wèn)及學(xué)生演示內(nèi)容）復(fù)習(xí)內(nèi)容：上講介紹了圖基本概念，圖在計(jì)算機(jī)中存放結(jié)構(gòu)，詳細(xì)講圖鄰接矩陣和鄰接表存放。這兩種存放結(jié)構(gòu)算法需要重點(diǎn)掌握。課程導(dǎo)入：樹(shù)一章中介紹了樹(shù)先根、中根和后根遍歷，即按照某種次序?qū)?shù)中全部結(jié)點(diǎn)訪問(wèn)一次且只訪問(wèn)一次次序，那么對(duì)圖來(lái)說(shuō)又怎么來(lái)訪問(wèn)它每一個(gè)結(jié)點(diǎn)呢，我們稱為圖遍歷。任務(wù)一、圖遍歷深度優(yōu)先搜索基本思想：從圖G中某個(gè)頂點(diǎn)出發(fā)，訪問(wèn)V1，然后選擇一下與V1相鄰且未被訪問(wèn)過(guò)頂點(diǎn)Vi訪問(wèn)，再?gòu)腣i出發(fā)選擇一個(gè)與Vi相鄰接且未被訪問(wèn)過(guò)頂點(diǎn)Vj訪問(wèn)，依次繼續(xù)。若當(dāng)前被訪問(wèn)過(guò)頂點(diǎn)全部鄰接頂點(diǎn)都已被訪問(wèn)，則回退到已被訪問(wèn)頂點(diǎn)序列中最終一個(gè)仍未被訪問(wèn)相鄰接頂點(diǎn)Vw，從Vw出以按一樣方法向前遍歷，直到圖中全部頂點(diǎn)被訪問(wèn)。安徽新華電腦專修學(xué)院課堂教學(xué)教案（軟工專業(yè)課使用）

教學(xué)過(guò)程設(shè)計(jì)(續(xù)表)2．廣度優(yōu)先搜索基本思想：首先訪問(wèn)初始點(diǎn)Vi,并將其標(biāo)識(shí)為已訪問(wèn)過(guò)，接著訪問(wèn)Vi全部未被訪問(wèn)過(guò)鄰接頂點(diǎn)Vi1,vi2…vit,并均標(biāo)識(shí)為已訪問(wèn)地過(guò)，然后再按照vi1,vi2…vit次序，訪問(wèn)每一個(gè)頂點(diǎn)全部未被訪問(wèn)過(guò)鄰接頂點(diǎn)，并均標(biāo)識(shí)為已訪問(wèn)，依次類推，直到圖G中全部和初始點(diǎn)Vi有路徑相通頂點(diǎn)都有被訪問(wèn)過(guò)為止。voidBFSTraverse(GraphG,Status(*visit)(intv)){for(v=0;v<G.vexnum;++v)visited[v]=FALSE;IntiQueque(Q);for(v=0;v<G.vexnum;++v)if(!visited[v]){EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(u);visited[u]=TRUE;Visit(u);for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;visited(w);EnQueue(G,w);}}}}任務(wù)二、圖生成樹(shù)生成樹(shù)定義：全部頂點(diǎn)均由邊連接在一起，但不存在回路圖叫~深度優(yōu)先生成樹(shù)與廣度優(yōu)先生成樹(shù)生成森林：非連通圖每個(gè)連通分量生成樹(shù)一起組成非連通圖~說(shuō)明一個(gè)圖能夠有許多棵不一樣生成樹(shù)全部生成樹(shù)具備以下共同特點(diǎn)：生成樹(shù)頂點(diǎn)個(gè)數(shù)與圖頂點(diǎn)個(gè)數(shù)相同生成樹(shù)是圖極小連通子圖一個(gè)有n個(gè)頂點(diǎn)連通圖生成樹(shù)有n-1條邊生成樹(shù)中任意兩個(gè)頂點(diǎn)間路徑是唯一在生成樹(shù)中再加一條邊必定形成回路含n個(gè)頂點(diǎn)n-1條邊圖不一定是生成樹(shù)最小生成樹(shù)網(wǎng)絡(luò)及其鄰接矩陣最小生成樹(shù)求最小生成樹(shù)慣用算法普里姆算法

算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊集合初始令U={u0},(u0?V),TE=F在全部u?U,v?V-U邊(u,v)?E中，找一條代價(jià)最小邊(u0,v0)將(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N最小生成樹(shù)算法實(shí)現(xiàn)：圖用鄰接矩陣表示算法描述算法評(píng)價(jià)：T(n)=O(n2)克魯斯卡爾算法算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹(shù)初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊非連通圖T=(V,{F})，每個(gè)頂點(diǎn)自成一個(gè)連通分量在E中選取代價(jià)最小邊，若該邊依附頂點(diǎn)落在T中不一樣連通分量上，則將此邊加入到T中；不然，舍去此邊，選取下一條代價(jià)最小邊依這類推，直至T中全部頂點(diǎn)都在同一連通分量上為止（3）統(tǒng)觀法復(fù)習(xí)思索題作業(yè)上機(jī)任務(wù)課后習(xí)題2題P138第三題P1384、5、6題參考文件晉良穎數(shù)據(jù)結(jié)構(gòu)人民郵電大學(xué)出版社課后記（或歸納小結(jié)）此次課程內(nèi)容為圖遍歷和最小生成樹(shù)，相對(duì)較難，課余時(shí)間要多看，多做題。課程名稱數(shù)據(jù)結(jié)構(gòu)教學(xué)對(duì)象新華軟工專業(yè)教材數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）講課內(nèi)容第七章圖課時(shí)3教學(xué)目標(biāo)與要求1、了解圖各種存放結(jié)構(gòu)及其結(jié)構(gòu)算法，了解實(shí)際問(wèn)題求解效率和采取何種存放結(jié)構(gòu)和算法有親密聯(lián)絡(luò)2.了解圖兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法，在學(xué)習(xí)中應(yīng)注意圖遍歷算法和樹(shù)遍歷算法之間類似和差異，樹(shù)先根遍歷是一個(gè)深度優(yōu)先搜索策略，樹(shù)層次遍歷是一個(gè)廣度優(yōu)先搜索策略3.了解課件中討論各種圖算法重點(diǎn)、難點(diǎn)重點(diǎn)：圖概念，存放，遍歷，拓樸排序，最小生成樹(shù)難點(diǎn)：算法實(shí)現(xiàn)、遍歷有生成樹(shù)和拓樸排序課型電腦應(yīng)用課教學(xué)方法講授、投影、板書(shū)教學(xué)過(guò)程設(shè)計(jì)（包含講授知識(shí)、演示內(nèi)容及案例、提問(wèn)及學(xué)生演示內(nèi)容）復(fù)習(xí)內(nèi)容：上一講主要講解是圖深度優(yōu)先和廣度優(yōu)先遍歷及其算法實(shí)現(xiàn)，以及生成樹(shù)和最小生成樹(shù)及求解最小生成樹(shù)各種算法，如普里姆算法、克魯期斯卡爾算法等。課程導(dǎo)入:用帶權(quán)有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間交通聯(lián)絡(luò)權(quán)——表示此線路長(zhǎng)度或沿此線路運(yùn)輸所花時(shí)間或費(fèi)用等問(wèn)題：從某頂點(diǎn)出發(fā)，沿圖邊抵達(dá)另一頂點(diǎn)所經(jīng)過(guò)路徑中，各邊上權(quán)值之和最小一條路徑——最短路徑安徽新華電腦專修學(xué)院課堂教學(xué)教案（軟工專業(yè)課使用）

教學(xué)過(guò)程設(shè)計(jì)(續(xù)表)任務(wù)一、最短路徑迪杰斯特拉(Dijkstra)算法(1)設(shè)置兩個(gè)頂點(diǎn)集合T和S;集合S存放已找到最短路徑頂點(diǎn)集合T存放當(dāng)前還未找到最短路徑頂點(diǎn)(2)初始狀態(tài)時(shí),S只包含源點(diǎn)v0;(3)從T中選取某個(gè)頂點(diǎn)vi(要求vi到v0路徑長(zhǎng)度最短)加入到S中,;(4)S中每加入一個(gè)頂點(diǎn)vi,都要修改頂點(diǎn)v0到T中剩下頂點(diǎn)最短路徑長(zhǎng)度值;它們值為原來(lái)值與新值較小者新值是vi最短路徑長(zhǎng)度值加上vi到該頂點(diǎn)路徑長(zhǎng)度(5)不停重復(fù)(3)和(4),直到S包含全部頂點(diǎn);任務(wù)二、拓樸排序1、問(wèn)題提出：學(xué)生選修課程問(wèn)題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是課程j先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣次序?qū)W習(xí)這些課程，才能無(wú)矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判?、定義AOV網(wǎng)——用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系有向圖稱為頂點(diǎn)表示活動(dòng)網(wǎng)(ActivityOnVertexnetwork)，簡(jiǎn)稱AOV網(wǎng)若<vi,vj>是圖中有向邊，則vi是vj直接前驅(qū)；vj是vi直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間優(yōu)先關(guān)系排列成一個(gè)線性序列過(guò)程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖結(jié)構(gòu)其頂點(diǎn)拓?fù)溆行蛐蛄校艟W(wǎng)中全部頂點(diǎn)都在它拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判蚍椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和全部以它為尾弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)頂點(diǎn)為止為先決條件

拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間優(yōu)先關(guān)系排列成一個(gè)線性序列過(guò)程叫~檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖結(jié)構(gòu)其頂點(diǎn)拓?fù)溆行蛐蛄?，若網(wǎng)中全部頂點(diǎn)都在它拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)拓?fù)渑判蚍椒ㄔ谟邢驁D中選一個(gè)沒(méi)有前驅(qū)頂點(diǎn)且輸出之從圖中刪除該頂點(diǎn)和全部以它為尾弧重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)頂點(diǎn)為止算法實(shí)現(xiàn)以鄰接表作存放結(jié)構(gòu)把鄰接表中全部入度為0頂點(diǎn)進(jìn)棧棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj直接后繼Vk，把Vk入度減1；若Vk入度為0則進(jìn)棧重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r(shí)輸出頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；不然，拓?fù)渑判蛲瓿舌徑颖斫Y(jié)點(diǎn)：typedefstructnode{intvex;//頂點(diǎn)域structnode*next;//鏈域}