数据基础结构 3

教案纸（首页）第1页第次课学时授课时间___________教学主题图的基本概念；图的存储结构；教学要求1、掌握图的定义及其逻辑结构特性，图抽象数据类型的描述方法。2、掌握图的基本术语及其含义。3、掌握图的邻接矩阵和邻接表两种主要的存储结构及其特点。4、掌握栈在实际求解问题中的应用方法。教学重点图的特点；图的概念，包括完全图、路径、连通图、强联通分量；图的邻接矩阵和邻接表教学难点完全图，路径，强连通分量等重要概念；图的邻接矩阵和邻接表教学方法讲授教学手段多媒体、板书讲授要点1、图的定义及图抽象数据类型的描述方法。2、图基本术语的定义及其含义。3、图的邻接矩阵和邻接表两种存储结构。4、基于图邻接矩阵和邻接表存储结构的基本算法设计。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记8.1图的概念1、图的定义图（Graph）G由顶点集合V(G)和边集合E(G)构成。图是现实问题的抽象，例如哥尼斯堡七桥问题（介绍问题背景）在图G中，如果代表边的顶点对是无序的，则称G为无向图。用圆括号序偶表示无向边。如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。2、图的常用术语顶点的度无向图中，以顶点i为端点的边数称为该顶点的度。有向图中，以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。完全图无向图中，每两个顶点之间都存在着一条边，称为完全无向图，包含有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)路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。连通、连通图和连通分量无向图中：若从顶点i到顶点j有路径，则称顶点i和j是连通的。若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。强连通图和强连通分量有向图中：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图。权和网图中每一条边都可以附带有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。8.2图的存储结构1、图的两种存储结构邻接表类似于树的孩子链表，将和同一顶点"相邻接"的所有邻接点链接在一个单链表中，单链表的头指针则和顶点信息一起存储在一个一维数组中。图的邻接表存储表示

constMAX_VERTEX_NUM=20;

typedefstructArcNode{//弧结点的结构

intadjvex;//该弧所指向的顶点的位置

structArcNode*nextarc;//指向下一条弧的指针

VRTypeweight;//与弧相关的权值，无权则为0

InfoType*info;//指向该弧相关信息的指针

};

typedefstructVNode{//顶点结点的结构

VertexTypedata;//顶点信息

ArcNode*firstarc;//指向第一条依附该顶点的弧

}AdjList[MAX_VERTEX_NUM];

typedefstruct{//图的邻接表结构定义

AdjListvertices;//顶点数组

intvexnum,arcnum;//图的当前顶点数和弧数

GraphKindkind;//图的种类标志

}ALGraph;(忽略相关信息指针)邻接矩阵将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。constINFINITY=INT_MAX;//最大值∞

constMAX_VERTEX_NUM=20;//最大顶点个数

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

//类型标志{有向图,有向网,无向图,无向网}

typedefstructArcCell{//弧的定义

VRTypeadj;//VRType是顶点关系类型。

//对无权图，用1或0表示相邻否；对带权图，则为权值类型。

InfoType*info;//该弧相关信息的指针

}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct{//图的定义

VertexTypevexs[MAX_VERTEX_NUM];//顶点信息

AdjMatrixarcs;//表示顶点之间关系的二维数组

intvexnum,arcnum;//图的当前顶点数和弧(边)数

GraphKindkind;//图的种类标志

}MGraph;

