当前位置：文档之家 › 数据结构第七章图PPT课件

数据结构第七章图PPT课件

  • 格式：ppt
  • 大小：3.56 MB
  • 文档页数：30

下载文档原格式

  / 30

合集下载

《数据结构》大本课件-7

《数据结构》大本课件-7

是一条简单回路；“v2→v1→v2→v4→v5→v3→v1→v2”是一条回路。
V1
4. 无向完全图、有向完全图
V1
V2
. 有n个顶点的无向图，最多可有n(n−1)/2
V2
V3
条边。如果一个有n个顶点的无向图，拥有
n(n−1)/2条边，那么就称该图为“无向完全图”。
可见，一个无向完全图的每个不同顶点对之 V3
度与出度之和，即：D(vi)=ID(vi)+OD(vi)。
V2
V3
. 比如在有向图里，由于弧< v2, v1>和< v3, v1>都以顶点v1为
弧头，所以顶点v1的入度ID(v1)=2；由于弧< v1, v2>以顶点v1为弧尾， 所以顶点v1的出度OD(v1)=1；于是，顶点v1的度为：
V4
V5
D(v1)=ID(v1)+OD(v1)=2+1=3
其他顶点 。
V6
. 比如，如图所示为一个非连通图，因为从顶点
v1没有路径可以到达顶点v7。
. 比如，该图的两个连通分量如图(a)和(b)所示。 V3
V1 V3
V6
V2
V7
V8
V4
V5
V9
(a)
(b)
7. 边的权、网络
. 可给图的边或弧依附上某种数值，这种
38 V1
与图的边或弧相关的数值被称为“权”。 44
V4
V4
V5
间，都存在有一条边。
. 如图所示是一个无向完全图，因为它有4个顶点，且它有4(4−1)/2=6条边，符合无
向完全图的定义。
. 对于有n个顶点的有向图，最多可以有n(n−1)条弧。如果一个有n个顶点的有向图，

数据结构严蔚敏7章图ppt课件

数据结构严蔚敏7章图ppt课件

