第十八讲图-导论.ppt

多关键字全文检索大作业分析讲评 2009/05/05 作业要求： 要求; ?按向量空间模型实现诗歌的检索，系统可以支持对任意指定的一组词（a bag of word），检索出最符合条件的诗歌（前十首，按相似度降序）。能够实现词（出现）匹配计算并完成系统并有较详细注释的，可以获得+2分。 考虑词频以及tf,idf并附有较详细报告与注释的可获得+3分。 能够综合考虑位置及其他信息，支持简单逻辑表达式进行检索运算的，并完成详细的设计报告者，可获得+4到5分。 提交情况 叶永鑫 骆文珊 张国晟 张潇云 唐紫薇 徐腾 陈刚 饶驰通 题目理解与分析： 待处理数据： 行号 -1 0 1,2,3,4,… 起始位置 词条 程序实现：（张国晟 ） 申请空间，读入数据： 运行初始化： Split: Dictionary+Postings 每出现新词条， 添加词典 每出现新词条， 添加postings 词条文档号重复， postings + 1 多关键码排序 词条权重： 图 — 基本概念与抽象数据类型 2009/05/5 主要内容 图的基本概念 图的相邻矩阵及邻接表的表示方法 图抽象数据类型 图的周游方法 求图的最小生成树（林） 图的基本概念 反映连通关系 反映连通属性 图的形式化定义 图由顶点（vertex）集合和边（edge）集合E组成， 记为G=(V，E)。 每条边就是一个顶点的偶对，所以E也就是V上的一个二元关系。 例如： V = { a,b,c,d}; E = {a,b, a,d, c,d, d,a} 有向图无向图 ‘度’ 的定义 关联：由一个顶点发出的边构成与该定点的一个关联。 顶点的度：与该顶点关联的所有的边或弧的数目。 (邻接点的个数定义为顶点的度。) 入度：（仅对有向图）以该顶点为头的弧数。 路径 无向图中的顶点序列v1,v2,… ,vk,若(vi,vi+1)?E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路； 有向图中的顶点序列v1,v2,… ,vk, 若vi,vi+1?E ( i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路； 路径上边或弧的数目称为该路径的路径长度。 连通图 在无（有）向图G =( V, E )中，若对任何两个不同顶点v、u都存在从v到u的路径，则称G是连通图。 图的其他一些相关概念 子图： 对于 G=(V，E) ， G’ =(V’，E’) 如果有 V’ in V E’ in E， 则称G’为G的子图。 带权图（网络）： 每条边加上权值信息。带权图也常被称为‘加权图’。带权图中的路径通常定义为路径之上所有边的权值总和。 图的存储结构1 —— 邻接矩阵表示法 设图 G = (V,E) G = (V,E)是一个有 是一个有 n个顶点的图 , 图的邻接矩阵是一个二维数组 edge[n][n]，定义： vexs1[]={‘a’, ‘b’, ‘c’, ‘d’} ; vexs2[]={v0,v1,v2,v3,v4} 邻接矩阵表示法的特点 (1)无向图的关系矩阵一定是一对称矩阵。(2)无向图的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。(3)?有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数就是第i个顶点的入度ID(vi)。(4) 从图的邻接矩阵表示，很容易确定图中任意两个顶点之间是否有边相连。添加或删除边也很方便。 带权图的邻接矩阵表示 如果G是带权的图，wij是边(vi,vj)或 vi,vj的权，则其关系矩阵定义为∶ 邻接矩阵表示法结构定义 typedef char VexType; typedef float AdjType; typedef struct { int n; /* 图的顶点个数 */ VexType *vexs; /* 顶点信息 */ AdjType *arcs[ ]; /* 边信息，二维数组 */ }GraphMatrix; 邻接表表示法—— 对图中每个顶点建立一个单链表， 第i个单链表中的结点表示依附于该顶点Vi的边（或弧） 矩阵两种存储表示的空间开销比较 设图G有n个顶点，e条边. 图的邻接矩阵表示的空间代价为O(n2)； 若图G是无向图， 则图的邻接表表示的空间代价为O(n+2e)；