《【经管类】图的定义和术语(4)》由会员分享，可在线阅读，更多相关《【经管类】图的定义和术语(4)（57页珍藏版）》请在金锄头文库上搜索。
1、第七章 图,7.1 图的定义和术语 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索 7.4 图的连通性问题 7.4.3 最小生成树 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径,7.1 图的定义和术语,图的定义：是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, R ) 其中 V = v
2、| v 某个数据对象 是顶点的有穷非空集合； R =VR=(v, w) | v, w V ,基本术语： 1.有向图与无向图 在有向图中，顶点对是有序的。在无向图中，顶点对(x, y)是无序的。有向边又可称为弧, 中vi称为弧尾或初始点，vj称为弧头或终端点。,有向图,V=1,2,3,4,5,6,7 VR=, , ,无向图,V=1,2,3,4,5,6,7 VR=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5),(1,7),2.邻接点及关联 若无向图中存在边(v, u)，则称顶点v和u互为邻接点；边(v, u)依附于顶点v和u；或者说边(v
3、, u)和顶点v和u相关联。 3.顶点的度、入度、出度 在无向图中： 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度=以V为狐尾的有向边数 顶点V的入度=以V为狐头的有向边数 顶点V的度= V的出度+V的入度,4.路径、回路,无向图G =（V，E）中的顶点序列v1,v2, ,vk, 若(vi,vi+1)E( i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。,在图G1中，V0,V1,V2,V3 是V0到V3的路径。 V0,V1,V2,V3,V0是回路。,例：,例：有向图G2,在图G2中，V0,V2,V3 是V
4、0到V3的路径。V0,V2,V3,V0是回路。,有向图G =（V，E）中的顶点序列v1,v2, ,vk, 若E (i=1,2,k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。,在一条路径中,若除起点和终点外,所有顶点各不相同, 则称该路径为简单路径。 由简单路径组成的回路称为简单回路。 在图G1中，V0,V1,V2,V3 是简单路径。 V0,V1,V2,V4,V1不是简单路径。 在图G2中，V0,V2,V3,V0是简单回路。,无向图G1,有向图G2,5.简单路径和简单回路,非连通图,连通图,强连通图,非强连通图,6.连通图（强连通图）,
5、在无（有）向图G=( V, E )中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）。,(a),(b),(c),8.子图,设有两个图G=（V，E）、G1=（V1，E1），若V1 V，E1 E，则称 G1是G的子图。 例:(b)、(c) 是 (a) 的子图,7.权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。,9.连通分量（强连通分量）,无向图G 的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。,非连通图,有向图G 的极大强连通子图称为G的强连通分量。极大强连通子图意
6、思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。,10.权与网,图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。,极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通 包含无向图G 所有顶点的极小连通子图称为G 的生成树 对非连通图，则称由各个连通分量的生成树的集合为非连通图的生成森林。,连通图 G1,G1的生成树,11.生成树和生成森林,7.2.1 数组表示法,邻接矩阵：表示顶点间相联关系的矩阵。 定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵：,网的邻接矩阵
7、可定义为：,邻接矩阵类型定义:,#define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enumDG,DN,AG,AN GraphKind; typedef struct ArcCell VRType adj; InfoType * info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; MGr
8、aph;,邻接表的类型定义 #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;,7.2.2 邻接表,实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。,typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM ; typedef struct AdjList
9、vertices; int vexnum,arcnum; int kind; ALGraph;,逆邻接表：有向图中对每个结点建立以Vi为弧头的弧的单链表。,7.3 图的遍历,7.3.1 深度优先搜索,方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点,重复上述过程，直至图中所有顶点都被访问为止。,深度遍历：V1 V2 V4 V8 V5 V3 V6 V7,深度优先遍历算法（递归算法）参见P169。,深度优先遍历算法（递归算法） Boolean vis
10、itedMAX; Status (*VisitFunc)(int v); void DFSTraverse(Gragh G, Status (*Visit)(int v) VisitFunc=Visit; for(v=0;v=0;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,W); ,7.3.2 广度优先搜索,方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图
11、中所有顶点都被访问为止。,广度优先遍历算法 void BFSTraverse(Graph G, Status(* Visit)(int v) for(v=0;v=0;w=NextAdjVex(G,u,w) Visitedw=TRUE;visit(w); EnQueue(Q,w); ,广度遍历：V1 V2 V3 V4 V5 V6 V7 V8,例:,广度遍历序列：1 4 3 2 5,7.4 图的连通性问题,问题提出：要在n个城市间建立通信联络网，用顶点表示城市；权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小(代价)生成树。
12、,7.4.3 最小生成树,算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合。 1.初始令U=u0,(u0V), TE=。 2.在所有uU,vV-U的边(u,v)E中，找一条代价最 小的边(u0,v0)。 3.将(u0,v0)并入集合TE，同时v0并入U。 4.重复上述操作直至U=V为止，则T=(V,TE)为N的最 小生成树。,方法一：普里姆(Prim)算法,构造最小生成树的方法,1,算法实现：图用邻接矩阵表示。,方法二：克鲁斯卡尔(Kruskal)算法,算法思想： 1.设连通网N=(V,E)，令最小生成树初始状态为只有 n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连
13、通分量。 2.在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边。 3.依此类推，直至T中所有顶点都在同一连通分量上为止。,7.5 有向无环图及其应用,7.5.1 拓扑排序,问题提出：假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。如何检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,什么是拓扑排序：把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫拓扑排序。,拓扑排序的方法: 1.在有向图中选一个没有前驱的顶点且输出之。 2.从图中删除该顶点和所有以它为尾的弧。
14、 3.重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。,拓扑序列： C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 一个AOV网的拓扑序列不是唯一的。,拓扑序列：C1,- C2,-C3,-C8,-C4,-C5,-C7,-C9,-C10,-C11,-C6,-C12,算法实现： 1.以邻接表作存储结构。 2.把邻接表中所有入度为0的顶点进栈。 3.栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。 4.重复
15、上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,1,6,输出序列：6,1,4,3,3,2,2,4,5,5,0,1,2,2,入度,指针,5,5,3,0,1,2,3,4,5,6,问题提出：把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。,7.5.2 关键路径,定义： AOE网(Activity On Edge)：也叫边表示活动的网。AOE 网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。 路径长度：路径上各活动持续时间之和。 关键路径：路径长度最长的路径。 ve(j)：表示事件Vj的最早发生时间。 vl(j)：表示事件Vj的最迟发生时间。 e(i)：表示活动ai的最早开始时间。 l(i)：表示活动ai的最迟开始时间。 l(i)-e(i)：表示完成活动ai的时间余量。 关键活动：关键路径上的活动，即l(i)=e(i)的活动。,设活动ai用弧表示，其持续时间记为：dut() 则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)从Ve(1)=0开始向前递推,(2)从Vl(n)=Ve(n)开始向后递推,问题分析 如何找e(i)=l(i)的关键活动？,
