图搜索基础.pptx

1
一、图搜索概论
1 树与图的回顾
树和图的定义、基本术语
图的存储结构
树和图的遍历方法
2 显式图&隐式图
3 图搜索术语&方法分类
二、广度优先搜索三、深度优先搜索
2
树型结构(非线性结构)
结点之间有分支
具有层次关系
例
自然界:树
人类社会
家谱
行政组织机构
计算机领域
编译:用树表示源程序的语法结构
数据库系统:用树组织信息
算法分析:用树描述执行过程
国务院
山东省
北京市
西藏自治区
…
济南市
青岛市
威海市
…
历下区
市中区
…
历城区
树的意义?
1 树与图的回顾
3
树的定义和基本术语
定义:
树(Tree) 是 n (n≥0) 个结点的有限集。若 n = 0,称
为空树;若 n > 0,则它满足如下两个条件:
(1) 有且仅有一个特定的称为根(Root) 的结点;
(2) 其余结点可分为 m (m≥0) 个互不相交的有限集 T1, T2,
T3, …, Tm,其中每一个集合本身又是一棵树,并称为
根的子树(SubTree)。
树的定义是一个递归的定义。
4
树的逻辑结构:树中任一结点都可以有零个或多个直接后继结点
但至多只能有一个直接前趋结点。
T3
T2
T1
基本术语:
结点的度:结点拥有的子树数。
度= 0
叶子
终端结点
度≠ 0
分支结点
非终端
结点
根结点以
外的分支
结点称为
内部结点
树的度:树内各结点的度的最大值。
双亲
孩子
兄弟
结点的祖先:从根到该结点所经分支上的所有结点。
结点的子孙:以某结点为根的子树中的任一结点。
第 1 层
第 2 层
第 3 层
第 4 层
堂兄弟
双亲在同一层的结点
树的深度:树中结点的最大层次。
有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。
无序树:树中结点的各子树无次序。
结点:数据元素+ 指向子树的分支
根结点:非空树中无前驱结点的结点
森林:是 m (m≥0) 棵互不相交的树的集合。
一棵树可以看成是一个特殊的森林。
把根结点删除树就变成了森林。
给森林中的各子树加上一个双亲结点,森林就变成了树。
树
森林
一定是
不一定是
E
F
G
H
I
A
B
C
D
J
K
L
M
5
定义:
图(Graph) 是一种复杂的非线性数据结构,由顶
点集合及顶点间的关系(也称弧或边)集合组成。可
以表示为: G=(V, {VR})  其中 V 是顶点的有穷非空集合; VR 是顶点之间关系
的有穷集合,也叫做弧或边集合。弧是顶点的有序对,
边是顶点的无序对。
图的定义和基本术语
6
图的意义
图是一种限制最少的数据结构。
更接近现实;
实际问题中很多数据关系都可以抽象成图,相关问题则可利用图的基本算法进行求解,很早就有专门研究图的是一门数学学科“图论”。
图论中著名算法:求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二分图最大匹配(指派问题)的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流量和最小割集算法等。其中一些算法在数据结构课程中已经学习过。
7
基本术语:
有向图
无向图
顶点:图中的数据元素。
v2
v1
v3
v4
G1
v2
v1
v3
v4
v5
G2
弧:若<v, w>∈VR,则<v, w> 表示从 v 到 w 的
一条弧,且称 v 为弧尾,称 w 为弧头, 此时的图称
为有向图。
G1 = (V1, {A1}) V1 = {v1, v2, v3, v4}
A1 = {< v1, v2>, < v1, v3>, < v3, v4>, < v4, v1>}
边:若<v, w>∈VR 必有<w, v>∈VR,则以无序
对(v, w) 代表这两个有序对,表示 v 和 w 之间的一条
边,此时的图称为无向图。
G2 = (V2, {E2}) V2 = {v1, v2, v3, v4, v5}
E2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5) , (v3, v4), (v3, v5)}
8
无向图中边的取值范围:0≤e≤n(n-1)/2。
(n 表示图中顶点数目, e 表示边的数目,且不
考虑顶点到自身的边)
完全图:有 n(n-1)/2 条边的无向图(即:无向图中每两个顶点间都存在一条边)称为完全图。
有向完全图:有 n(n-1) 条弧的有向图(即:有向
图中每两个顶点间都存在着方向相反的两条弧)称
为有向完全图。
v2
v1
v3
v4
v5