图论中搜索算法讲座.ppt

图论中搜索算法讲座
第1页，共57页，编辑于2022年，星期五
图论中搜索算法和最短路径算法
*
第2页，共57页，编辑于2022年，星期五
Read Euler, read Euler,
he is the m的度是和 v 相关联的边的数目，记做TD(v)。
v1
v2
v3
v5
v4
顶点 v3 的度为 3
对于有向图，顶点 v 的度 TD(V) 分为两部分——出度、入度。
以顶点 v 为头的弧的数目称为 v 的入度，记为ID(v) ；
以顶点 v 为尾的弧的数目称为 v 的出度，记为OD(v)；
顶点 v 的度为 TD(v) = ID(v) + OD(v)。
*
第14页，共57页，编辑于2022年，星期五
v1
v2
v4
v3
顶点 v1 的出度为 2
顶点 v1 的入度为 1
顶点 v1 的度为 3
*
第15页，共57页，编辑于2022年，星期五
路径、链、简单路径、回路(环)、简单回路
无向图 G 中若存在一条有穷非空序列 w = v0 e1 v1 e2 v2 ek vk ，其中 vi 和 ei 分别为顶点和边，则称 w 是从顶点 v0 到 vk 的一条路径。
…
顶点 v0 和 vk 分别称为路径 w 的起点和终点。
路径的长度是路径上的边的数目。
v0
v1
v2
vk-1
vk
. . .
e1
e2
ek
起点和终点相同的路径称为回路(环)。
*
第16页，共57页，编辑于2022年，星期五
若路径 w 的边 e1 , e2 , , ek 互不相同，则称 w 为链。
…
若路径 w 的顶点 v0 , v1 , , vk 互不相同，则称 w 为简单路径。
…
v0
v1
v2
vk-1
vk
. . .
e1
e2
ek
链是否为简单路径?
简单路径是否为链?
不一定
一定
e1
e2
e3
e4
e5
除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。
*
第17页，共57页，编辑于2022年，星期五
例
1
5
7
3
2
4
G2
6
路径：1，2，5，7，6，5，2，3
路径长度：7
简单路径：1，2，5，7，6
回路：1，2，5，7，6，5，2，1
简单回路：1，2，3，1
*
第18页，共57页，编辑于2022年，星期五
有向图 G 中若存在一条有穷非空序列 w = v0 e1 v1 e2 v2 ek vk ，其中 vi 和 ei 分别为顶点和弧，则称 w 是从顶点 v0 到 vk 的一条路径。
…
v0
v1
v2
vk-1
vk
. . .
e1
e2
ek
链
简单路径
回路
简单回路
*
第19页，共57页，编辑于2022年，星期五
例
2
4
5
1
3
6
G1
路径：1，2，3，5，6，3
路径长度：5
简单路径：1，2，3，5
回路：1，2，3，5，6，3，1
简单回路：3，5，6，3
*
第20页，共57页，编辑于2022年，星期五
连通、连通图
无向图G，如果从顶点 v 到顶点 v’ 有路径，则称 v 和 v’ 是连通的。
如果对于无向图 G 中任意两个顶点 vi , vj ∈V, vi 和 vj 都是连通的，则称 G 是连通图。
v1
v2
v3
v5
v4
是否为连通图
*
第21页，共57页，编辑于2022年，星期五
第2节 图的存储结构
顺序存储
邻接矩阵
链式存储
邻接表
邻接多重表
十字链表
如何表达顶点之间存在的联系？
v1
v2
v4
v3
*
第22页，共57页，编辑于2022年，星期五
邻接矩阵
设图 G = ( V ，E ) 具有 n(n≥1) 个顶点 v1 , v2 , , vn 和 m 条边或弧 e1 , e2 , , em ，则 G 的邻接矩阵是 n×n 阶矩阵，记为 A(G) 。
…
…
其每一个元素 aij 定义为:
邻接矩阵存放 n 个顶点信息和 n2 条边或弧信息。
aij =
0
1
顶点 vi 与 vj 不相邻接
顶点 vi 与 vj 相邻接
v1
v2
v4
v3
例有向图 G
A(G) =
1 2 3