《数据结构与算法》第7章 图

第七章图 图的定义和术语 图的存储结构 图的遍历与连通性 o最小生成树 活动网络 o最短路径

图的定义和术语 图的存储结构 图的遍历与连通性 最小生成树 活动网络 最短路径

71图的定义和术语 图形结构的形式定义图是由顶点集合 vertex)及顶点 间的关系集合组成的一种数据结构: Graph=(V,R) 其中 V={x|x∈某个数据对象},是顶点的有穷非空集合; R边的有限集合 R={(x,y)|x,y∈V}无向图或 R={x,y>|x,y∈&&Path(x,y)}有向图 是顶点之间关系的有穷集合,也叫做边(edge)集合。 Pth(x,y)表示从x到y的一条单向通路,它是有方向 的。x弧尾,y弧头

7.1 图的定义和术语 图形结构的形式定义 图是由顶点集合(vertex)及顶点 间的关系集合组成的一种数据结构： Graph＝( V, R ) 其中： V = { x | x  某个数据对象} ， 是顶点的有穷非空集合； R——边的有限集合 R = {(x, y) | x, y  V } 无向图 或 R = { | x, y  V && Path (x, y)}有向图 是顶点之间关系的有穷集合，也叫做边(edge)集合。 Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向 的。x弧尾，y弧头

有向图与无向图 令有向图中:边用表示,且x与y是有序的。 a.有向图中的边称为“弧 bx弧尾或初始点y弧头或终端点 无向图:边用(x,y)表示,且顶x与y是无序的 完全图 令在具有n个顶点的有向图中,最大孤数为n(n-1) 令在具有n个顶点的无向图中,最大边数为n(n-1)2 顶点的度 无向图:与该页点相关的边的数目 令有向图 入度(v):以该顶点为头的弧的数目 出度OD(v):以该顶点为尾头的弧的数目

有向图与无向图 ❖ 有向图中：边用表示，且x与y是有序的。 a. 有向图中的边称为“弧” b. x——弧尾或初始点 y——弧头或终端点 ❖ 无向图：边用(x, y) 表示，且顶x与 y是无序的。 完全图 ❖ 在具有n 个顶点的有向图中，最大弧数为n(n-1) ❖ 在具有n 个顶点的无向图中，最大边数为n(n-1)/2 顶点的度 ❖ 无向图：与该顶点相关的边的数目 ❖ 有向图： 入度ID(v) ：以该顶点为头的弧的数目 出度OD(v) ：以该顶点为尾头的弧的数目

在有向图中,顶点的度等于该顶点的入度与出度 之和 邻接点 令无向图:两顶点之间有条边,则两顶点互为邻接点 -y( y) 令有向图:从x到y有一条弧,则y是x的邻接点, 但x不是y的邻接点 X→→y

在有向图中, 顶点的度等于该顶点的入度与出度 之和。 邻接点 ❖ 无向图：两顶点之间有条边，则两顶点互为邻接点 x —— y ( x ,y ) ❖ 有向图：从x到y有一条弧，则y是x的邻接点， 但x不是y的邻接点 x y

权某些图的边具有与它相关的数,称之为权。 这种带权图叫做网络。 0子图设有两个图G=(VE)和G=(V,E") 若vcV且EcE,则称图G是图G的子图 1 3 (a)G1 子图 子图 子图 b)63子图子图子图

权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。 若 V’ V 且 E‘E, 则称 图G’是 图G 的子图

路径在图G=(V,E)中,若从顶点v出发,沿一些边 经过一些顶点v,V23…,vm,到达顶点v则称顶点 序列(V1v2…Vmv)为从顶点v到顶点y的路径。 它经过的边(vv1(V)…、(vmv应是属于E 的边。 路径长度 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和

路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边 经过一些顶点 vp1 , vp2 , …, vpm，到达顶点vj。则称顶点 序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。 它经过的边(vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj )应是属于E 的边。 路径长度 非带权图的路径长度是指此路径上边/弧的条数。 带权图的路径长度是指路径上各边/弧的权之和

简单路径若路径上各顶点v,2…,n均不互相 重复,则称这样的路径为简单路径。 回路着路径上第一个顶点v1与最后一个顶点 vn重合,则称这样的路径为回路或环。 (a)简单路径 (b)非简单路径 (C)回路 连通图与连通分量在无向图中若从顶点v到 顶点v有路径,则称顶点v与v2是连通的。如果 图中任意一对顶点都是连通的,则称此图是连通 图。非连通图的极大连通子图叫做连通分量

简单路径 若路径上各顶点 v1 ,v2 ,...,vm 均不互相 重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合, 则称这样的路径为回路或环。 连通图与连通分量 在无向图中, 若从顶点v1到 顶点v2有路径, 则称顶点v1与v2是连通的。如果 图中任意一对顶点都是连通的, 则称此图是连通 图。非连通图的极大连通子图叫做连通分量

强连通图与强连通分量在有向图中,若对于每一对顶 点v和v都存在一条从w到v和从v到v的路径,则称此 是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树一个连通图的生成树是它的极小连通子图, 在n个顶点的情那下,有n-1条边 令生成树是对指连通图来而言的 令是连同图的极小连同子图 令包含图中的所有顶点 令有且仅有n-条边 本章不予 讨论的图 d a)带自身环的图 b)多重图

强连通图与强连通分量 在有向图中, 若对于每一对顶 点vi和vj , 都存在一条从vi到vj和从vj到vi的路径, 则称此 图是强连通图。非强连通图的极大强连通子图叫做强 连通分量。 生成树 一个连通图的生成树是它的极小连通子图， 在n个顶点的情形下，有n-1条边。 ❖ 生成树是对指连通图来而言的 ❖ 是连同图的极小连同子图 ❖ 包含图中的所有顶点 ❖ 有且仅有n-1条边 本章不予 讨论的图

72图的存储表示 1.邻接矩阵( Adjacency Matrix)表示法 (数组表示法) 顶点表:一个记录各个顶点信息的一维数组, 0邻接矩阵:一个表示各个顶点之间的关系(边 或弧)的二维数组。 设图G=(V,E是一个有n个顶点的图,则图的 邻接矩阵 G arcsIn四定义为 Garculli|1若V,vj>或(Ⅴ)∈E 0反之

7.2 图的存储表示 顶点表: 一个记录各个顶点信息的一维数组， 邻接矩阵：一个表示各个顶点之间的关系（边 或弧）的二维数组。 设图 G = (V, E)是一个有 n 个顶点的图，则图的 邻接矩阵G.arcs[n][n] 定义为： G.arcs[i][j]= 1 若 或(Vi,Vj)∈E 0 反之 1. 邻接矩阵 (Adjacency Matrix)表示法 （数组表示法）

1)类型定义 # define maX VErTEX num20/最大顶点数 typedef int AdjMatrix MAX VERTEX NUMIIMAX VERTEX NUMB ∥接矩阵类型 typedef struct i Vertex Type vexs MAX VERTEX NUM];/顶点表 AdjMatrix arcs ∥接矩阵 int vexnum arcum /图的顶点数和弧数 } MGraph;(有四个域)

1）类型定义 #define MAX_VERTEX_NUM 20 //最大顶点数 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵类型 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点表 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的顶点数和弧数 } MGraph;（有四个域）