自考数据结构02142-第五章ppt课件.ppt

《自考数据结构02142-第五章ppt课件.ppt》由会员分享，可在线阅读，更多相关《自考数据结构02142-第五章ppt课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第第五五章章 图图5 5.1.1 图的基本概念图的基本概念5 5.2.2 图的存储结构图的存储结构5 5.3.3 图的遍历图的遍历5 5.4.4 图的应用图的应用在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确一、图的定义一、图的定义图图G G 是由集合是由集合V V和和E E组成，记成组成，记成G=G=（V V，E E）其中：其中：V V 顶点集顶点集（非空）；（非空）；E E 边集边集（可空）。（可空）。边是顶点的有序对或无

2、序对。边是顶点的有序对或无序对。（边反映了两顶点之间的关系）（边反映了两顶点之间的关系）有向图有向图：边是顶点的有序对的图。：边是顶点的有序对的图。（图中每条边都用箭头指明了方向）（图中每条边都用箭头指明了方向）无向图无向图：边是顶点的无序对的图。：边是顶点的无序对的图。5.1 5.1 图的基本概念图的基本概念在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确例：例：V(G1)=1，2，3，4E(G1)=(1,2)，(1,3)，(1,4)，(2,3)，(2,4)，(3,4)（图（图G1）（无向图）（无向图）V(G2)=1，2，3，4，5

3、，6，7E(G2)=(1,2)，(1,3)，(2,4)，(2,5)，(3,6)，(3,7)（图（图G2）V(G3)=1，2，3E(G3)=，（图（图G3）（有向图）（有向图）注：注：1 1）边集可空；）边集可空；2 2）边集中不允许出现相同的边。）边集中不允许出现相同的边。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确二、图的基本术语二、图的基本术语顶点顶点(Vertex)(Vertex)图中的数据元素；图中的数据元素；V有向图中有向图中,顶点顶点V Vi i到到 顶点顶点V Vj j的边的边,也称也称弧弧；弧弧头头（终端点）：箭头

4、端；（终端点）：箭头端；弧弧尾尾（初始点）：无箭头端；（初始点）：无箭头端；完全图完全图无向完全图：无向完全图：边数边数=n*(n-1)/2=n*(n-1)/2的无向图；的无向图；有向完全图：有向完全图：边数边数=n*(n-1)=n*(n-1)的有向图；的有向图；(顶点数顶点数n)n)权权图的边附带的数值图的边附带的数值（可表示从一个顶点到另一（可表示从一个顶点到另一 顶点的距离、代价等）顶点的距离、代价等）子图子图图图G G和和G,G,若有若有V(G)V(G)V(G)V(G)和和 E(G)E(G)E(G),(G),则称则称GG为图为图G G的子图。的子图。（图（图G1）（图（图G2）（图（图

