第七章图 图的定义 图的存储结构 图的遍历 图的连通性问题 有向无环图 最短路径 关键路径 7.1基本概念 图 结 Graph=(V,R) V=xxEdataobject RRJ VR=x, y>P(x, y)AND(,yEV)) V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 顶点:图中的数据元素; 弧、弧头、弧尾:(v1,2),v-弧尾v—弧头
1 第七章 图 • 图的定义 • 图的存储结构 • 图的遍历 • 图的连通性问题 • 有向无环图 • 最短路径 • 关键路径 数 据 结 构 之 图 2 7.1 基本概念 ¾ 图 Graph=(V,R) Graph=(V,R) V={x|x∈dataobject dataobject} R={VR} VR={|P(x,y) AND (x,y VR={|P(x,y) AND (x,y∈V) } V是顶点的有穷非空集合; VR是两个顶点之间的关系的集合。 顶点：图中的数据元素； 弧、弧头、弧尾：(v1,v2) , v1—弧尾 v2—弧头
有向图:在图G中,边是顶点的有序对,每 条边都用箭头指明了方向,若是有向 数据结构 图中的一条边,则称V是尾或初始顶点;V是 头或终端顶点,且用从尾到头的箭头表示, v,v1>和不同。 >无向图:边是顶点的无序对,和 表示同一条边。 无向图 有向图 >无向完全G图:如果在无向图中,任何两个顶点都有 条边相连接,则称此图为无向完全图。含有n个顶 数据结构 点,每一个顶点都与其它个n1顶点有边,因此,共有 n(n-1)2条边 有向完全图:在有向图G中,任何两个顶点都有方向 相反的两条弧线连接,若图G中含有个m顶点,则共有 n(n-1)条弧。 无向完全图 有向完全图
2 数 据 结 构 之 图 3 ¾ 有向图： 在图G中，边是顶点的有序对，每 条边都用箭头指明了方向，若是有向 图中的一条边，则称Vi 是尾或初始顶点；Vj 是 头或终端顶点，且用从尾到头的箭头表示， 和不同。 ¾ 无向图： 边是顶点的无序对， 和 表示同一条边。 V1 V2 V3 V4 V5 有向图 V1 V2 V3 V4 V5 无向图 数 据 结 构 之 图 4 ¾ 无向完全G图：如果在无向图中，任何两个顶点都有 一条边相连接，则称此图为无向完全图。含有n个顶 点，每一个顶点都与其它个n-1顶点有边，因此，共有 n*(n-1)/2条边。 ¾ 有向完全图：在有向图G中，任何两个顶点都有方向 相反的两条弧线连接，若图G中含有个n顶点，则共有 n*(n-1)条弧。 V1 V2 V3 V4 V5 无向完全图 V1 V2 V3 V4 V5 有向完全图
网:如果图G(V,{E})中每条边都赋有反映这 据结构 条边的某种特性的数据,则称此图G是一个网, 其中与边相关的数据称为该边的权,权所反 映的特性,由具体问题决定,例于两点之间 的距离,时间,代f 网 子图:假设有两个图G=(V,{E})和图G=(V 数{E}),如果ⅤV,且E'cE,则称G为G的子图。 据 构 无向图 >邻接点:对于无向图G=(V,{E}),如果边∈E, 则称顶点和V互为邻接点,边(V,V)依附于顶点V和
3 数 据 结 构 之 图 5 ¾ 网： 如果图G(V,{E})中每条边都赋有反映这 条边的某种特性的数据，则称此图G是一个网， 其中与边相关的数据称为该边的权，权所反 映的特性，由具体问题决定，例于两点之间 的距离，时间，代价。 网 V1 V2 V3 V4 V5 5 3 6 4 8 7 1 2 V1 V2 V3 V4 V5 4 5 6 8 3 数 据 结 构 之 图 6 ¾子 图：假设有两个图G=(V，{E})和图G’ =(V’ ， {E’ })，如果V’ ⊆V，且E’ ⊆E , 则称G’ 为G的子图。 V1 V2 V3 V4 V5 无向图 子图 V1 V2 V5 V1 V5 V4 V3 V2 V2 V1 V1 V2 V5 V3 ¾邻接点： 对于无向图G=(V,{E})，如果边∈E, 则称顶点V和V’ 互为邻接点，边(V,V’ )依附于顶点V和 V’
度:顶点V的度是和V相关联的边的数目,记为 TD(。 据>入度:如果顶点V是有向图的一个顶点,则称以V为 头的弧的数目为V的入度,记为D(。 出度:如果顶点是有向图的一个顶点,则称以为 尾的弧的数目为V的出度,记为ODD >有向图顶点的度:顶点的度TD(V=D(+OD( 推论:如果顶点V的度为TD(V),那么有n个顶点, e条边或弧的图,满足如下关系 ⑦D(v,) 路径:图中从顶点到顶点v的路径是顶点 的序列(V=V,V1,…,Vm=V),其中 构 Vi∈E,15Jm。 路径的长度:路径上所含边的数目。 之>回路:第一个顶点和最后一个顶点相同的路 径称为回路或环 圆>简单路径:序列中顶点不重复出现的路径称 为简单路径。 简单回路:除第一个和最后一个顶点之外, 其它顶点不重复出现的回路称为简单回路或环
4 数 据 结 构 之 图 7 ¾度：顶点V的度是和V相关联的边的数目，记为 TD(V)。 ¾入度：如果顶点V是有向图的一个顶点，则称以V为 头的弧的数目为V的入度，记为ID(V)。 ¾出度：如果顶点V是有向图的一个顶点，则称以V为 尾的弧的数目为V的出度，记为OD(V)。 ¾有向图顶点的度：顶点V的度TD(V)=ID(V)+OD(V)。 推论： 如果顶点Vi 的度为TD（Vi ），那么有n个顶点， e条边或弧的图，满足如下关系 ∑= = n i i e TD v 1 ( ) 2 1 数 据 结 构 之 图 8 ¾路径： 图中从顶点V到顶点V’ 的路径是顶点 的序列（V=Vi,0, Vi,1, …, Vi,m = V’），其中 （Vi,j-1, Vi,j)∈E，1≤ j ≤m。 ¾路径的长度：路径上所含边的数目。 ¾回路： 第一个顶点和最后一个顶点相同的路 径称为回路或环。 ¾简单路径：序列中顶点不重复出现的路径称 为简单路径。 ¾简单回路：除第一个和最后一个顶点之外， 其它顶点不重复出现的回路称为简单回路或环
连通:在无向图G中,若从顶点V到顶点V有路径, 则称V和V是连通的 据>连通图:若对于图中任意两个顶点v,V∈V 结都是连通的,则称是连通图。 连通分量:指无向图中极大连通子图。 强连通图:在有向图中,如果对每一对v;V; ∈V,V;≠V;,从V到V和从V到V都存在路径,则 称G是强连通图。有向图G的极大强连通子图称为 强连通分量。 不是强连通图 两个强连通分量 生成树 据 定义:设无向图G是含有n个顶点的连通图,则图G 构的生成树是含有n个顶点,且只有m1条边的连通子图 小连通子 n个顶点 图,若再加 n-1条边 条边,必 连通 勾成 10 生成树=→m-1条边
5 数 据 结 构 之 图 9 ¾连通： 在无向图G中，若从顶点V到顶点V’ 有路径， 则称V和V’ 是连 通的。 ¾连 通 图： 若对于图中任意两个顶点 Vi ，Vj ∈V 都是连通的，则称是连通图。 ¾连通分量：指无向图中极大连通子图。 ¾强连通图：在有向图中，如果对每一对Vi ，Vj ∈V ， Vi ≠Vj ，从Vi 到Vj 和从Vj 到Vi 都存在路径，则 称G是强连通图。有向图G的极大强连通子图称为 强连通分量。 1 2 3 4 1 2 3 4 不是强连通图 两个强连通分量 数 据 结 构 之 图 10 ¾ 生成树 定义：设无向图G是含有n个顶点的连通图， 则图G 的生成树是含有n个顶点，且只有n-1条边的连通子图 三要素： n个顶点 n-1条边 连通 生成树 n-1条边 极小连通子 图，若再加 一条边，必 构成环
数图的基本操作 LOC-VERTEX(G,v):顶点定位函数 构 GET-VERTEX(G,I):取顶点函数; FIRST-ADJ (G, v) 求第一个邻接点函数 之 NEXT-ADJ(G,v,w):求下一个接点函数; INS-VERTEX(G,u):插入顶点操作; 图INS-ARC(G,v,w):插入弧操作; DEL-VERTEX(G,v):删除顶点操作; DEL-ARC(G,v,w):删除弧的操作 72图的存储结构 数>邻接矩阵:用一个二维数组来表示图中的相邻关系。 设图G(V,NR)有n1个顶点,则G的邻接矩阵是 构按如下定义的n阶方阵: 1,若(i,V)或∈VR 0,反之 无向图G2的邻接矩阵 0110 A1=0000 10101 12 0001 A2=01011 1000 10100 有向图G1的邻接矩阵 01100
6 数 据 结 构 之 图 11 图的基本操作 LOC-VERTEX（G，v）： 顶点定位函数； GET-VERTEX（G，I）： 取顶点函数； FIRST-ADJ（G，v）： 求第一个邻接点函数； NEXT-ADJ（G，v，w）： 求下一个接点函数； INS-VERTEX（G，u）： 插入顶点操作； INS-ARC（G，v，w）： 插入弧操作； DEL-VERTEX（G，v）： 删除顶点操作； DEL-ARC（G，v，w）： 删除弧的操作。 数 据 结 构 之 图 12 7.2 图的存储结构 ¾ 邻接矩阵：用一个二维数组来表示图中的相邻关系。 设图G=（V，VR）有n≥1个顶点，则G的邻接矩阵是 按如下定义的n阶方阵： 1，若（Vi , Vj )或∈ VR A[i，j]= 0，反之 无向图G2的邻接矩阵 0 1 1 0 0 1 0 1 0 A1= 0 0 0 0 1 0 1 0 1 0 0 0 1 A2= 0 1 0 1 1 1 0 0 0 1 0 1 0 0 有向图G1的邻接矩阵 0 1 1 0 0
/例:分别写出下面图的邻接矩阵 0100 0100 1011 0010 0001 0110 0100 邻接矩阵存储的特点 数据结构 无向图的邻接矩阵是对称的,对有n个顶 点的无向图只需存入下三角矩阵,即需要 n(n+1)/2个存储单元; 而有向图的邻接矩阵不一定对称,对有n 个顶点的有向图需要n*n个单元来存储邻 接矩阵; 另外用向量来存储顶点的有关信息;
7 数 据 结 构 之 图 13 例：分别写出下面图的邻接矩阵。 1 2 3 4 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 2 3 4 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 数 据 结 构 之 图 14 ¾ 邻接矩阵存储的特点 ¾无向图的邻接矩阵是对称的，对有n个顶 点的无向图只需存入下三角矩阵，即需要 n(n+1)/2 个存储单元； ¾而有向图的邻接矩阵不一定对称，对有n 个顶点的有向图需要n*n个单元来存储邻 接矩阵； ¾另外用向量来存储顶点的有关信息；
求顶点的度 据结构 对无向图,vi的度数=邻接矩阵第i行元 素之和 TDi=∑AG,j=∑A[,i 对有向图,vi的出度=第i行元素之和 vi的入度=第i列元素之和 TD(Vi=OD(VITID(Vi) ∑A[i,+∑A[j,i >网的邻接矩阵 w,若(Vi,V)或∈ⅤR 据A[i,jl=10,(i=j) 构 反之 05 04 0 0∞506 50 3∞∞∞10
8 数 据 结 构 之 图 15 ¾求顶点的度 ¾对无向图，Vi的度数=邻接矩阵第 i 行元 素之和 ¾对有向图，Vi的出度=第 i 行元素之和 Vi的入度=第 i 列元素之和 n n TD(Vi)=∑A[i,j]=∑A[j,i] j=1 j=1 TD(Vi)=OD(Vi)+ID(Vi) n n = ∑A[i,j]+∑A[j,i] j=1 j=1 数 据 结 构 之 图 16 ¾ 网的邻接矩阵 wi , j，若（Vi , Vj )或∈ VR A[i，j]= 0 , ( i = j ) ∞，反之 0 5 ∞ 7 ∞ ∞ ∞ 0 4 ∞∞ ∞ 8 ∞ 0 ∞ ∞ 9 ∞ ∞ 5 0 ∞ 6 ∞∞∞ 5 0 ∞ 3 ∞ ∞∞ 1 0 V1 V2 V3 V4 V6 V5 1 5 3 5 4 8 7 9 6 5
>图的数组(邻接矩阵)存储表示邻接矩阵 #define max Data 35000 提# define VerNum20 结/有向图,有向网,无向图,无向网 M typedef enum(DG, DN, UDG, UDN GraphKind typedef char VertexType typedef int VRType;/顶点关系0/或“权值 typedef struct( VRType adj; Info Type *information; ArcType; typedef structi VertexType vex verNum; ArcType arcs VerNum VerNum; int vernum arenum. Graph Kind kind; MGraph; 采用邻接矩阵表示法,构造图 s Status Create Graph(MGraph &G)( 构 scanf(&G kind) switch(G kind)t case DG: return CreateDG(G) case DN: return CreateDN(G); case UDG: return CreateUDG(G); case UDN: return CreateUDN(G) default: return ERROR;
9 数 据 结 构 之 图 17 ¾ 图的数组（邻接矩阵）存储表示邻接矩阵 #define MaxData 35000 #define VerNum 20 /* 有向图，有向网，无向图，无向网 */ typedef enum{DG, DN, UDG, UDN}GraphKind; typedef char VertexType; typedef int VRType; /*顶点关系 0/1 或 “权值” typedef struct{ VRType adj; InfoType *information; }ArcType; typedef struct{ VertexType vexs[VerNum]; ArcType arcs[VerNum][VerNum]; int vernum, arcnum; GraphKind kind; } MGraph; 数 据 结 构 之 图 18 采用邻接矩阵表示法，构造图 Status CreateGraph(MGraph &G){ scanf(&G.kind); switch(G.kind){ case DG: return CreateDG(G); case DN: return CreateDN(G); case UDG: return CreateUDG(G); case UDN: return CreateUDN(G); default: return ERROR; } }
采用邻接矩阵表示法,构造无向网 Status CreateUDN(MGraph &G) scanf(&G. vexnum, &G arcum, &Infoflag); I* for(i-0;i的权值* if(infoflag) input( G arcs[jj. information) 19 G.ares[jlliI=G arcs[illil; 3 return OK: 邻接链表 数 据 图的邻接链表存储结构是一种顺序分配和链 式分配相结合的存储结构:一部分是链表; 构 另一部分是向量 链表部分:每个顶点对应一个链表,共有n 个链表; 向量部分:用于存储n个链表的表头结点。 4 20 4 4vs-2一
10 数 据 结 构 之 图 19 采用邻接矩阵表示法，构造无向网 Status CreateUDN(MGraph &G){ scanf(&G.vexnum,&G.arcnum,&Infoflag); for(i=0;i的权值 */ if(infoflag) input(*G.arcs[i][j].information); G.arcs[j][i]=G.arcs[i][j]; } return OK; } 数 据 结 构 之 图 20 ¾ 邻接链表 ¾ 图的邻接链表存储结构是一种顺序分配和链 式分配相结合的存储结构：一部分是链表； 另一部分是向量。 ¾ 链表部分：每个顶点对应一个链表，共有n 个链表； ¾ 向量部分：用于存储n个链表的表头结点。 V1 V2 V4 V5 V3 0 v1 1 v2 2 v3 3 v4 4 v5 3 1 ^ 2 0 ^ 2 1 ^ 4 3 4 2 0 ^ 1 ^