教案紙（首頁）第1頁第次課學時授課時間___________教學主題圖的基本概念；圖的存儲結(jié)構(gòu)；教學要求1、掌握圖的定義及其邏輯結(jié)構(gòu)特性，圖抽象數(shù)據(jù)類型的描述方法。2、掌握圖的基本術(shù)語及其含義。3、掌握圖的鄰接矩陣和鄰接表兩種主要的存儲結(jié)構(gòu)及其特點。4、掌握棧在實際求解問題中的應用方法。教學重點圖的特點；圖的概念，包括完全圖、路徑、連通圖、強聯(lián)通分量；圖的鄰接矩陣和鄰接表教學難點完全圖，路徑，強連通分量等重要概念；圖的鄰接矩陣和鄰接表教學方法講授教學手段多媒體、板書講授要點1、圖的定義及圖抽象數(shù)據(jù)類型的描述方法。2、圖基本術(shù)語的定義及其含義。3、圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。4、基于圖鄰接矩陣和鄰接表存儲結(jié)構(gòu)的基本算法設計。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記8.1圖的概念1、圖的定義圖（Graph）G由頂點集合V(G)和邊集合E(G)構(gòu)成。圖是現(xiàn)實問題的抽象，例如哥尼斯堡七橋問題（介紹問題背景）在圖G中，如果代表邊的頂點對是無序的，則稱G為無向圖。用圓括號序偶表示無向邊。如果表示邊的頂點對是有序的，則稱G為有向圖。用尖括號序偶表示有向邊。2、圖的常用術(shù)語頂點的度無向圖中，以頂點i為端點的邊數(shù)稱為該頂點的度。有向圖中，以頂點i為終點的入邊的數(shù)目，稱為該頂點的入度。以頂點i為始點的出邊的數(shù)目，稱為該頂點的出度。一個頂點的入度與出度的和為該頂點的度。完全圖無向圖中，每兩個頂點之間都存在著一條邊，稱為完全無向圖，包含有n(n-1)/2條邊。有向圖中，每兩個頂點之間都存在著方向相反的兩條邊，稱為完全有向圖，包含有n(n-1)條邊。子圖設有兩個圖G=(V，E)和G'=(V'，E')，若V'是V的子集，即V'V，且E'是E的子集，即E'E，則稱G'是G的子圖。路徑和路徑長度在一個圖G=(V，E)中，從頂點i到頂點j的一條路徑(i，i1，i2，…，im，j)。其中，所有的(ix，iy)∈E(G)，或者<ix，iy>∈E(G)路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點和結(jié)束點可以相同外，其余頂點均不相同，則稱此路徑為簡單路徑。連通、連通圖和連通分量無向圖中：若從頂點i到頂點j有路徑，則稱頂點i和j是連通的。若圖中任意兩個頂點都連通，則稱為連通圖，否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然，任何連通圖的連通分量只有一個，即本身，而非連通圖有多個連通分量。強連通圖和強連通分量有向圖中：若從頂點i到頂點j有路徑，則稱從頂點i到j是連通的。若圖G中的任意兩個頂點i和j都連通，即從頂點i到j和從頂點j到i都存在路徑，則稱圖G是強連通圖。權(quán)和網(wǎng)圖中每一條邊都可以附帶有一個對應的數(shù)值，這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個頂點到另一個頂點的距離或花費的代價。邊上帶有權(quán)的圖稱為帶權(quán)圖，也稱作網(wǎng)。8.2圖的存儲結(jié)構(gòu)1、圖的兩種存儲結(jié)構(gòu)鄰接表類似于樹的孩子鏈表，將和同一頂點"相鄰接"的所有鄰接點鏈接在一個單鏈表中，單鏈表的頭指針則和頂點信息一起存儲在一個一維數(shù)組中。圖的鄰接表存儲表示

constMAX_VERTEX_NUM=20;

typedefstructArcNode{//弧結(jié)點的結(jié)構(gòu)

intadjvex;//該弧所指向的頂點的位置

structArcNode*nextarc;//指向下一條弧的指針

VRTypeweight;//與弧相關(guān)的權(quán)值，無權(quán)則為0

InfoType*info;//指向該弧相關(guān)信息的指針

};

typedefstructVNode{//頂點結(jié)點的結(jié)構(gòu)

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧

}AdjList[MAX_VERTEX_NUM];

typedefstruct{//圖的鄰接表結(jié)構(gòu)定義

AdjListvertices;//頂點數(shù)組

intvexnum,arcnum;//圖的當前頂點數(shù)和弧數(shù)

GraphKindkind;//圖的種類標志

}ALGraph;(忽略相關(guān)信息指針)鄰接矩陣將圖的頂點信息存儲在一個一維數(shù)組中，并將它的鄰接矩陣存儲在一個二維數(shù)組中即構(gòu)成圖的數(shù)組表示。constINFINITY=INT_MAX;//最大值∞

