数据结构第 7章 图2课件

《数据结构第 7章 图2课件》由会员分享，可在线阅读，更多相关《数据结构第 7章 图2课件（89页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构,主讲：张荣梅,二零零五年五月,第7章 图,第六章 图,知 识 点 图的逻辑结构特征及图的基本术语 邻接矩阵和邻接表两种图的存储结构的特点及适用范围 深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程 生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法 最短路径的含义及求最短路径的算法 拓扑排序的基本思想和步骤 关键路径法及其在管理科学中的作用,难 点 图的遍历、最小生成树、最短路径、拓朴排序算法的理解 关键路径法求关键活动和关键路径的方法 要 求 熟练掌握以下内容： 图的存储结构 图的遍历算法 了解以下内容： 图的最小生成树和求最小生成树算法的基本思想

2、带权有向图的最短路径问题 利用AOV网络的拓朴排序问题 利用AOE网络的关键路径法,第七章目录,7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.7 关键路径法 小 结 习题与练习,7.1 图的定义和术语,图是一种比树更为复杂的数据结构。在图中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。 一、图的抽象数据类型定义：P156 ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：RVR,VR| v,wV且P(v,w)，表示从v到w的 弧，谓词P(v,

3、w)定义了弧的意义或信息 ,7.1 图的定义和术语 二、名词和术语,顶点vertex 弧 Arc与有向图 边与无向图 完全图与有向完全图 稀疏图与 稠密图 权与网 子图,8. 邻接点、 度、 入度、 出度 9. 路径、回路、环、简单路径、简单回路、简单环 10. 连通图、 连通分量 11. 强连通图、 强连通分量 12. 生成树、最小生成树 13. 生成森林,有向图与无向图,无向图G2,有向图G1,返回,完全图与有向完全图,n(n-1)/2条边,n(n-1)条弧,返回,子图,返回,非连通图G,返回,图G1的强连通分量,返回,图G1,7.2 图的存储结构,7.2.1 数组表示法 7.2.2 邻接

4、表-链式 7.2.3 十字链表-有向图 7.2.4 邻接多重表-无向图,7.2.1 数组表示法邻接矩阵,用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。,/图的数组（邻接矩阵）存储表示 #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enumDG, DN, AG, AN GraphKind; /有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。 / 对无权图，用1或0表示相邻否； /

5、 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph;,邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。 邻接矩阵是一个（nn）阶方阵，n为图的顶点数，它的

6、每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为：,无向图的邻接矩阵是对称的，如果Ai，j=1，必有Aj，i=1。这说明，只输入和存储其上三角阵元素即可得到整个邻接矩阵。 一般有向图的邻接矩阵是不对称的，Ai，j不一定等于Aj，i。 根据邻接矩阵很容易判定任意两个顶点之间是否有边（弧）相连，并很容易求得各个顶点的度。 对于无向图，顶点Vi的度是邻接矩阵中第i行 （或第i列）的元素之和。 对于有向图，第i行的元素之和为顶点Vi的出度，第j列元素之和为顶点Vj的入度 网及其邻接矩阵。P162图7.9,结论,算法分析,算法7.1 构造邻接矩阵表示的图 p162 算法

7、7.2 构造邻接矩阵表示的网 p162,返回,构造邻接矩阵无向图算法,void CreateUDG(MGraph ,for( k=1;kv1v2; i=v1-1; j=v2-1; G.arcsij.adj=1; G.arcsji.adj=G.arcsij.adj; ,仿照此程序，编写构造无向网的算法,7.2.2 邻接表链式,邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。 每个结点由三个域组成，邻接点域adjvex指示与顶点Vi邻接的点在图中的 位置，链域nextarc指示下一条边或弧的结点；数

8、据域info存储和边或弧相关的 信息，如权值等。 每个链表上附设一个表头结点。链域指向链表中的第一个结点，数据域data存储顶点Vi的名。表头结点通常以顺序结构的形式存储。,/图的邻接表存储表示 #define MAX_VERTEX_NUM 20 typedef struct ArcNode /弧结点类型定义 int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typedef struct VNode /表结点类型定义 VertexType dat

9、a; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM;,typedef struct /图类型定义 AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph; P164图7.10,构造邻接表图的算法,void CreateALGraph(ALGraph *G) /创建图 ArcNode *s; int i,j,k; coutG-vexnumG-arcnum; coutvexnumvexnum ;i+) ci

10、nG-verticesi.data; G-verticesi.firstarc =NULL; ,请对比课本中的算法，有哪些不同？,coutarcnum arcnum ;k+) coutij; /从1开始 s=(ArcNode *)new ArcNode; s-adjvex =j-1; s-nextarc =G-vertices i-1.firstarc ; G-verticesi-1.firstarc =s; s=(ArcNode *)new ArcNode; /对无向图 ，生成2个边结点 s-adjvex =i-1; s-nextarc =G-vertices j-1.firstarc ;

11、G-verticesj-1.firstarc =s; ,返回,7.2.3 有向图的十字链表（自学）,P164-165图7.11 。哪些结点表示边？哪些结点表示弧？为什么从顶点firstout连接起来的单链表（水平方向）结点的tailvex都相同且都和该顶点的序号相同？为什么从顶点firstin连接起来的单链表（非水平）结点的headvex都相同且都和该顶点的序号相同？,tailvex,headvex,hlink,tlink,info,弧结点,data,firstin,firstout,顶点结点,/有向图的十字链表存储表示 #define MAX_VERTEX_NUM 20 typedef st

12、ruct ArcBox int tailvex, headvex; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量 int vexnum, arc

13、num; / 有向图的当前顶点数和弧数 OLGraph;,返回,7.2.4 无向图的邻接多重表（自学）,边结点,mark,ivex,ilink,jvex,jlink,info,mark：标志域，标记该边是否被搜索过。 ivex和jvex为该边依附的两个顶点。 ilink和jlink分别指示依附于顶点ivex和jvex的边。,顶点结点,data,firstedge,V1,V2,V3,V4,V5,P167图7.12,P167类型说明,返回,7.3 图的遍历,7.3.1 深度优先搜索（类似于树的先根遍历） 从图中某个顶点V0 出发，访问此顶点，然后依次从V0的未被访问的邻接点出发深度优先搜索遍历图，

14、直至图中所有和V0有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。, 首先访问图中某指定起始点Vi ，然后由Vi出发访问它的任一相邻接顶点Vj，再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk，再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。 如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问； 如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向后回退一步进行

15、搜索，重复上述过程，一直到所有顶点均被访问过为止。,深度优先搜索,示例，见图所示,深度优先搜索的顶点序列？,V1,V3,V4,V2 或,V1,V2,V3,V4,1,2,4,8,5,3,6,7,或1,2,5,8,4,3,7,6,？图的遍历和线性表、树的遍历有什么不同？,深度优先搜索的顶点序列？,图的深度优先遍历示例-非连通图,A,C,F,E,D,G,H,I,K,J,L,M,B,A, L,M,J,B,F,C D,E G,K,H,I,图的深度优先遍历算法,/- 下列算法使用的全局变量 - Boolean visitedMAX; / 访问标志数组 Status (* VisitFunc)(int v); / 函数变量 void DFSTraverse(Graph G, Status (* Visit)(int v) / 对图G作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初