2019年图搜索基础ppt课件.ppt

《2019年图搜索基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图搜索基础1树的定义和基本术语定义：树(Tree)是n(n≥0)个结点的有限集。若n=0，称为空树；若n>0，则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。树的定义是一个递归的定义。2树的逻辑结构：树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。T3T2T1基本术语：结点的度：结点拥有的子树数。度=0叶子终端结点度≠0分支结点非终端结点根结点以外的分支结点称

2、为内部结点树的度：树内各结点的度的最大值。双亲孩子兄弟结点的祖先：从根到该结点所经分支上的所有结点。结点的子孙：以某结点为根的子树中的任一结点。第1层第2层第3层第4层堂兄弟双亲在同一层的结点树的深度：树中结点的最大层次。有序树：树中结点的各子树从左至右有次序(最左边的为第一个孩子)。无序树：树中结点的各子树无次序。结点：数据元素+指向子树的分支森林：是m(m≥0)棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点，森林就变成了树。树森林一定是不一定是EFGHIABCDJKLM3定义

3、：图(Graph)是一种复杂的非线性数据结构，由顶点集合及顶点间的关系(也称弧或边)集合组成。可以表示为：G＝(V,{VR})其中V是顶点的有穷非空集合；VR是顶点之间关系的有穷集合，也叫做弧或边集合。弧是顶点的有序对，边是顶点的无序对。图的定义和基本术语4度：无向图中顶点v的度是和v相关联的边的数目，记为TD(v)。v2v1v3v4v5入度：有向图中以顶点v为终点的弧数目称为v的入度，记ID(v)。出度：有向图中以顶点v为起点的弧数目称为v的出度，记OD(v)。度：入度和出度之和，即：TD(v)=ID(v)+OD(v)。v2v1v3v4如果顶

4、点vi的度为TD(vi)，则一个有n个顶点e条边(弧)的图，满足如下关系：终端顶点：有向图中把出度为0的顶点称为终端顶点。5路径：从顶点v到v´的路径是一个顶点序列(v=vi,0,vi,1,…,vi,m=v´)，满足(vi,j-1,vi,j)VR或VR(1jm)。对于有向图，路径也是有向的。v2v1v3v4v5v2v1v3v4路径长度：路径上边或弧的数目。回路(环)：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点(两端点除外)不重复出现的路径。简单回路(简单环)：前后两端点相同的简单路径。连通：无向图中

5、从顶点v到v´有路径，则说v和v´是连通的。连通图：无向图中任意两个顶点都是连通的。v2v1v3v4v56连通分量：无向图的极大连通子图；任何连通图的连通分量只有一个，即其本身；非连通图有多个连通分量(非连通图的每一个连通部分)。v2v1v3v4v5v2v1v3v4v5强连通图：有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。v2v1v3v4强连通分量：有向图的极大强连通子图；任何强连通图的强连通分量只有一个，即其本身；非强连通图有多个强连通分量。v2v1v3v4v2v1v3v

6、47对于一个具有n个顶点的图，可用两个数组存储。其中一个一维数组存储数据元素(顶点)的信息，另一个二维数组(图的邻接矩阵)存储数据元素之间的关系(边或弧)信息。邻接矩阵：设G=(V,{VR})是具有n个顶点的图，顶点的顺序依次为{v1,v2,…,vn}，则G的邻接矩阵是具有如下性质的n阶方阵：图的存储结构之数组表示法(邻接矩阵表示法)8v2v1v3v4G1v2v1v3v4v5G2v1v2v3v4v1v2v3v4v5v1v2v3v4v1v2v3v4v5特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n-1)/2。有向图邻接

7、矩阵不一定对称；有n个顶点的有向图需存储空间为n²，空间复杂度O(n2)，用于稀疏图时空间浪费严重。无向图中顶点vi的度TD(vi)是邻接矩阵中第i行1的个数。有向图中顶点vi的出度是邻接矩阵中第i行1的个数。顶点vi的入度是邻接矩阵中第i列1的个数。9网的邻接矩阵可定义为：v2v1v3v4v5v65489755613v1v2v3v4v5v6v1v2v3v4v5v610顶点表结点datafirstarc边表结点adjvexnextarcinfov2v1v3v4v5G2v1v3v4v2v5012343^142^043^12^02^1链域，指示下一条

8、边或弧。特点：若无向图中有n个顶点、e条边，则其邻接表需n个顶点表结点和2e个边表结点。适宜存储稀疏图。无向图中顶点vi的度为第i个单链