constMAX_VERTEX_NUM=20;//最大頂點個數(shù)

typedefenum{DG,DN,AG,AN}GraphKind;

//類型標志{有向圖,有向網(wǎng),無向圖,無向網(wǎng)}

typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點關(guān)系類型。

//對無權(quán)圖，用1或0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。

InfoType*info;//該弧相關(guān)信息的指針

}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點信息

AdjMatrixarcs;//表示頂點之間關(guān)系的二維數(shù)組

intvexnum,arcnum;//圖的當前頂點數(shù)和弧(邊)數(shù)

GraphKindkind;//圖的種類標志

}MGraph;

第次課學時授課時間________教學主題圖的遍歷及圖遍歷算法的應用教學要求1、掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。2、掌握圖遍歷算法的應用。教學重點圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法教學難點圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算及其應用教學方法講授+練習教學手段多媒體、上機實操講授要點1、圖遍歷的概念。2、圖的深度優(yōu)先遍歷算法及其在圖搜索算法設計中的應用。3、圖的廣度優(yōu)先遍歷算法及其在圖搜索算法設計中的應用。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記8.3圖的遍歷圖的遍歷從給定圖中任意指定的頂點（稱為初始點）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，使每個頂點僅被訪問一次，這個過程稱為圖的遍歷。圖的遍歷得到的頂點序列稱為圖遍歷序列。2、深度優(yōu)先遍歷（1）從圖中某個初始頂點v出發(fā)，首先訪問初始頂點v。（2）選擇一個與頂點v相鄰且沒被訪問過的頂點w，再從w出發(fā)進行深度優(yōu)先搜索，直到圖中與當前頂點v鄰接的所有頂點都被訪問過為止。采用鄰接表的DFS算法實現(xiàn)：voidDFS(AdjGraph*G，intv){ArcNode*p;intw;visited[v]=1; //置已訪問標記printf("%d"，v); //輸出被訪問頂點的編號p=G->adjlist[v].firstarc; //p指向頂點v的第一條邊的邊頭結(jié)點while(p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G，w); //若w頂點未訪問，遞歸訪問它p=p->nextarc; //p指向頂點v的下一條邊的邊頭結(jié)點}}3、廣度優(yōu)先遍歷（1）訪問初始點v，接著訪問v的所有未被訪問過的鄰接點v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，訪問每一個頂點的所有未被訪問過的鄰接點。（3）依次類推，直到圖中所有和初始點v有路徑相通的頂點都被訪問過為止。采用鄰接表的BFS算法：voidBFS(AdjGraph*G，intv){intw，i;ArcNode*p;SqQueue*qu; //定義環(huán)形隊列指針I(yè)nitQueue(qu); //初始化隊列intvisited[MAXV]; //定義頂點訪問標記數(shù)組for(i=0;i<G->n;i++)visited[i]=0; //訪問標記數(shù)組初始化printf("%2d"，v); //輸出被訪問頂點的編號visited[v]=1; //置已訪問標記enQueue(qu，v);while(!QueueEmpty(qu)) //隊不空循環(huán){deQueue(qu，w); //出隊一個頂點wp=G->adjlist[w].firstarc; //指向w的第一個鄰接點while(p!=NULL) //查找w的所有鄰接點{if(visited[p->adjvex]==0) //若當前鄰接點未被訪問{printf("%2d"，p->adjvex); //訪問該鄰接點visited[p->adjvex]=1; //置已訪問標記enQueue(qu，p->adjvex); //該頂點進隊}p=p->nextarc; //找下一個鄰接點}}printf("\n");}4、圖的遍歷算法的應用利用圖的遍歷求解迷宮問題。廣度優(yōu)先遍歷找到的路徑一定是最短路徑，而深度優(yōu)先遍歷則不一定。深度優(yōu)先遍歷能找所有路徑，而廣度優(yōu)先遍歷難以實現(xiàn)。教學總結(jié)：本章節(jié)主要介紹了圖的遍歷及圖遍歷算法的應用。第次課學時授課時間________教學主題最小生成樹的定義；最小生成樹的Prim和Kruskal算法教學要求1、掌握生成樹和最小生成樹的定義。2、掌握求最小生成樹的Prim和Kruskal算法。教學重點最小生成樹的定義；Prim和Kruskal算法教學難點求最小生成樹的Prim和Kruskal算法教學方法講授教學手段多媒體、板書講授要點1、生成樹、深度優(yōu)先生成樹和廣度優(yōu)先生成樹的概念。2、最小生成樹的定義，求最小生成樹的Prim和Kruskal算法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記8.4生成樹和最小生成樹1、生成樹的概念一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部n個頂點和構(gòu)成一棵樹的(n-1)條邊。最小生成樹：對于帶權(quán)連通圖G（每條邊上的權(quán)均為大于零的實數(shù)），可能有多棵不同生成樹。每棵生成樹的所有邊的權(quán)值之和可能不同。其中權(quán)值之和最小的生成樹稱為圖的最小生成樹。構(gòu)造最小生成樹的準則必須使用且僅使用該連通圖中的n-1條邊連接圖中的n個頂點；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達到最小。2、普利姆（Prim）算法：假設N=（V，{E}）是連通網(wǎng)，TE是N上最小生成樹種邊的集合。算法從U={u0}（U屬于V），TE={}開始，重復執(zhí)行下述操作；在所有u屬于U，v屬于V-U的邊（u，v）屬于E中找一條代價最小的邊（u0,v0）并入集合TE，同時v0并入U，直至U=V為止。此時TE中必有n-1條邊，則T=（V，{TE}）為N的最小生成樹。3、克魯斯卡爾（Kruskal）算法：假設連通網(wǎng)N=（V，{E}），則令最小生成樹的狀態(tài)為只有n個頂點而無邊的非連通圖T=（V，{}），圖中每個頂點自稱一個連通分量。在E中選擇代價最小的邊，如該邊依附的頂點落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至T中所有頂點都在同一連通分量上為止。第次課學時授課時間________教學主題求單源最短路徑的Dijkstra算法求多源最短路徑的Flody算法教學要求1、掌握最短路徑的概念和求最短路徑的Dijkstra和Flody算法。教學重點求單源最短路徑的Dijkstra算法求多源最短路徑的Flody算法教學難點求單源最短路徑的Dijkstra算法求多源最短路徑的Flody算法教學方法講授教學手段多媒體、板書講授要點1、求單源最短路徑的Dijkstra算法。2、求多源最短路徑的Flody算法。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記8.5最短路徑圖或網(wǎng)還經(jīng)常用于描述一個城市或城市間的交通運輸網(wǎng)絡，以圖中頂點表示一個城市或某個交通樞紐，以邊或弧表示兩地之間的交通狀況，邊或弧上的權(quán)值可表示各種相關(guān)信息，例如兩地之間的路程長度，交通費用或行程時間等等。那么對于網(wǎng)來說，兩個頂點之間的路徑長度就不再是前面章節(jié)中所定義的路徑中"弧的數(shù)目"，而是路徑中"弧的權(quán)值之和"。則當兩個頂點之間存在多條路徑時，其中必然存在一條"最短路徑"，即路徑中弧的權(quán)值和取最小值的那條路徑，本節(jié)就是討論如何求得這條最短路徑的算法。考慮到交通圖的有向性。1、最短路徑考慮帶權(quán)有向圖，把一條路徑（僅僅考慮簡單路徑）上所經(jīng)邊的權(quán)值之和定義為該路徑的路徑長度或稱帶權(quán)路徑長度。從源點到終點可能不止一條路徑，把路徑長度最短的那條路徑稱為最短路徑。2、求單源最短路徑的Dijkstra算法單源點路徑問題是指，已知一個有向網(wǎng)和網(wǎng)中某個源點，求得從該源點到圖中其它各個頂點之間的最短路徑。

例如圖G6中，從源點a到終點b存在多條路徑，如路徑{a,b}的長度為24，路徑{a,c,e,g,b}的長度為27等，其中以路徑{a,d,g,b}的長度(=22)為最短。類似地，從源點a到其它各頂點也都存在一條路徑長度最短的路徑，如右所列。

(有向網(wǎng)G6)如何求得這些最短路徑？迪杰斯特拉提出了一個"按各條最短路徑長度遞增的次序"產(chǎn)生最短路徑的算法。

從有向網(wǎng)的例子可見，如果從源點到某個終點存在路徑，必存在一條路徑長度取最小值的路徑，這些最短路徑彼此之間的長度不一定相等，則迪杰斯特拉算法正是按右側(cè)所列從源點a到其它各終點的最短路徑長度遞增的次序先后產(chǎn)生這些最短路徑。首先，在這些最短路徑中，長度最短的這條路徑上必定只有一條弧，且它的權(quán)值是從源點出發(fā)的所有弧上權(quán)的最小值。

其次，第二條長度次短的最短路徑只可能有兩種情況：它或者只含一條從源點出發(fā)的弧且弧上的權(quán)值大于已求得最短路徑的那條弧的權(quán)值，但小于其它從源點出發(fā)的弧上的權(quán)值；或者是一條只經(jīng)過已求得最短路徑的頂點的路徑，換句話說，如果第一條長度最短的最短路徑是從源點s到v1的話，若從v1到v2之間存在一條弧，且路徑{s,v1,v2}的長度比<s,v2>的權(quán)值小，則{s,v1,v2}是第二條長度次短的最短路徑。

依次類推，按迪杰斯特拉算法先后求得的每一條最短路徑必定只有兩種情況，或者是由源點直接到達終點，或者是只經(jīng)過已經(jīng)求得最短路徑的頂點到達終點。

例如，求從源點a到其它終點的最短路徑的過程如右動畫所示。從這個過程可見，類似于普里姆算法，在算法中應保存當前已得到的從源點到每個終點的最短路徑，它的初值為：如果從源點到該點有弧，則存在一條路徑，其路徑長度即為該弧上的權(quán)值，之后每求得一條到達某個終點w的"最短路徑"之后，就需要檢查一下，是否存在經(jīng)過這個頂點w的其它路徑(即是否存在從頂點w出發(fā)到尚未求得最短路徑頂點的弧)，如果存在，其長度是否比當前求得的路徑長度短，如果是，則應修改當前路徑。假設n為圖G=(V,E)中的頂點數(shù)，dist[n]存放從源點到每個終點當前最短路徑的長度，path[n]存放相應路徑，S為已求得最短路徑的終點的集合。則迪杰斯特拉算法求最短路徑的過程為：

(1)令S={vs};//為源點

并設定dist[i]的初始值為：

(2)選擇頂點vj使得dist[j]=Min{dist[k]|∈V-S}，并將頂點vj并入到集合S中，

(3)對集合V-S中所有頂點vk，若存在從vj指向該頂點的弧，且dist[j]+wjk<dist[k]，則修改dist[j]和path[k]的值。

(4)重復(2)和(3)直至求得從源點到所有其它頂點的最短路徑為止。從源點a到圖中其它各終點的最短路徑按路徑長度從短到長依次為：

路徑{a,c}的長度為8，

路徑{a,c,f}的長度為11，

路徑{a,c,f,e}的長度為13，

路徑{a,d}的長度為15，

路徑{a,d,g}的長度為19，

路徑{a,d,g,b}的長度為22。這應該是可以理解的，因為若它是由經(jīng)過其它頂點構(gòu)成的路徑，那么必定不是所有最短路徑中長度最短的那條。3、求多源最短路徑的Floyd算法如果希望求得圖中任意兩個頂點之間的最短路徑，顯然只要依次將每個頂點設為源點，調(diào)用迪杰斯特拉算法n次便可求出，其時間復雜度為O(n3)。弗洛伊德提出了另外一個算法，雖然其時間復雜度也是O(n3)，但算法形式更簡單。

弗洛伊德算法的基本思想是求得一個n階方陣的序列

D(-1),D(0),D(1),…,D(k),…,D(n-1)

其中：D(-1)[i][j]表示從頂點vi不經(jīng)過其它頂點直接到達頂點vj的路徑長度，即

D(-1)[i][j]=G.arcs[i][j]，

D(k)[i][j]則表示中間只可能經(jīng)過v0,v1,…,vk等頂點，且不可能經(jīng)過vk+1,vk+2,…,vn-1等頂點的最短路徑長度。

由此，D(n-1)[i][j]自然是從頂點vi到頂點vj的最短路徑長度。

為了記下路徑，和上列路徑長度序列相對應有路徑的方陣序列

P(-1),P(0),P(1),…,P(k),…,P(n-1)

弗洛伊德算法的基本操作為：

if(D[i][k]+D[k][j]<D[i][j])

{

D[i][j]=D[i][k]+D[k][j];

P[i][j]=P[i][k]+P[k][j]

}

其中k表示在路徑中新增添考慮的頂點號，i為路徑的起始頂點號，j為路徑的終止頂點號。

第次課學時授課時間________教學主題拓撲排序算法；AOE網(wǎng)的含義和關(guān)鍵路徑教學要求1、掌握拓撲排序過程。2、掌握關(guān)鍵路徑的定義及其構(gòu)造過程。教學重點拓撲排序算法；關(guān)鍵路徑的定義及其構(gòu)造過程教學難點拓撲排序算法；關(guān)鍵路徑的定義及其構(gòu)造過程教學方法講授+練習教學手段多媒體、上機實操講授要點1、拓撲排序的意義及其算法設計。2、AOE網(wǎng)的含義和關(guān)鍵路徑的定義。3、求關(guān)鍵路徑的過程。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首