图搜索基础.ppt

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