数据结构严蔚敏7章.ppt

7.1 图的定义和术语,第7章 图和广义表,7.2 图的存储结构,7.3 图的遍历,7.4 连通图的最小生成树,7.5 单源最短路径,7.6 拓朴排序,7.7 关键路径,*7.8 广义表,图(graph)是由一个顶点(vertex)的有穷非空集V(G)和一个弧或边(arc)的集合E(G)组成。记作G=V,E. 图又分为有向图和无向图,图中的顶点即为数据元素。 对有向图 没有箭头的出发端称为弧尾(tail) 或始点(initial)。 带箭头的终止端称为弧头(head) 或终点(terminal node) 用有序对表示从v到w的一 条弧。(如图中 ） 对无向图,7.1 图的定义和术语,1 图的定义,(a) 有向图G1,7.1 图的定义和术语,1 图的定义,(b) 无向图G2,图(graph)是由一个顶点(vertex)的有穷非空集V(G)和一个弧或边(arc)的集合E(G)组成。记作G=V,E. 图又分为有向图和无向图,图中的顶点即为数据元素。 对有向图 没有箭头的出发端称为弧尾(tail) 或始点(initial)。 带箭头的终止端称为弧头(head) 或终点(terminal node) 用有序对表示从v到w的一 条弧。(如图中 ） 对无向图,用(v,w)表示一条边。,如(A,B)表示无向图G2中的一条边。,图的表示 G1=( V1, E1 ) V1=A,C,B,F,D,E,G E1=, , ,G2=( V2, E2 ) V2=A,B,C,D,E,F E2=(A,B),(A,C),(B,C),(B,E), (B,F),(C,F),(C,D),(E,F),(C,F),假设有两个图G=(V,E)和G=(V,E),如果 V V且E E,则称G是G的子图。,可以证明,对于具有n个顶点的无向图的边和具有n个顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。 称具有n(n-1)/2条边的无向图为完全图(completed grahp)。 称具有n(n-1)条弧的有向图为完全有向图 称边或弧的数目enlogn的图为稀疏图(sparse graph),反之则称为稠密图(dense graph)。 子图,2 几个常用术语,可以证明,对于具有n个顶点的无向图的边和具有n个顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。 称具有n(n-1)/2条边的无向图为完全图(completed grahp)。 称具有n(n-1)条弧的有向图为完全有向图 称边或弧的数目enlogn的图为稀疏图(sparse graph),反之则称为稠密图(dense graph)。 子图,2 几个常用术语,假设有两个图G=(V,E)和G=(V,E),如果 V V且E E,则称G是G的子图。,度、入度和出度 若uv是有向图中的一条弧,则称u邻接到v,或称v被邻接到u。 图中所邻接到顶点v的弧(即以它为弧头的弧)的数目,称为顶点v的入度(indegree),记作ID(v);反之,从某顶点u出发的弧(即邻接自该顶点的弧),称为该顶点的出度(outdegree),记作OD(u)。 有向图中顶点v的入度和出度之和 称为该顶点的总度,简称为度(degree) ,记作TD(v),如右所示的有向图 顶点C邻接到顶点E, vcvE,ID(vc)=,2,OD(vc)=,1,TD(vc)=,3,无向图中顶点的度定义为与该顶点 相连的边的数目。 如果顶点vi的度记为TD(vi),则一个含n个顶点,e条边或弧的图,满足如下关系,TD(vB)=,4,度、入度和出度 若uv是有向图中的一条弧,则称u邻接到v,或称v被邻接到u。 图中所邻接到顶点v的弧(即以它为弧头的弧)的数目,称为顶点v的入度(indegree),记作ID(v);反之,从某顶点u出发的弧(即邻接自该顶点的弧),称为该顶点的出度(outdegree),记作OD(u)。 有向图中顶点v的入度和出度之和 称为该顶点的总度,简称为度(degree) ,记作TD(v),路径和回路,若有向图G中k+1个顶点之间都有弧存在(即, 是图G中的弧),则这个顶点的序列(v0,v1,., vk)为从顶点v0到顶点vk的一条有向路径,路径中弧的数目定义为路径长度。 若序列中的顶点都不相同,则称为简单路径。,(v0, v1, v2 , v4,v1, v5 , v6 ) 是v0到v6的一条有向路径,(v0, v1, v5 , v6) 也是v0到v6的一条有向路径,简单路径,路径和回路,若有向图G中k+1个顶点之间都有弧存在(即, 是图G中的弧),则这个顶点的序列(v0,v1,., vk)为从顶点v0到顶点vk的一条有向路径,路径中弧的数目定义为路径长度。 若序列中的顶点都不相同,则称为简单路径。 对于无向图,相邻顶点之间存在边的k+1个顶点序列 构成一条长度为k的无向路径。,(v0, v1, v2 , v4, v5, v2 , v3 ) 是v0到v3的一条无向路径,(v0, v1, v2 , v3) 也是v0到v3的一条有向路径,如果v0和vk是同一个顶点, 则是一条由某个顶点出发又回到该顶点的路径,称这种路 径为回路或环(cycle).,简单路径,(v0, v1, v5 , v2, v0) 是一条回路或环路,连通图和连通分量,若无向图中任意两个顶点之间都 存在一条无向路径,则称该无向图为连通图。 若有向图中任意两个顶点之间都存在一条有向路径,则称该有向图为强连通图。 非(强)连通图中各个(强)连通子图称为该图的(强)连通分量.,连通图,非连通图,强连通图,非强连通图,2个连通分量,4个强连通分量,带权图和网,边(弧)上带有权值的图称为网。 带权有向图和带权无向图分别称为有向网和无向网。,1,0,2,3,4,3,8,6,5,9,有向网,图的基本操作,CreateGraph(&G,V,VR) . BFSTraverse(G,v,visit(),7.2 图的存储结构,1.图的数组(邻接矩阵)存储表示 2.图的邻接表存储表示,7.2 图的存储结构,7.2.1 图的数组(邻接矩阵)存储表示,无权图的邻接矩阵的定义,设G=(V,E)是具有n(n0)个顶点的图,顶点的顺序依次为(v0,v1,vn-1),则G的邻接矩阵A是n阶方阵,A00 A01 A0n-1 A10 A11 A1n-1 An-10 An-11 An-1n-1,A=,Aij=,1,若vi和vj之间有弧或边存在,0,反之,7.2 图的存储结构,7.2.1 图的数组(邻接矩阵)存储表示,网的邻接矩阵的定义,设G=(V,E)是具有n(n0)个顶点的带权图,顶点的顺序依次为(v0,v1,vn-1), wij则是顶点i和j的弧 (边)上的权值,则G的邻接矩阵A是n阶方阵,A00 A01 A0n-1 A10 A11 A1n-1 An-10 An-11 An-1n-1,A=,Aij=,wij,若vi和vj之间有弧或边存在,反之,G1,(1)有向图的邻接矩阵,a. 有向图的邻接矩阵一般是个稀疏矩阵,b.第i行非零元素的个数是顶点vi的,的出度。,c.第j列非零元素的个数是顶点vj的,的入度。,有向图邻接矩阵的几个特点,(2)无向图的邻接矩阵,a.无向图的邻接矩阵是个对称矩阵; b.第i行非零元素的个数是顶点vi的度。,G2,无向图邻接矩阵的几个特点,(3) 有向网的邻接矩阵,1,0,2,3,4,3,8,6,5,9,有向网,一个图的邻接矩阵是唯一的,邻接矩阵的类型定义 const INT_MAX=32767; const MAX_V=20; typedef int VRType; typedef int InforType; typedef int VertexType; typedef enum DG, DN, AG, AN GraphKind; typedef struct VRType adj; InforType *info; ArcCell,AdjMatrixMAX_VMAX_V; typedef struct VertexType vexMAX_V; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; MGraph;,/设置“无穷大”值,/最大顶点数目,/图的种类,/邻接矩阵类型,/顶点关系类型,/指向边或弧信息(如权值)的指针,/顶点信息数组(如顶点编号等),/图的邻接矩阵,/图的顶点数和边(弧)的数目,/图的种类标志,7.2.2 图的邻接表存储表示,邻接表是一种链式存储表示方法，它类似于树的孩子链表。 在邻接表中,对图中每个顶点建立一个单链表, 第i个顶点的单链表的所有结点,表示依附于顶点vi的边(或以vi为尾的弧)。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：,(1)表结点的三个域 adjvex 是个整形变量,指示与顶点vi邻接的顶点在表头数组中的存储位置(下标); nextarc 是指针型变量,指向下一条边或弧的结点; Info存储与边或弧相关的信息,如权值等; (2)表头结点的两个域 data 存储顶点vi的名称或编号等信息; firstarc指向链表中第一个结点。,表结点,表头结点,表结点,表头结点,typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;,typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V;,typedef struct /图的邻接表类型 AdjList vertices; /存储图中所有顶点的数组 int vexnum,arcnum; /存储图的顶点数目和边(弧)的数目 int kind; /图的种类标志 ALGraph;,typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;,typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V;,typedef struct AdjList vertices; int vexnum,arcnum; int kind; ALGraph;,ALGraph G;,0,1,MAX_V-1,.,.,.,G.vertices,G.vexnum,G.arcnum,G.kind,data,firstarc,有向图的邻接表存储示意图,1,2,4,5,有向图G1的邻接表,注意：图的邻接表不是唯一的，因为与一个顶点相邻的边的顺序没有明确规定。 在此规定：边的顺序号按相关顶点的顺序号由小到大排定。,有向图G的逆邻接表,表结点指针域链接的不是出边而是入边.,有向网G3,有向网的邻接表,1,2,0,3,4,有向网G3的邻接表,算法7.1 建立无向图的邻接表存储结构,void CreateUDG(ALGraph ,/输入边的起、止顶点名称值,/确定v1,v2下标,/输入顶点名称值,/用头插法插入v1的相邻结点,/用头插法插入v2的相邻结点,typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode, *ArcNodeP;,typedef struct VertexType data; ArcNode *firstarc; VNode,AdjListMAX_V;,typedef struct AdjList vertices; int vexnum,arcnum; int kind; ALGraph;,/算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph /for / CreateUDG,/算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph . . . ,/算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph . . . ,/算法 7.1的改进算法(用尾插法建立无向图的邻接表) void CreateUDG(ALGraph /for / CreateUDG,/补充算法 7.1-1 确定顶点名称值为v的存储下标 int LocateVex(ALGraph G, VertexType v) int i; for(i=0;i=G.vexnum) ErrorMessage(“顶点名称值有错！“); return i; ,/补充算法 7.1-2 输出图的邻接表 void DisplayGraph(ALGraph G) int i;ArcNode *p; cout“adjvex; p=p-nextarc; coutendl; ,/主函数调用实例 . ALGraph G; CreateUDG(G); DisplayGraph(G);,无向图G3,以右上图为例 图中9个顶点名称值的输入顺序为 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 图中11条边的输入顺序为 1-2 , 1-3 , 1-4 , 2-3 , 2-4 , 3-6 , 4-9 , 5-6 , 5-7 , 5-8 ,7-9,/运行结果(省略了输入提示信息) 当前图的邻接表为： 0:1-1-2-3 1:2-0-2-3 2:3-0-1-5 3:4-0-1-8 4:5-5-6-7 5:6-2-4 6:7-4-7 7:8-4-6 8:9-3 Press any key to continue,无向图G3,1,2,3,4,5,6,7,8,9,7.3 图的遍历(Graph Traversal),从给定图中某个指定的顶点(称为初始点)出发, 沿着图的某条路径对图中其余顶点进行访问,且使每个顶点仅被访问一次,这一过程称为图的遍历(graph traversal)。,图的遍历方法有两种： (1)深度优先搜索(Depth First Search-DFS) (2)广度优先搜索(Breadth First Search-BFS)。,7.3.2 深度优先搜索遍历图,图的深度优先搜索(depth first search)类似于树的先根遍历的推广，搜索过程是： (1)从图中某个初始顶点v出发,首先访问该顶点v; (2)依次从它的各个未被访问的邻接顶点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到; (3)若尚有其它顶点未被访问,则另选一个未被访问的邻接点作起始顶点; (4)重复上述过程,直到图中所有顶点都被访问到为止。 显然, 遍历过程是个递归过程。,BFS,/算法 7.4 从邻接表头下标为v的顶点从发, 递归地深度 /优先遍历图G。 void DFS(ALGraph G, int v) int w; ArcNode *p; visitedv=true; coutnextarc) w=p-adjvex; if (!visitedw) DFS(G,w);/对v的未访问的邻接顶点w进行DFS /DFS,/主函数调用实例 int i; ALGraph G; CreateUDG(G); visited=new boolG.vexnum; for(i=0;iG.vexnum;i+) visitedi=false; DisplayGraph(G); cout“深度优先搜索的顶点序列为“endl; DFS(G, LocateVex(G, 3);,/建立图的邻接表,/建立搜索访问标志数组,/false表示该顶点尚未被访问,/显示图的邻接矩阵,/对课本P209的图7.6(a),/以v3顶点为起点,进行深度优先搜索,运行结果如下,/初始化访问标志数组,输入顶点数目和边的数目:9 11 输入第1个顶点的值:1 . 输入第9个顶点的值:9 请输入第1条边的起止顶点值:1 2 . 请输入第11条边的起止顶点值:7 8 当前图的邻接表为： 0:1-1-2-3 1:2-0-2-3 2:3-0-1-5 3:4-0-1-8 4:5-5-6-7 5:6-2-4 6:7-4-7 7:8-4-6 8:9-3 深度优先搜索的顶点序列为 3 , 1 , 2 , 4 , 9 , 6 , 5 , 7 , 8 , Press any key to continue,注意 课本P209正数第四行给出的DFS结果有误！,无向图G3,无向图的深度优先搜索手工操作过程举例1,v3,v1,v2,v4,v9,v6,v5,v7,v8,注：课本P209正数第4行给出的DFS遍历序列不正确。,无向图的深度优先搜索手工操作过程举例2,A,无向图G2,B,C,D,E,F,程序验证 6个顶点的输入次序为: A , B , C , D , E , F 9条边的输入次序为: A-B, A-C, B-C, B-E, B-F, C-D, C-E, C-F , E-F 算法运行结果如下,输入顶点数目和边的数目:6 9 输入第1个顶点的值:A . 输入第6个顶点的值:F 请输入第1条边的起止顶点值:A B . 请输入第9条边的起止顶点值:E F 当前图的邻接表为： 0:A-1-2 1:B-0-2-4-5 2:C-0-1-3-4-5 3:D-2 4:E-1-2-5 5:F-1-2-4 深度优先搜索的顶点序列为 A , B , C , D , E , F , Press any key to continue,无向图G2,有向图的深度优先搜索过程,v0,v1,v2,v4,v3,得到的遍历序列:,结束,以v0为初始顶点,有向图,1,0,2,3,4,7.3.2 广度优先搜索(BFS)遍历图,广度优先搜索(breadth first search )的基本思想是： 从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。 若此时图中尚有顶点未被访问,则需另选一个未曾被访问的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。 为存储已被访问过的顶点,需附设一个队列。 BFS过程类似于树的按层次遍历,v1,if ( !visitedv) visitedv=TRUE;VisitFunc(G.vexsv); EnQueue_Sq(Q, v); while (!QueueEmpty_Sq(Q) DeQueue_Sq(Q, u); for ( w=0; wG.vexnum; w+; ) if ( G.arcsu, w.adj /if /while /if,v3,v3,u=,v3,w=,0,v1,1,v2,v2,2,3,4,5,v6,v6,v1,v4,v4,v5,v5,v9,v9,v7,v7,v8,v8,队列为空，遍历结束,v1,v3,v3,v1,v2,v2,v6,v6,v4,v4,v5,v5,v9,v9,v7,v7,v8,v8,队列为空，遍历结束,1,2,3,0,4,无向图,无向图的广度优先搜索遍历过程,2,1,3,0,4,得到的遍历序列:,以为v2初始顶点,1,3,4,0,队列,队列为空，遍历结束,有向图的广度优先搜索遍历过程,0,1,3,4,2,得到的遍历序列:,以v0为初始顶点,1,3,2,4,队列,有向图,1,0,2,3,4,队列为空，遍历结束,7.4 连通网的最小生成树,1.生成树(Spanning Tree) 在一个含有n个顶点的连通图中,必能选出n-1条边构成一个极小连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边,称这颗树为连通图的生成树。 极小连通子图:若删除极小连通子图的任意一条边,该图就成为非连通图,若在极小连通子图中增加一条边,必定构成一个环。 对一个连通图进行一次深度优先搜索或广度优先搜索得到的顶点集合及相关边的集合就构成图G的一个生成树(DFS生成树或BFS生成树) 一个连通图的生成树不是唯一的。,(a)连通网,(b)权值总和为43的生成树,(c)权值总和为36的生成树,(d)权值总和为64的生成树,一个连通网的所有生成树中,具有权值总和最小的生成树称为连通网的最小生成树,如何构造一个带权无向连通图的最小生成树？ 1.克鲁斯卡尔(Kruskal)算法 2.普里姆(Prim)算法。,问题,1.克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法的基本思想为：,为使生成树上的总权值之和达最小,应使每一条边的上的仅值尽可能小,自然应从权值最小的边选起,直至选出n-1条权值最小的边为止。 然而这n-1条边必须不构成回路。因此并非每一条居当前权值最小的边都可选。,首先构造只含n个 顶点的森林,然后依权值从小到大从连通网中选择边加入 到森林中去,并使森林中不产生回路,直至森林变成一颗树 为止。,12,8,7,4,2,10,12,16,7,6,5,3,4,2,8,9,14,1.克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法的具体做法如下：,3,克鲁斯卡尔算法构造的最小生成树,5,4,3,2,1,首先构造只含n个 顶点的森林,然后依权值从小到大从连通网中选择边加入 到森林中去,并使森林中不产生回路,直至森林变成一颗树 为止。,1.克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法的具体做法如下：,首先选取图中任意一个顶 点v作为生成树的根,之后继续往生成树中添加顶点w,则在 顶点w和v之间必须有边,且该边上的权值应在所有和v相邻 接的边中属最小.,2.普里姆(Prim)算法 普里姆算法的基本思想为：,2.普里姆(Prim)算法 普里姆算法的具体做法如下：,从具有n个顶点的连通网G=(V,E)中找出最小生成树T=(U,TE)的步骤如下：,1. 选G中任一顶点v为起点, 初始化U=v, 将v与V-U中所有相邻顶点构成的边加入候选边集E,重复以下步骤,直到全部n个顶点都加入到U中为止。 将E中最小权值的边加入TE,并将该边在V-U中的顶点vk加入U中,同时将vk从V-U中删除。 考查vk与V-U中所有相邻顶点构成的边,若边(vk ,vj)的权小于E中边(vu ,vj)的权,则用(vk ,vj)取而代之;若E不存在与vj关联的边,则将(vk ,vj)加入E中 。,2,g,U=,V=,V-U=,E,(候选边直接在原图中标出),a,b,c,d,e,f,g,a,b,c,d,e,f,g,(a, b):12,b,V-U=,(b, f ):7,f,g,(f, e ):2,e,g,d,g,c,(e, d ):4,(d, c ):3,g,(e, g ):8,TE,12,7,3,4,8,n个结点已全部加入生成树中,结束！,普里姆算法构造最小生成树的过程,1,5,2,4,3,以v5为起点，采用Prim算法，写出构造连通网G的最小生成树的过程。,0,图G,2,2,4,1,2,4,0,1,5,2,4,0,7.5 单源最短路径,单源最短路径的背景是,从某个城市出发,能否到达其 他各城市？走哪条路线花费最少？ 单源路径的抽象提法为：从有向网中的源点到其余各终点有否路径？其最短路径及其长度是什么？ 从源点到终点的路径可能存在三种情况：一种是没有路径;另一种是只有一条路径;第三种情况是存在多条路径。,图7.15 有向网及其邻接矩阵,7.5 单源最短路径,单源最短路径的背景是,从某个城市出发,能否到达其 他各城市？走哪条路线花费最少？ 单源路径的抽象提法为：从有向网中的源点到其余各终点有否路径？其最短路径及其长度是什么？ 从源点到终点的路径可能存在三种情况：一种是没有路径;另一种是只有一条路径;第三种情况是存在多条路径。,b 到 f 无路径,b 到 a 只有一条路径,b 到 d 有三条路径,(b , a , g , c , e , d):64,(b , c , e , d):27,(b , d):30,7.5 单源最短路径,单源最短路径的背景是,从某个城市出发,能否到达其 他各城市？走哪条路线花费最少？ 单源路径的抽象提法为：从有向网中的源点到其余各终点有否路径？其最短路径及其长度是什么？ 从源点到终点的路径可能存在三种情况：一种是没有路径;另一种是只有一条路径;第三种情况是存在多条路径。,0,1,2,3,4,5,6,AS77,图7.15 有向网及其邻接矩阵,问题 如何求出有向网G=V,E中某一顶点(称为源点)到G中其余任一顶点的带权最短路径? 单源最短路径问题 迪杰斯特拉(Dijkstra)算法,则u为目前找到的从源点出发的最短路径的终点,将u加入S。 (3)搜索u与网中所有顶点w,构成的弧,若,迪杰斯特拉(Dijkstra)算法,(1)设ASnn为有向网G=V,E的邻接矩阵, vi为源 点, S为最短路径终点集,初态S=vi ,一维组Distn的每个 分量记录当前找到的从vi出发,途经S中顶点到各终点的候选路径长度,其初始值为 Distn=ASi,n (7-4) (2)选择满足下式的顶点u,Distu=min Distw |,(7-5),Distu+ASu,wDistw,则令 Distw=Distu+ASu,w (7-6),(4)重复步骤(2)和(3),直到与vi有路径的顶点都加入S为止,即可求得G中源点vi到其余顶点的最短距离,另设Pathnn记录最短路径,path77,dist7,0,1