第次课学时授课时间________教学主题图的遍历及图遍历算法的应用教学要求1、掌握图的深度优先和广度优先遍历算法。2、掌握图遍历算法的应用。教学重点图的深度优先遍历和广度优先遍历算法教学难点图的深度优先遍历和广度优先遍历算及其应用教学方法讲授+练习教学手段多媒体、上机实操讲授要点1、图遍历的概念。2、图的深度优先遍历算法及其在图搜索算法设计中的应用。3、图的广度优先遍历算法及其在图搜索算法设计中的应用。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记8.3图的遍历图的遍历从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。图的遍历得到的顶点序列称为图遍历序列。2、深度优先遍历（1）从图中某个初始顶点v出发，首先访问初始顶点v。（2）选择一个与顶点v相邻且没被访问过的顶点w，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。采用邻接表的DFS算法实现：voidDFS(AdjGraph*G，intv){ArcNode*p;intw;visited[v]=1; //置已访问标记printf("%d"，v); //输出被访问顶点的编号p=G->adjlist[v].firstarc; //p指向顶点v的第一条边的边头结点while(p!=NULL){w=p->adjvex;if(visited[w]==0)DFS(G，w); //若w顶点未访问，递归访问它p=p->nextarc; //p指向顶点v的下一条边的边头结点}}3、广度优先遍历（1）访问初始点v，接着访问v的所有未被访问过的邻接点v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，访问每一个顶点的所有未被访问过的邻接点。（3）依次类推，直到图中所有和初始点v有路径相通的顶点都被访问过为止。采用邻接表的BFS算法：voidBFS(AdjGraph*G，intv){intw，i;ArcNode*p;SqQueue*qu; //定义环形队列指针InitQueue(qu); //初始化队列intvisited[MAXV]; //定义顶点访问标记数组for(i=0;i<G->n;i++)visited[i]=0; //访问标记数组初始化printf("%2d"，v); //输出被访问顶点的编号visited[v]=1; //置已访问标记enQueue(qu，v);while(!QueueEmpty(qu)) //队不空循环{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、图的遍历算法的应用利用图的遍历求解迷宫问题。广度优先遍历找到的路径一定是最短路径，而深度优先遍历则不一定。深度优先遍历能找所有路径，而广度优先遍历难以实现。教学总结：本章节主要介绍了图的遍历及图遍历算法的应用。第次课学时授课时间________教学主题最小生成树的定义；最小生成树的Prim和Kruskal算法教学要求1、掌握生成树和最小生成树的定义。2、掌握求最小生成树的Prim和Kruskal算法。教学重点最小生成树的定义；Prim和Kruskal算法教学难点求最小生成树的Prim和Kruskal算法教学方法讲授教学手段多媒体、板书讲授要点1、生成树、深度优先生成树和广度优先生成树的概念。2、最小生成树的定义，求最小生成树的Prim和Kruskal算法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记8.4生成树和最小生成树1、生成树的概念一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。最小生成树：对于带权连通图G（每条边上的权均为大于零的实数），可能有多棵不同生成树。每棵生成树的所有边的权值之和可能不同。其中权值之和最小的生成树称为图的最小生成树。构造最小生成树的准则必须使用且仅使用该连通图中的n-1条边连接图中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。2、普利姆（Prim）算法：假设N=（V，{E}）是连通网，TE是N上最小生成树种边的集合。算法从U={u0}（U属于V），TE={}开始，重复执行下述操作；在所有u属于U，v属于V-U的边（u，v）属于E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树。3、克鲁斯卡尔（Kruskal）算法：假设连通网N=（V，{E}），则令最小生成树的状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自称一个连通分量。在E中选择代价最小的边，如该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。第次课学时授课时间________教学主题求单源最短路径的Dijkstra算法求多源最短路径的Flody算法教学要求1、掌握最短路径的概念和求最短路径的Dijkstra和Flody算法。教学重点求单源最短路径的Dijkstra算法求多源最短路径的Flody算法教学难点求单源最短路径的Dijkstra算法求多源最短路径的Flody算法教学方法讲授教学手段多媒体、板书讲授要点1、求单源最短路径的Dijkstra算法。2、求多源最短路径的Flody算法。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记8.5最短路径图或网还经常用于描述一个城市或城市间的交通运输网络，以图中顶点表示一个城市或某个交通枢纽，以边或弧表示两地之间的交通状况，边或弧上的权值可表示各种相关信息，例如两地之间的路程长度，交通费用或行程时间等等。那么对于网来说，两个顶点之间的路径长度就不再是前面章节中所定义的路径中"弧的数目"，而是路径中"弧的权值之和"。则当两个顶点之间存在多条路径时，其中必然存在一条"最短路径"，即路径中弧的权值和取最小值的那条路径，本节就是讨论如何求得这条最短路径的算法。考虑到交通图的有向性。1、最短路径考虑带权有向图，把一条路径（仅仅考虑简单路径）上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径，把路径长度最短的那条路径称为最短路径。2、求单源最短路径的Dijkstra算法单源点路径问题是指，已知一个有向网和网中某个源点，求得从该源点到图中其它各个顶点之间的最短路径。

例如图G6中，从源点a到终点b存在多条路径，如路径{a,b}的长度为24，路径{a,c,e,g,b}的长度为27等，其中以路径{a,d,g,b}的长度(=22)为最短。类似地，从源点a到其它各顶点也都存在一条路径长度最短的路径，如右所列。

(有向网G6)如何求得这些最短路径？迪杰斯特拉提出了一个"按各条最短路径长度递增的次序"产生最短路径的算法。

从有向网的例子可见，如果从源点到某个终点存在路径，必存在一条路径长度取最小值的路径，这些最短路径彼此之间的长度不一定相等，则迪杰斯特拉算法正是按右侧所列从源点a到其它各终点的最短路径长度递增的次序先后产生这些最短路径。首先，在这些最短路径中，长度最短的这条路径上必定只有一条弧，且它的权值是从源点出发的所有弧上权的最小值。

其次，第二条长度次短的最短路径只可能有两种情况：它或者只含一条从源点出发的弧且弧上的权值大于已求得最短路径的那条弧的权值，但小于其它从源点出发的弧上的权值；或者是一条只经过已求得最短路径的顶点的路径，换句话说，如果第一条长度最短的最短路径是从源点s到v1的话，若从v1到v2之间存在一条弧，且路径{s,v1,v2}的长度比<s,v2>的权值小，则{s,v1,v2}是第二条长度次短的最短路径。

依次类推，按迪杰斯特拉算法先后求得的每一条最短路径必定只有两种情况，或者是由源点直接到达终点，或者是只经过已经求得最短路径的顶点到达终点。

例如，求从源点a到其它终点的最短路径的过程如右动画所示。从这个过程可见，类似于普里姆算法，在算法中应保存当前已得到的从源点到每个终点的最短路径，它的初值为：如果从源点到该点有弧，则存在一条路径，其路径长度即为该弧上的权值，之后每求得一条到达某个终点w的"最短路径"之后，就需要检查一下，是否存在经过这个顶点w的其它路径(即是否存在从顶点w出发到尚未求得最短路径顶点的弧)，如果存在，其长度是否比当前求得的路径长度短，如果是，则应修改当前路径。假设n为图G=(V,E)中的顶点数，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。这应该是可以理解的，因为若它是由经过其它顶点构成的路径，那么必定不是所有最短路径中长度最短的那条。3、求多源最短路径的Floyd算法如果希望求得图中任意两个顶点之间的最短路径，显然只要依次将每个顶点设为源点，调用迪杰斯特拉算法n次便可求出，其时间复杂度为O(n3)。弗洛伊德提出了另外一个算法，虽然其时间复杂度也是O(n3)，但算法形式更简单。

弗洛伊德算法的基本思想是求得一个n阶方阵的序列

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

其中：D(-1)[i][j]表示从顶点vi不经过其它顶点直接到达顶点vj的路径长度，即

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

D(k)[i][j]则表示中间只可能经过v0,v1,…,vk等顶点，且不可能经过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网的含义和关键路径教学要求1、掌握拓扑排序过程。2、掌握关键路径的定义及其构造过程。教学重点拓扑排序算法；关键路径的定义及其构造过程教学难点拓扑排序算法；关键路径的定义及其构造过程教学方法讲授+练习教学手段多媒体、上机实操讲授要点1、拓扑排序的意义及其算法设计。2、AOE网的含义和关键路径的定义。3、求关键路径的过程。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首