理论教学第8教案

1、图是比线性表、数和集合更一般、更复杂的数据结构， 性结构中，每个数据元素只有一个直接前驱和一个直接后继结点。在树结构中，数据元 间有着明显的层次关系，同层的元 间的关系是任意的，每个元素都可以和任何其他元素相关。图这一章阐述了图的基本概念以及图的 结构：相邻矩阵表示法、邻接表表示法，并讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念，并 了生成最小支图是比线性表、数和集合更一般、更复杂的数据结构， 性结构中，每个数据元素只有一个直接前驱和一个直接后继结点。在树结构中，数据元 间有着明显的层次关系，同层的元 间的关系是任意的，每个元素都可以和任何其他元素相关。图这一章阐述了图的基

2、本概念以及图的 结构：相邻矩阵表示法、邻接表表示法，并讨论了图的深度优先周游和广度优先周游。此外提出了最小支撑树的概念，并 了生成最小支各知识点建议授 间如下：0.5学时图的 结构 1.5学时图的周游 1.5学时最小生成树 1学时贪心算法 0.5学时 STL map 0.5学时邻接表(adjacency list)表示法是一种链式链表（Orthogonal List）是有向图的另一种链式结构中。 图的深度优先周游方法的特点是尽可能先对纵深方向进行搜索。对于给定的图G=，与它们邻接的所有未曾 过的顶点。重复上述过程直至图中所有与源点v有路径相通的顶点都被 为止。若G是连通图，则周游完成；否则，在

3、图G中选一个尚未 的顶点作为新源点继 (2) 知。其余的顶点放在另一个集合V-S中。初始时，集合S只包含源点，即S=s，这时只有源点DuWu,vi）。然后重复上述操作，一旦S包含了所有V中的顶点，D中各顶点的距离值就特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为O(ne)loge)，适合于稀疏图。特殊路径长度时需要对堆进行一次重排，此时的时间复杂度为O(ne)loge)，适合于稀疏图。 O( n2 )的时间，这种方法适合于稠密图。（7）KruskalKruskal算法的构造 是：给定含有n个顶点和e条边的无向连通带权图 的森林，可以记为TV，。然后在E中选择代价最小的边，如果该边依附于

4、两个不同的连通分 么将这条边加入到T中，否则舍去这条边而选择下一条代价最小的边。依此类推，直到T中所有顶点都在同 通分量中为止，此时就得到图G的一棵最小生成树。 在Kruskal算的连通分支，采用UnionKruskal算法中，需要按边权值递增的顺序作业，1-2道综合上机实习题。安排一次习题讲评。 例如：算法方面 的者是无向图）G = 以及一对顶点vi、vjV，输出的结果是：如果从vi到vj存在一条简单路设G = 是一个如果U = V，则算法结束；否则重复步骤2TE中包含了G中的n-1条边。经过上述步骤选取到的所有边恰好就 了图G的一棵最小生成树。void Prim(Graph& G,s,Ed

5、ge*&MST)/s是开始顶点，数组MST用于保存最小生成树的边 MSTtag = 0;/ 最小生成树的边计数MSTnew/ 为数组MST申请空DistDnewDistG. / 为数组Dfori0iNumi/ 初始化Mark数组、D数G.Marki= Di.index =Di.pre = s; Ds.length=G.MarksVISITED; / Ds.length=G.MarksVISITED; / 开始顶点标记为VISITED v = s;for(i =0; i ifDvINFINITY/ 非连通，有不可达顶/ 因为v的加入，需要刷新与v相邻接的顶点的Dfor Edge e = G. D

6、G.ToVertex(e).length=e.weight; DG.ToVertex(e).pre = v; vminVertex(G, D); / 在D数组中找最小值记为vG.Markv/ 标过 edge(Dv.preDv.indexDv.length保存AddEdgetoMST(edge,MST,MSTtag将边edge加到MSTminVertex(Graph&GDist*&D在Dist数组中找最小i, v; for (i = 0; i G.Vertiif (G.Marki = UNVISITED) v=i; / 让v为随意一个for(i =0;i Num();if(G.Marki=UNVISITED) &(Divi; / 保存当前发现的具有最小距离的顶returnO(e)，因此共需要花费O( n2 )的时间，此算法适合于稠密图。在本章介绍的内容中，图的 结构和图的相关算法是本章的重点。要求掌握图的基本概念、图的 结构，并可以写出基于图的 结构的各种算法，掌握计算最短路径算法和计算MarkAllenWeissDataStr