5、G3）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确邻接邻接若若(V(Vi i,V,Vj j)E(G)E(G)，则称，则称V Vi i和和V Vj j互为邻接点互为邻接点;关联关联若若(V(Vi i,V,Vj j)E(G)E(G)，则称边，则称边(V(Vi i,V,Vj j)关联于关联于顶顶 点点V Vi i和和V Vj j;注：注：1 1）邻接是指顶点之间的关系，而关联是指边）邻接是指顶点之间的关系，而关联是指边与与 顶点间的关系。顶点间的关系。2 2）若弧）若弧VE(G)E(G)，则称，则称V Vj j是是V Vi i的邻接点的

6、邻接点度度无向图：顶点无向图：顶点V Vi i的度为与的度为与V Vi i相关联的边的个数；相关联的边的个数；D(VD(Vi i)有向图有向图出度出度:顶点顶点V Vi i的出度为以的出度为以V Vi i为尾的出边数；为尾的出边数；OD(VOD(Vi i)入度入度:顶点顶点V Vi i的入度为以的入度为以V Vi i为头的入边数；为头的入边数；ID(VID(Vi i)度度:有向图的度有向图的度=入度入度+出度；出度；D(VD(Vi i)D(V D(Vi i)=OD(V)=OD(Vi i)+ID(V)+ID(Vi i)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，

7、由浅入深，所提出的问题也很明确注：注：图中边数图中边数e e与顶点的度的关系与顶点的度的关系 e=e=2 21 1ni=1i=1D（Vi）（一边带二度，两度组成一边）（一边带二度，两度组成一边）路径路径图中，顶点图中，顶点VpVp至顶点至顶点VqVq的路径是顶点序列的路径是顶点序列 Vp,V Vp,Vi1i1,V,Vi2i2,V,Vinin,Vq ,Vq 且且 对无向图，边对无向图，边(Vp,V(Vp,Vi1i1),(V),(Vi1i1,V,Vi2i2),(V),(Vinin,Vq)VR(G);,Vq)VR(G);对有向图，弧对有向图，弧Vp,V,VR(G);,VqVR(G);路径长度路径长度

8、路径上边或弧的数目；路径上边或弧的数目；简单简单路径路径序列中顶点不重复出现的路径；序列中顶点不重复出现的路径；在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确回路回路第一个和最后一个顶点相同的路径，也称环；第一个和最后一个顶点相同的路径，也称环；简单回路简单回路除第一个和最后一个外，其余各顶除第一个和最后一个外，其余各顶 点均不相同的点均不相同的回路回路；注：回路中可以有多个圈，而简单回路只能有一个圈。注：回路中可以有多个圈，而简单回路只能有一个圈。连通连通无向图中，若从顶点无向图中，若从顶点V Vi i到到V Vj j顶点有路顶点

9、有路径，则称径，则称V Vi i和和V Vj j是连通的。是连通的。连通图连通图和和连通分量连通分量针对无向图而言针对无向图而言在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确l生成树生成树含有该连通图的全部顶点的一含有该连通图的全部顶点的一个极个极 小连通子图小连通子图 若连通图若连通图G G的顶点个数为的顶点个数为n n，则，则G G的生成的生成树的树的边边数为数为n-1n-1。G G的子图的子图GG边数大于边数大于n-1,

10、n-1,则则GG中一定中一定有环有环。G G的子图的子图GG边数小于边数小于n-1,n-1,则则GG中一定中一定不连通。不连通。l生成森林生成森林在非连通图中，每个连通分在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图成树。这些生成树就组成了一个非连通图的生成森林。的生成森林。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确图的基本运算图的基本运算建立图建立图GreateGraph(G,V,E)GreateGraph(G,V,E)取顶点信息取顶点信息G

11、etvex(G,u)Getvex(G,u)取边信息取边信息Getarc(G,u,v)Getarc(G,u,v)查询第一个邻接点查询第一个邻接点FirstVex(G,u)FirstVex(G,u)查询下一个邻接点查询下一个邻接点NextVex(G,u,v)NextVex(G,u,v)插入顶点插入顶点InsertVex(G,v)InsertVex(G,v)删除顶点删除顶点DeleteVex(G,v)DeleteVex(G,v)插入边插入边InsertArc(G,v,w)InsertArc(G,v,w)删除边删除边DeleteArc(G,v,w)DeleteArc(G,v,w)遍历图遍历图Trave

12、rs(G,tag)Travers(G,tag)在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.2.1 5.2.1 邻接矩阵表示法邻接矩阵表示法 5.2 5.2 图的存储结构图的存储结构1 1、图的邻接矩阵、图的邻接矩阵 表示图的各顶点之间关系的矩阵。表示图的各顶点之间关系的矩阵。定义定义 设设G=(V,E)G=(V,E)是是n n个顶点的图，则个顶点的图，则G G的的 邻接矩阵为下列邻接矩阵为下列n n阶方阵：阶方阵：Aij=1若若(V(Vi i,V,Vj j)或或 VE(G)E(G)0否则否则 在整堂课的教学中，刘教师总是让学生

13、带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确G1=0111101011011010（图（图G1）（图（图G2）010101000G2=例：例：结论：结论：（1 1）无向图的邻接矩阵是对称的；）无向图的邻接矩阵是对称的；（(V(Vi i,V,Vj j)E(G)E(G)，则，则(V(Vj j,V,Vi i)E(G)E(G)）（2 2）从邻接矩阵容易判断任意两顶点间是否有边相联；）从邻接矩阵容易判断任意两顶点间是否有边相联；容易求出各顶点的度；容易求出各顶点的度；无向图：无向图：顶点顶点V Vi i的度的度D(VD(Vi i)=)=矩阵中第矩阵中第i i行的行的1 1总

14、和总和 有向图：有向图：OD(VOD(Vi i)=)=矩阵中第矩阵中第i i行的行的1 1总和总和 ID(VID(Vi i)=)=矩阵中第矩阵中第i i列的列的1 1总和总和在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2、带权图带权图(网网)的邻接矩阵的邻接矩阵 Aij=Aij=w wijij 若若(V(Vi i,V,Vj j)或或 VE(G)E(G)V Vi i、V Vj j间无边或弧间无边或弧（W Wijij为边或弧的权为边或弧的权）3 3、邻接矩阵的类型定义、邻接矩阵的类型定义 c const int vnum=20;o

15、nst int vnum=20;const int MAX_INT=32767;const int MAX_INT=32767;Typedef struct gpTypedef struct gp VertexType vexsvnum;VertexType vexsvnum;/顶点信息顶点信息 WeightType WeightType arcsvnumvnum;arcsvnumvnum;/带权带权邻接邻接矩阵矩阵 int vexnum,arcnum;int vexnum,arcnum;/顶点数，边数顶点数，边数 W WGraph;Graph;在整堂课的教学中，刘教师总是让学生带着问题来学习

16、，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确将矩阵将矩阵A A的每个元素都初始化为最大值。的每个元素都初始化为最大值。然后读入边和权值（然后读入边和权值（i i，j j，w wijij），将），将A A的相应元素的相应元素设为设为w wijij。算法如下：。算法如下：4 4、建立无向带权邻接矩阵：、建立无向带权邻接矩阵：VoidCreatGraph(Graph*g)inti,j,n,e,w;charch;scanf(“%d%d”,&n,&e);g-vexnum=n;g-arcnum=e;for(i=0;ivexnum;i+)scanf(“%c”,&ch);g-vexsi=ch;

17、for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)g-arcsij=MAX_INT;for(k=0;karcnum;k+)scanf(“%d%d%d”,&i,&j,&w);g-arcsij=w;g-arcsji=w;在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1.定义：定义：对图对图G G中每个顶点都建立一个单链表，第中每个顶点都建立一个单链表，第i i个个2.2.单链表（称单链表（称边表边表）链接图中与顶点链接图中与顶点V Vi i相邻接的所有相邻接的所有顶点。顶点。结点形式：结点形式：邻接点域邻接点域

18、（顶点域）：（顶点域）：存放与顶点存放与顶点V Vi i相邻接相邻接顶点顶点V Vj j的序号的序号j j；链域链域：指向：指向V Vi i的下一个邻接点；的下一个邻接点；每个链表均设一表头结点（以向量存储，称每个链表均设一表头结点（以向量存储，称顶点表顶点表）表头结点：表头结点：ViVi第第i i个链表的表头结点；个链表的表头结点；Vi.vertex Vi.vertex 存放顶点存放顶点V Vi i的信息；的信息；Vi.Vi.firstarc 指向指向V Vi i的邻接链表的第一个结点。的邻接链表的第一个结点。5.2.2 5.2.2 邻接表表示法邻接表表示法 在整堂课的教学中，刘教师总是让学

19、生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.结论：结论：1 1）n n个顶点个顶点、e e条边条边的无向图，则其邻接表的表头的无向图，则其邻接表的表头结点数为结点数为n n，链表结点总数为链表结点总数为2e2e；2 2）对于）对于无向图，第无向图，第i i个链表的结点数为顶点个链表的结点数为顶点V Vi i的度的度；对于对于有向图，第有向图，第i i个链表的结点数为顶点个链表的结点数为顶点V Vi i的出的出度；度；3 3）在边稀疏时，邻接表比邻接矩阵省单元；）在边稀疏时，邻接表比邻接矩阵省单元；4 4）邻接表表示在检测边数方面比邻接矩阵表示效）邻接表表示在

20、检测边数方面比邻接矩阵表示效率率 要高。要高。2.例：例：（P136图图5-10中中G2的邻接表）的邻接表）（P137图图5-11中中G1的邻接表）的邻接表）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确0 01 12 23 34 40241341212表头向量表头向量 adjlist adjlistV V1 1V V2 2V V3 3V V4 4V V5 5 例：例：0 01 12 2表头向量表头向量 adjlist adjlist102在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出

21、的问题也很明确4.4.邻接表的类型定义：邻接表的类型定义：#definevnum20Typedefstructarcnodeintadjvex;/下一条边的顶点编号下一条边的顶点编号WeightTypeweight;/带权图的权值域带权图的权值域structarcnode*nextarc；/指向下一条边的指针指向下一条边的指针ArcNode;Typedefstructvexnodeintvertex;/顶点编号顶点编号ArcNode*firstarc;/指向第一条边的指针指向第一条边的指针AdjListvnum;TypedefstructgpAdjListadjlist;intvexnum,a

22、rcnum;/顶点和边的个数顶点和边的个数Graph;在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确对于对于无向图，第无向图，第i i个链表的结点数为顶点个链表的结点数为顶点V Vi i的度的度；对于对于有向图，第有向图，第i i个链表的结点数只为顶点个链表的结点数只为顶点V Vi i的出度；的出度；若要求入度，必须遍历整个邻接表。在单链表中，其若要求入度，必须遍历整个邻接表。在单链表中，其邻接点域的值为邻接点域的值为i i的结点个数是顶点的结点个数是顶点V Vi i的入度。的入度。对于有向图，有时候就要建立一个对于有向图，有时候就

23、要建立一个逆逆邻接表。即邻接表。即对对每每个顶点个顶点V Vi i建立一个以建立一个以V Vi i为弧头的邻接点的链表。这样，为弧头的邻接点的链表。这样，逆邻接表第逆邻接表第i i个单链表中的结点个数就是个单链表中的结点个数就是V Vi i的入度。的入度。5.5.计算计算图的度图的度例：图例：图5-2中中G1的邻接表和逆邻接表见的邻接表和逆邻接表见P137图图5-11在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确结点形式：结点形式：6.6.带权图邻接表带权图邻接表adjvex weight nextarc权值域：用于存储边的权值权值

24、域：用于存储边的权值画出画出图图5-1a5-1a无向带权图的邻接表。无向带权图的邻接表。图图5-8a5-8a有向带权图的邻接表、逆邻接表。有向带权图的邻接表、逆邻接表。建立有向图的邻接表的方法：建立有向图的邻接表的方法：l将邻接表表头数组初始化将邻接表表头数组初始化;l第第i i个表头的个表头的vertexvertex域初始化为域初始化为i i；lfirstfirst域初始化为域初始化为NULL;NULL;l读入顶点对读入顶点对,产生一个表结点；产生一个表结点；l将将j j放入到该结点的放入到该结点的adjvexadjvex域；域；l将该结点链到邻接表的表头数组的第将该结点链到邻接表的表头数组

25、的第i i个元素的个元素的firstfirst域上。域上。建立有向图的邻接表算法见P138在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.3 5.3 图的遍历图的遍历遍历的含义及方法：遍历的含义及方法：图的遍历图的遍历从图从图G中某一顶点中某一顶点v出发，出发，顺顺序访问各顶点一次。序访问各顶点一次。方法：方法：深度优先搜索法深度优先搜索法广度优先搜索法广度优先搜索法为克服顶点的重复访问，设立辅助数组为克服顶点的重复访问，设立辅助数组visitedn。1顶点顶点i已被访问过已被访问过0顶点顶点i未被访问过未被访问过visitedi

26、=遍历方法遍历方法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.3.1 5.3.1 深度优先搜索法（深度优先搜索法（DFSDFS）一、过程一、过程 从图从图G(V,E)G(V,E)中任一顶点中任一顶点V Vi i开始，首先访问开始，首先访问V Vi i，然后访问，然后访问V Vi i的的任任一未访问过的邻接点一未访问过的邻接点V Vj j，再以，再以V Vj j为新的出发点继续进为新的出发点继续进行深度优先搜索，直到所有顶点都被访问过。行深度优先搜索，直到所有顶点都被访问过。二、例：二、例：三、算法：三、算法：分析：分析：a、为

27、克服顶点的重复访问，设立一标志向量、为克服顶点的重复访问，设立一标志向量visited n;b、图可用邻接矩阵或邻接表表示；、图可用邻接矩阵或邻接表表示；从从V V1 1出发出发,DFS:V1，V2，V4，V5，V3，V6V V4 4V V1 1V V2 2V V3 3V V5 5V V6 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确注意：注意：搜索到达某个顶点时搜索到达某个顶点时(图中仍有顶点未被访问图中仍有顶点未被访问)，如果，如果这个顶点的所有邻接点都被访问过，那么搜索就要回这个顶点的所有邻接点都被访问过，那么搜索就要回到

28、前一个被访问过的顶点，再从该顶点的下一未被访到前一个被访问过的顶点，再从该顶点的下一未被访问的邻接点开始深度优先搜索。；问的邻接点开始深度优先搜索。；深度搜索的顶点的访问序列深度搜索的顶点的访问序列不是唯一的不是唯一的。连通图的深度优先搜索的算法连通图的深度优先搜索的算法:Dfs(Graphg,intv)访问访问v；visitedv=1;/visitedv初值都为初值都为0，顶点，顶点v已被访问，就置为已被访问，就置为1找出找出g中中v的第一个邻接点的第一个邻接点w；while(w存在存在)ifw未被访问未被访问Dfs(g,w);w=g中中v的下一个邻接点；的下一个邻接点；在整堂课的教学中，刘

29、教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确深度优先搜索法算法：深度优先搜索法算法：对图按深度优先遍历的递归算法（对图按深度优先遍历的递归算法（邻接表邻接表）：）：intvisitedN=0;/*对访问标记对访问标记visited数组初始化数组初始化*/Dfs(Graphg,intv)/从从第第v个个顶顶点点出出发发递递归归地地深深度度优优先先遍遍历历图图g，图图以以邻邻接接表表作作为为存存储结构储结构ArcNode*p;printf(“%d”,v);/*访问起始顶点访问起始顶点v*/visitedv=1;/*置置“已访问已访问”标记标记*/p=g.

30、adjlistv.firstarc;/*取顶点表中取顶点表中v的边表头指针的边表头指针*/while(p!=NULL)/*依次搜索依次搜索v的邻接点的邻接点*/if(!visitedp-adjvex)/*v的一个邻接点未被访问的一个邻接点未被访问*/Dfs(g,p-adjvex);/*沿此沿此邻接点出发继续邻接点出发继续DFS*/p=p-nextarc;/*取取v的下一个邻接点的下一个邻接点*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7

31、70 01 12 23 34 45 56 67 70340561717262534表头向量表头向量 adjlist adjlist从从V V0 0出发出发,深度优先搜索深度优先搜索:V V0 0，V V1 1，在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确深度优先搜索法算法：深度优先搜索法算法：对图按深度优先遍历的递归算法对图按深度优先遍历的递归算法（邻接矩阵邻接矩阵）：）：intvisitedN=0;/*对访问标记对访问标记visited数组初始化数组初始化*/Dfs(Graphg,intv)/从从第第v个个顶顶点点出出发发递递归

32、归地地深深度度优优先先遍遍历历图图g，图图以以邻邻接接矩矩阵阵作作为为存存储储结构结构intj;printf(“%d”,v);/*访问起始顶点访问起始顶点v*/visited v=1;/*置置“已访问已访问”标记标记*/for(j=0;jarcsvj;/*顺序访问矩阵的第顺序访问矩阵的第v行结点行结点*/if（m&!visitedj）/*如果如果v与与j邻接，且邻接，且j未被访问未被访问*/Dfs(g,j);/*递归访问递归访问j*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确5.3.2广度优先搜索法（广度优先搜索法（BFS）一、

33、过程一、过程从图从图G(V,E)中某一点中某一点Vi出发，首先访问出发，首先访问Vi的所的所有邻接点（有邻接点（w1，w2，wt），然后再顺序访问），然后再顺序访问w1，w2，wt的的所有未被访问过的邻接点所有未被访问过的邻接点.,重复重复此过程直到所有顶点都被访问过。此过程直到所有顶点都被访问过。二、例：二、例：三、算法：三、算法：分析：分析：a、为克服顶点的重复访问，设立一标志、为克服顶点的重复访问，设立一标志向量向量visited n;b、图可用邻接矩阵或邻接表表示；、图可用邻接矩阵或邻接表表示；c、顶点的处理次序、顶点的处理次序先进先出，故先进先出，故需需用到用到一队列一队列从从V V

34、1 1出发出发,BFS:V1，V2，V3，V4，V5，V6V V4 4V V1 1V V2 2V V3 3V V5 5V V6 6在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确广度优先遍历算法基本思想：广度优先遍历算法基本思想：1.1.所有结点标记置为所有结点标记置为“未被访问未被访问”标志；标志；2.2.访问起始顶点，同时置起始顶点访问起始顶点，同时置起始顶点“已访问已访问”标记标记;3.3.将起始顶点进队列；将起始顶点进队列；4.4.当队列不为空时重复执行以下步骤；当队列不为空时重复执行以下步骤；1 1）取当前队头顶点；）取当前

35、队头顶点；2 2）对与队头顶点相邻接的所有未被访问过）对与队头顶点相邻接的所有未被访问过 的顶点依次做：的顶点依次做：(a)(a)访问该顶点；访问该顶点；(b)(b)置该顶点为置该顶点为“已访问已访问”标记标记,并将它进队列；并将它进队列；3 3）当前队头元素顶点出队；）当前队头元素顶点出队；4)4)重复进行，直到队空时结束。重复进行，直到队空时结束。广度优先遍历算法广度优先遍历算法：intvisitedN=0;/*对访问标记对访问标记visited数组初始化数组初始化*/intqueueN;/*队列队列queue存放已访问过的顶点存放已访问过的顶点*/在整堂课的教学中，刘教师总是让学生带着问

36、题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确对图按广度优先遍历的算法：对图按广度优先遍历的算法：bfs(Graph g,int vbfs(Graph g,int v )/从顶点从顶点v v出发，按广度优先遍历图出发，按广度优先遍历图g g，图用，图用邻接表邻接表表示表示 printf(“%d”,v printf(“%d”,v ););visited visited v=1;v=1;/*/*访问初始顶点访问初始顶点v vi i*/*/rear=1;front=0;rear=1;front=0;queuerear=v;queuerear=v;/*/*起始顶点（序号）入队起始

37、顶点（序号）入队*/*/while(front!=rear)while(front!=rear)/*/*队列不空，则循环队列不空，则循环*/*/front=(front+1)%N;front=(front+1)%N;/*/*置队头置队头*/*/v=queuefront;v=queuefront;/*/*队头元素出队队头元素出队*/*/p=g.adjlistv.firstarc;p=g.adjlistv.firstarc;/*/*取取刚刚出出队队顶顶点点v v的的边边表表的的头指针头指针*/*/while(p!=NULL)while(p!=NULL)/*/*依次搜索依次搜索v v的邻接点的邻接点

38、*/*/if if(!(!visitedp-adjvex)visitedp-adjvex)/*v/*v的的一一个个邻邻接接点点未未被访问被访问*/*/printf printf(“%d”,p-adjvex)(“%d”,p-adjvex)/*/*访访问问此此邻邻接接点点*/*/visitedp-adjvex=1;visitedp-adjvex=1;rear=(rear+1)%N;rear=(rear+1)%N;/*/*队尾指针增队尾指针增1*/1*/queuerear=p-adjvex;queuerear=p-adjvex;/*/*访问过的顶点入队访问过的顶点入队*/*/p=p-nextarc;

39、p=p-nextarc;/*/*找找v v的下一个邻接点的下一个邻接点*/*/*bfs*/*bfs*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确V V0 0V V1 1V V2 2V V3 3V V4 4V V5 5V V6 6V V7 70 01 12 23 34 45 56 67 70340561717262534表头向量表头向量 adjlist adjlist从从V V0 0出发出发,广度优先搜索广度优先搜索:V V0 0，在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题

40、也很明确Bfs(Graphg,intv)LkQueQ;/Q为链队列intj;InitQueue(&Q);printf(“%d”,v);/v为访问的起始结点visitedv=1;/访问过的标志EnQueue(&Q,v);while(!EmptyQueue(Q)/判队列是否为空v=Gethead(&Q);OutQueue(&Q);/出队列for(j=0;jarcsvj;if(m&!visitedj)/判断是否邻接点，且未被访问printf(“%d”,j);visitedj=1;/置被访问标志EnQueue(&Q,j);/邻接点入队列在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有

41、一定的梯度，由浅入深，所提出的问题也很明确1 1、判断图的连通性、判断图的连通性 对图对图G G调用一次调用一次DFSDFS或或BFSBFS，得到一顶点集，得到一顶点集合，然后将之与合，然后将之与V(G)V(G)比较，若两集合相等，比较，若两集合相等，则图则图G G是连通图，否则就说明有未访问过的是连通图，否则就说明有未访问过的顶点，因此图不连通。顶点，因此图不连通。5.3.3求图的连通分求图的连通分量量在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2、求图的连通分量、求图的连通分量 从无向图的从无向图的每个连通分量每个连通分量

42、的一个顶点出发遍的一个顶点出发遍历，则可求得无向图的所有连通分量。历，则可求得无向图的所有连通分量。图遍历的一种应用图遍历的一种应用算法：算法：void trace(Graph G)void trace(Graph G)/*G/*G为用邻接矩阵或邻接表表示的有为用邻接矩阵或邻接表表示的有n n个顶点的无向个顶点的无向图，求该图的连通分量图，求该图的连通分量*/*/int i;int i;for(i=0;iN;+i)for(i=0;iN;+i)if(!flagi)if(!flagi)dfs(i);dfs(i);/*/*调用调用DFSDFS算法的次数仅决定于连通分量个数算法的次数仅决定于连通分量个

43、数*/*/OUTPUT OUTPUT；/*/*输出访问到的顶点和依附于这输出访问到的顶点和依附于这*/*/*/*些顶点的边，就得到一个连通分量些顶点的边，就得到一个连通分量*/*/*trace*/*trace*/在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确一、生成树一、生成树1 1、生成树定义生成树定义：连通图：连通图G=(V,E)G=(V,E)，从任一顶点，从任一顶点 遍历，则图中边分成两部分：遍历，则图中边分成两部分：遍历通过的边遍历通过的边 剩下的边剩下的边(即遍历时未通过的边）即遍历时未通过的边）E(G)=T(G)+B(G

44、)E(G)=T(G)+B(G)则则G(VG(V，T)T)为为G G的子图，称之为的子图，称之为G G的一棵生成树。的一棵生成树。深度优先生成树：深度优先生成树：按深度优先遍历而得的生成树按深度优先遍历而得的生成树广度优先生成树：广度优先生成树：按广度优先遍历而得的生成树按广度优先遍历而得的生成树5.4 5.4 图的应用图的应用在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2、例：、例：其深度优先生成树为：其深度优先生成树为：其广度优先生成树为：其广度优先生成树为：图的生成树不是惟一的。图的生成树不是惟一的。在整堂课的教学中，刘教

45、师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确1 1、问题的提出：、问题的提出：通讯网：通讯网：网中网中n n个顶点个顶点nn个城市个城市两顶点间的边两顶点间的边两城市间线路两城市间线路边的权边的权架设相应线路的费用架设相应线路的费用问题问题1 1：n n个城市间的通讯网，个城市间的通讯网，至少至少要多少条线路？要多少条线路？（n-n-1 1）n n个城市间最少的可行的通讯线路就是个城市间最少的可行的通讯线路就是一棵生成树一棵生成树问题问题2 2：选择怎样的：选择怎样的n-1n-1条线路，使总费用最少条线路，使总费用最少？网上问题：取网上问题：取n-1n

46、-1条边，并使边权总和为最少。条边，并使边权总和为最少。最小生成树问题最小生成树问题二、最小生成树二、最小生成树在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2 2、最小生成树定义、最小生成树定义 给定一个带权图，构造带权图的一棵生给定一个带权图，构造带权图的一棵生成树，使树中所有边的权总和为最小。成树，使树中所有边的权总和为最小。3、最小生成树的构造算法、最小生成树的构造算法Prim算法和算法和kruskal算法算法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确基本思想

47、：基本思想：假设假设G=(V,E)G=(V,E)是一个无向带权图，生成的最小生成树为是一个无向带权图，生成的最小生成树为MinT=(V,T),MinT=(V,T),其中其中V V为顶点的集合，为顶点的集合，T T为边的集合。求为边的集合。求T T的步骤如下：的步骤如下：1.1.初始化初始化U=uU=u0 0，T=T=；其中；其中U U为一个新设置的顶点的集合，初始为一个新设置的顶点的集合，初始U U中只含有顶点中只含有顶点u u0 0，这里假设在构造最小生成树时，从顶点，这里假设在构造最小生成树时，从顶点u u0 0出发；出发；2.2.对所有对所有uUuU，vV-U(vV-U(其中其中u u，

48、v v表示顶点表示顶点)的边的边(u,v)(u,v)中，找一条权中，找一条权最小的边最小的边(u,v)(u,v)，将这条边加入到集合，将这条边加入到集合T T中，将顶点中，将顶点vv加入到加入到集合集合U U中；中；3.3.如果如果U=VU=V，则算法结束；否则重复，则算法结束；否则重复2 2、3 3步。步。最后得到最小生成树最后得到最小生成树MinT=,其中其中T为最小生成树为最小生成树的边的集合的边的集合三、最小生成树的构造方法（三、最小生成树的构造方法（Prim法）法）在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确初态初态 5

49、 5 0,1,2,3,4 0,1,2,3,4 1 1 5,30,1,2,4 2 2 5,3,20,1,4 3 3 5,3,2,01,4 4 4 5,3,2,0,14 5 5 5,3,2,0,1,4 （6 6个顶点，个顶点，5 5条边）条边）0132452513546656 步骤步骤 已选顶点集已选顶点集U U 剩余顶点集剩余顶点集V-UV-U 已选已选集集TETE35201431524例：对下图用例：对下图用Prim法构造最小生成树法构造最小生成树在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 最小生成树的构造方法（最小生成树的构造

50、方法（PrimPrim法）法）适合于求边稠密的带权图的最小生成树。适合于求边稠密的带权图的最小生成树。设设G=G=（V V，E E）是个无向带权图，）是个无向带权图，U U是最小生成树的顶是最小生成树的顶点集合，点集合，T T是最小生成树的边集合，则是最小生成树的边集合，则PrimPrim算法描述如算法描述如下：下：Prim(Graph G)Prim(Graph G)/*/*构造图构造图G G的最小生成树的最小生成树*/*/从从G G中任选一顶点中任选一顶点pV pV；U=p U=p；T=T=；while(UV while(UV）在在pUpU，qV-UqV-U中找一条权最小的边（中找一条权最小