数据结构第七章(上)

7.2.2 邻接表 实现：为图中每个顶点建立一个单链表，第i个单 链表中的结点表示依附于顶点Vi的边（有向图中指 以Vi为尾的弧）。 邻接表的类型定义参见P163。
例： a c b d
表结点 头结点 邻接点的位 置，即序号
数据结构
adjvex nextarc vexdata firstarc adjvex nextarc 2 ^
G1 vexdata firstarc 1 a b 2 ^ 3 c 4 d
3 4 1 ^ ^
数据结构 例： a c d G2 e adjvex nextarc 4 ^ 3 4 3 3 ^ ^ 5 5 ^ ^ b
vexdata firstarc 2 1 a b 2 1 3 c 2 4 d 1 5 e 2
⎧1, 若(v i , v j )或 < v i , v j >∈ E A[i, j ] = ⎨ ⎩0，其它
例： 1 3 G1 2 4
⎡0 ⎢ ⎢0 ⎢0 ⎢ ⎢1 ⎣ 1 0 0 0 1 0 0 0 0⎤ ⎥ 0⎥ 1⎥ ⎥ 0⎥ ⎦
数据结构 例： 1 3 4 G2 5 2
⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 ⎤ ⎥ 1 ⎥ 1 ⎥ ⎥ 0 ⎥ ⎥ 0 ⎥ ⎦
⎧ω ij , 若(v i , v j )或 < v i , v j >∈ E 网的邻接矩 阵可定义为： A[i, j ] = ⎨∞，其它 ⎩
例： 1 3 7 5 2
⎡∞ ⎢ ⎢5 ⎢7 ⎢ ⎢∞ ⎢ ⎢3 ⎣ 5 ∞ ∞ 4 8 7 ∞ ∞ 2 1 ∞ 4 2 ∞ 6 3⎤ ⎥ 8⎥ 1⎥ ⎥ 6⎥ ⎥ ∞⎥ ⎦
数据结构
连通分量（强连通分量） 无向图G 的极大连通子图称为G的连通分量。 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。 V0 V1 V4 非 连 通 V3 V2 V5 连通分量 图
V0 V3 V1 V2 V4 V5
数据结构
有向图G 的极大强连通子图称为G的强连通分量。 极大强连通子图意思是：该子图是G的强连通子图 ，将D的任何不在该子图中的顶点加入，子图不再 是强连通的。
非 连 通 图 非 强 连 通 图
V2
V3
V2
V3
数据结构
权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 子图 设有两个图G=（V，{E}）、G1=（V1，{E1}）， 若V1⊆ V，E1 ⊆ E，则称 G1是G的子图。 例:(b)、(c) 是 (a) 的子图
V0 V2 V3 (a) V4 V3 (b) V1 V0 V2 V4 V3 (c) V1 V0 V2 V4 V1
V0 V1 V2 V3 V4 V0 V1
无向图G1
有向图G2
V2 V3
数据结构
连通图（强连通图） 在无（有）向图G=( V, {E} )中，若对任何两个顶 点 v、u 都存在从v 到 u 的路径，则称G是连通图 （强连通图）。 连 通 图 强 连 通 图
V0 V2 V3 V0 V4 V1 V3 V0 V2 V5 V1 V1 V0 V1 V4
数据结构
数据结构
7.1 图的定义和术语
图的定义：是一种多对多的结构关系，每个元素 图的定义： 可以有零个或多个直接前趋；零个或多个直接后 继。图是由顶点集合(vertex)及顶点间的关系集 合组成的一种数据结构： Graph＝( V, R ) 其中 V = { v | v ∈ 某个数据对象}
是顶点的有穷非空集合； R ={VR}={(v, w) | v, w ∈ V } 图的类型定义参见P156
V0 V2 V3
V1ห้องสมุดไป่ตู้
V4
V0
V1
V2
V3
数据结构
路径、回路 无向图G =（V，{E}）中的顶点序列v1,v2,… ,vk, 若(vi,vi+1)∈E( i=1,2,…k-1), v =v1, u =vk, 则 称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。 例：
V0 V2 V3 V4 V1
数据结构
基本术语： 有向图与无向图 在有向图中，顶点对<v, w>是 有序的。在无向图中，顶点对(x, y)是无序的。 1 有向图 2 3 6 7 5 4 有向边又可称为弧, <vi,vj> 中vi称为狐尾或初始点，vj 狐尾 称为狐头或终端点。 狐头
V={1,2,3,4,5,6,7} VR={<1,3>,<1,2>,<3,7>,<3,6>,<2,5>,<2,6>, <2,4>,<5,7>,<6,7>}
在图G1中，V0,V1,V2,V3 是V0到V3的路径。 V0,V1,V2,V3,V0是回路。
数据结构
有向图G =（V，{E}）中的顶点序列v1,v2,… ,vk, 若<vi,vi+1>∈E (i=1,2,…k-1), v =v1, u =vk, 则 称该序列是从顶点v到顶点u的路径。 若v=u，则称该序列为回路。 例： 有向图G2
强连通分量 V0 V1 V0 V1
V2
V3
V2
V3
权与网 图中边或弧所具有的相关数称为权。表明从一 个顶点到另一个顶点的距离或耗费。带权的图 称为网。
数据结构
生成树和生成森林 极小连通子图：该子图是G 的连通子图，在该子 极小连通子图 图中删除任何一条边，子图不再连通。 包含无向图G 所有顶点的极小连通子图称为G 的 生成树。对非连通图，则称由各个连通分量的生 成树的集合为非连通图的生成森林。
数据结构
1 3 4 5 6 7 2 无向图
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) }
数据结构
邻接点及关联 若无向图中存在边(v, u)，则称顶点v 和u互为邻接点；边(v, u)依附于顶点v 和u；或者说边(v, u)和顶点v和u相关 联。 顶点的度、入度、出度 在无向图中： 顶点V的度 = 与V相关联的边的数目 在有向图中： 顶点V的出度=以V为狐尾的有向边数 顶点V的入度=以V为狐头的有向边数 顶点V的度= V的出度+V的入度
V2 V3 V0 V1
在图G2中，V0,V2,V3 是V0到V3的路径。 V0,V2,V3,V0是回路。
数据结构
简单路径和简单回路 在一条路径中,若除起点和终点外,所有顶点各不 相同,则称该路径为简单路径。 由简单路径组成的回路称为简单回路。 在图G1中，V0,V1,V2,V3 是简单路径。 V0,V1,V2,V4,V1不是简单路径。 在图G2中， V0,V2,V3,V0是简单回路。
8 4 5 1 6 3 4 2
邻接矩阵类型定义:
数据结构
#define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 typedef enum{DG,DN,AG,AN} GraphKind; typedef struct ArcCell //边或弧的结构 { VRType adj; // 顶点关系：0/1或权值 InfoType * info; //边或弧相关信息的指针 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_ NUM] typedef struct { VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; GraphKind kind; }MGraph;
《 数据结构》
第七章(上)
第七章 图
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 每一对顶点之间的最短路径
数据结构
逆邻接表：有向图中对每个结点建立以Vi为弧头 的弧的单链表。
例： a b 1 c G1 d 2 3 4 vexdata a b c d firstarc adjvex nextarc 4 1 1 3 ^ ^ ^ ^
V0 V2 V3 V4 V3 V1 V0 V2 V4 V1 V3 V2 V0 V1 V4
连通图 G1
G1的生成树
图的几种基本操作参见P158。
数据结构
7.2.1 数组表示法 邻接矩阵：表示顶点间相联关系的矩阵。 邻接矩阵： 定义：设G=(V,{E})是有n≥1个顶点的图，G的邻接 矩阵A是具有以下性质的n阶方阵：