InfoType *info;
}VNode,AdjList[MAX_V];
}ArcNode;
typedef struct //图的邻接表类型
{ AdjList vertices; //存储图中所有顶点的数组
int vexnum,arcnum; //存储图的顶点数目和边(弧)的数目
int kind; //图的种类标志
返回
表结点
adjvex nextarc info
表头结点
data firstarc
typedef struct ArcNode typedef struct
{ int adjvex;
{ VertexType data;
struct ArcNode *nextarc; ArcNode *firstarc;
}ArcCell,AdjMatrix[MAX_V][MAX_V];
typedef struct
{ VertexType vex[MAX_V]; //顶点信息数组(如顶点编号等)
AdjMatrix arcs;
//图的邻接矩阵
int vexnum,arcnum; //图的顶点数和边(弧)的数目
GraphKind kind;//图的种类标志
A CB F DE G (a) 有向图G1
A BC D EF (b) 无向图G2
返回
2 几个常用术语 可以证明,对于具有n个顶点的无向图的边和具有n个
顶点的有向图的弧的最大数目分别为n(n-1)/2和n(n-1)。 称具有n(n-1)/2条边的无向图为完全图(completed
grahp)。 称具有n(n-1)条弧的有向图为完全有向图 称边或弧的数目e<nlogn的图为稀疏图(sparse

数据结构《第七章、图》PPT课件

数据结构《第七章、图》PPT课件
由于“弧”是有方向的，因此称由顶点集 和弧集构成的图为有向图。
例如: G1 = (V1, VR1)
其中 A
V1={A, B, C, D, E}
B
E VR1={<A,B>, <A,E>,
C
D
<B,C>, <C,D>, <D,B>, <D,A>, <E,C> }
若<v, w>VR 必有<w, v>VR, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。
A
B
EB
E
CF
CF
假设一个连通图有 n 个顶点和 e 条边， 其中 n-1 条边和 n 个顶点构成一个极小连 通子图，称该极小连通子图为此连通图的 生成树。
B A
F
C D
E
对非连通图，则 称由各个连通分 量的生成树的集 合为此非连通图 的生成森林。
基本操作
结构的建立和销毁 对顶点的访问操作
插入或删除顶点 插入和删除弧
7.2 图的存储表示
一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
一、图的数组(邻接矩阵)存储表示
定义:矩阵的元素为
{ 0 (i,j)VR
Aij= 1 (i,j)VR
B A
F
C D
E
010010 100010 000101 001001 110000 011100
含有 e=n(n-1) 条弧的有向图称作 有 向完全图;
若边或弧的个数 e<nlogn，则称作 稀疏图，否则称作稠密图。
假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点， 边(v,w) 和顶点v 和w 相关联。

《数据结构》课件——第7章 图

《数据结构》课件——第7章 图

邻接矩阵
arc=
V1
1
0
1
1
V1
V2
V2 0 1 0 0
V3 1 1 0 0
无向图的邻接矩阵的特点？
主对角线为 0 且一定是对称矩阵。
无向图的邻接矩阵
V0
V3
V1
V2
如何求顶点 Vi 的度？
012 3
vertex= V0 V1 V2 V3
V0 V1 V2 V3
V0 0 1 0 1 arc= V1 1 0 1 1
V0
V1
V2
V3
V4
生成树
V0 V3
V1
V6
生成森林
V5
V4
V2
V0
V3 V0 V4
V1 V2
V4
V1 V3 V6 V5
V2
案例：六度空间理论
➢ 你和任何一个陌生人之间所间隔的 人不会超过6个，也就是说，最多通 过6个中间人你就能够认识任何一个 陌生人。
图的抽象数据类型定义
图是一种与具体应用密切相关的数据结构，它的基本操作往往随 应用不同而有很大差别。下面给出一个图的抽象数据类型定义的例子 ，简单起见，基本操作仅包含图的遍历，针对具体应用，需要重新定 义其基本操作。
V0 V3
V1 V6
V5
V4
V2
V0
V1
V4 V3
V2 V6
连通分量是对无向图的一种划分
V5
图的基本术语
➢ 强连通图：在有向图中，对图中任意一对顶点vi和vj （i≠j），若 从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称该有向图是
强连通图。 ➢ 强连通分量：非强连通图的极大强连通子图。

数据结构课件 第7章 图

数据结构课件 第7章 图

例如下列定义的有向图如右图所示。 G1=(V1, VR1) 其中：V1 = {A, B, C, D, E} VR1={<A,B>,<A,E>,<B,C>,<C,D>, <D,B>,<D,A>,<E,C>}
例如下列定义的无向图如右所示。 G2=(V2, VR2) 其中：V2={A, B, C, D, E, F} VR2={(A,B),(A,E),(B,E),(C,D) ,(D,F),(B,F),(C,F) }
图的构造 操作的实现框架
Status CreateGraph (MGraph &G) { //采用数组（邻接矩阵）表示法，构造图G Scanf(&G.kind); Switch(G.kind) case DG：return CreatDG; //构造有向图G case DN：return CreatDN; //构造有向网G case UDG：return CreatUDG; //构造有向图G case UDN：return CreatUDN; //构造有向网G default：return ERROR; }
7.2 图的存储表示 7.2.1 图的数组（邻接矩阵）存储表示 假设图中顶点数为n，则邻接矩阵 定义为
网的邻接矩阵的定义为，当vi到vj有弧相邻接时， aij 的值应为该弧上的权值，否则为∞。 将图的顶点信息存储在一个一维数组中，并将它的邻 接矩阵存储在一个二维数组中即构成图的数组（邻接矩阵） 表示。
FirstAdjVex(G, v); 初始条件：图 G 存在，v 是 G 中某个顶点。 操作结果：返回 v 的第一个邻接点。 若该顶点在 G 中没有邻接点，则返回“空”。 NextAdjVex(G, v, w); 初始条件：图 G 存在，v 是 G 中某个顶点， w 是 v 的邻接顶点。 操作结果：返回 v 的（相对于 w 的）下一个邻接 点。若 w 是 v 的最后一个邻接点，则返回"空"。

数据结构精品PPT课件第七章 图(ppt文档)

数据结构精品PPT课件第七章 图(ppt文档)

V0
V1
V2
V3
V4
V0
V1
V2
V3
练例习
245
1
3
6
G1
图G1中：V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
例 1
57
32
46
G2
图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
1
V1 0 0 1 0
1
V2 0 0 1 1
2
V3 0 0 0 1
V4 1 1 0 0 2
出度
1 2 1 2
0
0 1 01 1
1
2
G1.arcs
1
10
0 1
1 0
0 1
3
1010
0
0 1 01
1
G2.arcs 1 0 1
2
000
无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。
V1={v0 ,v1,v2,v3,v4 } E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}
7.1图的定义和术语
例
V0
V1
V2
V3
有序对<vi,vj> ： 用以为vi起点、以vj 为终点的有向线段表 示，称为有向边或弧 ；
G2=<V2,E2>
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第7章 图
CAC - 2
CAC - 3
7.1 图的定义和术语
7.1.1 图的定义和术语
1. 图的定义（graph）
图G由两个集合构成，记作G=<V,E> ，其中V是顶点的非空有限集合，
E是顶点间关系----边的有限集合，边是顶点的无序对或有序对集合。 。
【例】 V0
V1
V2
V3
V4
无序对(vi,vj)： 用连接顶点vi、vj的线段
V0
V1
V0
V1
V2
V3
V2
V3
两个强连通分量
CAC - 17
练习
具有n个顶点的强连通图至少有多少条边？是什么形状？
分析：强连通图是针对有向图而言的。由于强连通图要求 图中任何2个顶点之间能够连通，因此每个顶点至少要有一条 以该顶点为终点（弧头）和出发点（弧尾）的弧，每个顶点 的入度和出度至少各为1，即顶点的度至少为2。
边或弧
G2=<V2,E2> V2={ v0 ,v1,v2,v3 } E2={ <v0,v1 > , <v0,v2 >, <v2,v3 >,<v3,v0 > }
CAC - 6
7.1.1 图的定义和术语
2. 图的相关术语 （1）无向图：若图G中所有边是没有方向的，则称G为无向图。 （2）有向图：若图G中所有顶点间的连线是有方向的，则称G为有向图。 （3）顶点：数据元素Vi称为顶点。 （4）边和弧：P(Vi,Vj)表示在顶点Vi和Vj之间有线相连，如果是无向图， 则称该线为边；在有向图中，则称该连线为弧。边用顶点的无序偶对(Vi， Vj)表示，弧用有序偶对< Vi，Vj >表示。 （5）弧头和弧尾：有序偶对的第一个结点称为始点（或弧尾，即不带箭 头的一端），有序偶对的第二个结点称为终点（或弧头，即带箭头的一 端）。
（12）路径长度：非带权图的路径长度是指此路径上边的条数，带权图的 路径长度是指路径上各边的权之和。
V0
V1
V2
V3
V4
V0
V1
V2
V3
CAC - 11
7.1.1 图的定义和术语
（13）回路：若路径上第一个顶点 V1 与最后一个顶点Vm 重合，则称这样 的路径为回路或环。
（14）简单路径：若路径上各顶点 V1,V2,...,Vm 均不互相重复，则称这样 的路径为简单路径。
表示，称为无向边；
G1=<V1,E1>
V1={v0,v1,v2,v3,v4 } E1={ (v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3) ,(v2,v4) }
CAC - 5
7.1.1 图的定义和术语
V0
V1
V2
V3
有序对<vi,vj> ： 用以为vi起点、以vj为终点 的有向线段表示，称为有向
（6）有向完全图：在有向图中，如果任意两个顶点间都有方向互为相反 的两条弧连接，则称该图为有向完全图。n个顶点的有向图最大边数是 n(n-1)。 （7）无向完全图：在无向图中，如果任意两个顶点间都有一条边连接， 则称该图为无向完全图。n个顶点的无向图最大边数是n(n-1)/2。
（8）稠密图、稀疏图：若一个图接近完全图，则称为稠密图；边数很少 的图称为稀疏图。
顶点V的入度(ID)：以V为终点有向边数
顶点V的度TD(V)= OD(V)+ID(V)
V2
V3
CAC - 10
7.1.1 图的定义和术语
（10）边的权、网：与图的边或弧相关的数据信息称为权。在实际应用中， 权值可以有某种含义。边上带权的图称为网。
（11）路径：在图G=(V,E )中, 若从顶点Vi出发,沿一些边经过一些顶点Vp1, Vp2, …, Vpm，到达顶点Vj。则称顶点序列 (Vi,Vp1,Vp2 ... Vpm,Vj )为从顶点 Vi 到顶点Vj 的路径。它经过的边(Vi,Vp1)、(Vp1,Vp2)、...、(Vpm ,Vj)应是属 于E 的边。
（15）简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出 现的回路叫简单回路。
CAC - 12
7.1.1 图的定义和术语
(16) 子图
设有两个图 G＝(V, E) 和 G’＝(V’, E ’)。若 V’ V 且 E ’ E, 则称 图G’ 是 图G 的子图。
V0
V1
V2
V3
V4
(a)
V0
V1
V2
V3
V4
(b)
V0
V2
V3
V4
(c)
CAC - 13
7.1.1 图的定义和术语
(17) 连通、连通图：从顶点V 到顶点W 有一条路径，则说V和 W是连通的。图中任意两个顶点都是连通的图叫连通图。
V0
V1
V2
V3
V4
V0
V1
V4
V3
V2
V5
CAC - 14
7.1.1 图的定义和术语
（18）连通分量：无向图G的极大连通子图称为G的连通分量。 “极大”的含义是：该子图是G连通子图，将G的任何不在 该子图中的顶点加入，子图不再连通。
非
V0
V1
V4
连
通
图
V3
V2
V5
两个连通分量
CAC - 15
7.1.1 图的定义和术语
（19）强连通图：有向图中，如果对每一对顶点Vi，VjV, ViVj，从Vi到Vj 和从Vj到 Vi 都存在路径，则称G是强连通 图。
V0
V1
V0
V1
V2
V3Biblioteka V2V3CAC - 16
7.1.1 图的定义和术语
（20）强连通分量：有向图的极大强连通子图称为强连通分 量。
CAC - 7
7.1.1 图的定义和术语
描述图中两种关系的术语 ➢ 邻接：顶点之间的关系。若Vi与Vj间有边相连接， 则Vi与Vj互称邻接点； ➢ 关联：边与顶点间的关系。若Vi与Vj间有边相连接， 则称边(Vi,Vj)关联于顶点Vi,Vj。
V0
V1
V2
V3
V4
CAC - 8
7.1.1 图的定义和术语
CAC - 9
7.1.1 图的定义和术语
（9）顶点的度、入度、出度： 顶点V的度：关联于某顶点V 的边的数目。
V0
V1
V2
V3
V4
顶点的度与边数之间的关系：设图G的 顶点数为n，边数为e，则图的所有顶点 的度数和为2*e（每条边对图的所有顶 点的度数和“贡献”2度）
在有向图中：
V0
V1
顶点V的出度(OD)：以V为起点有向边数
这样根据图的顶点数、边数和各顶点度3者之间的关系， 可得边数=2*n/2=n。
对于强连通图，由于从每个顶点都可以到达其余所有顶点， 因此当每个顶点的入度和出度都为1时，这个图一定是一个n 的顶点构成的环。
CAC - 18
7.1.2 图的基本运算
1. LocateVex(G,u) 初始条件：图G存在 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否 则返回其它信息。 2. GetVex(G,v) 初始条件：图G存在，v是G中某个顶点的编号 操作结果：返回v的值 3. FirstAdjVex(G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空”。