《图搜索基础》.ppt

该【《图搜索基础》 】是由【相惜】上传分享，文档一共【55】页，该文档可以免费在线阅读，需要了解更多关于【《图搜索基础》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图搜索根底1精选课件树的定义和根本术语定义:树(Tree)是n(n≥0)个结点的有限集。假设n=0,称为空树;假设n>0,那么它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点;(2)其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)。树的定义是一个递归的定义。2精选课件树的逻辑结构:树中任一结点都可以有零个或多个直接后继结点但至多只能有一个直接前趋结点。T3T2T1根本术语:结点的度:结点拥有的子树数。度=0叶子终端结点度≠0分支结点非终端结点根结点以外的分支结点称为内部结点树的度:树内各结点的度的最大值。双亲孩子兄弟结点的祖先:从根到该结点所经分支上的所有结点。结点的子孙:以某结点为根的子树中的任一结点。第1层第2层第3层第4层堂兄弟双亲在同一层的结点树的深度:树中结点的最大层次。有序树:树中结点的各子树从左至右有次序(最左边的为第一个孩子)。无序树:树中结点的各子树无次序。结点:数据元素+指向子树的分支森林:是m(m≥0)棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。把根结点删除树就变成了森林。给森林中的各子树加上一个双亲结点,森林就变成了树。树森林一定是不一定是EFGHIABCDJKLM3精选课件定义:图(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如果顶点vi的度为TD(vi),那么一个有n个顶点e条边(弧)的图,满足如下关系:终端顶点:有向图中把出度为0的顶点称为终端顶点。5精选课件路径:从顶点v到v′的路径是一个顶点序列(v=vi,0,vi,1,…,vi,m=v′),满足(vi,j-1,vi,j)?VR或<vi,j-1,vi,j>?VR(1?j?m)。对于有向图,路径也是有向的。v2v1v3v4v5v2v1v3v4路径长度:路径上边或弧的数目。回路(环):第一个顶点和最后一个顶点相同的路径。简单路径:序列中顶点(两端点除外)不重复出现的路径。简单回路(简单环):前后两端点相同的简单路径。连通:无向图中从顶点v到v′有路径,那么说v和v′是连通的。连通图:无向图中任意两个顶点都是连通的。v2v1v3v4v56精选课件连通分量:无向图的极大连通子图;任何连通图的连通分量只有一个,即其本身;非连通图有多个连通分量(非连通图的每一个连通局部)。v2v1v3v4v5v2v1v3v4v5强连通图:有向图G中,假设对于V(G)中任意两个不同的顶点vi和vj,都存在从vi到vj以及从vj到vi的路径,那么称G是强连通图。v2v1v3v4强连通分量:有向图的极大强连通子图;任何强连通图的强连通分量只有一个,即其本身;非强连通图有多个强连通分量。v2v1v3v4v2v1v3v47精选课件对于一个具有n个顶点的图,可用两个数组存储。其中一个一维数组存储数据元素(顶点)的信息,另一个二维数组(图的邻接矩阵)存储数据元素之间的关系(边或弧)信息。邻接矩阵:设G=(V,{VR})是具有n个顶点的图,顶点的顺序依次为{v1,v2,…,vn},那么G的邻接矩阵是具有如下性质的n阶方阵:图的存储结构之数组表示法(邻接矩阵表示法)8精选课件v2v1v3v4G1v2v1v3v4v5G2v1v2v3v4v1v2v3v4v5v1v2v3v4v1v2v3v4v5特点:无向图的邻接矩阵对称,可压缩存储;有n个顶点的无向图需存储空间为n(n-1)/2。有向图邻接矩阵不一定对称;有n个顶点的有向图需存储空间为n2,空间复杂度O(n2),用于稀疏图时空间浪费严重。无向图中顶点vi的度TD(vi)是邻接矩阵中第i行1的个数。有向图中顶点vi的出度是邻接矩阵中第i行1的个数。顶点vi的入度是邻接矩阵中第i列1的个数。9精选课件网的邻接矩阵可定义为:v2v1v3v4v5v65489755613v1v2v3v4v5v6v1v2v3v4v5v610精选课件