文档详情

第七章数据结构中的图.ppt

发布:2017-04-22约4.06千字共75页下载文档
文本预览下载声明
数据结构与应用;内容简介 ;教材目录;第1章 绪论 1.1 数据结构的产生和发展 1.2 数据结构研究的内容 1.3 基本概念和术语 1.4 算法 第2章 线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较 2.5 线性表的应用;第3章 栈和队列 3.1 栈 3.2 队列 3.3 栈的应用 第4章 串 4.1 串的逻辑结构 4.2 串的顺序存储结构 4.3 串的链式存储结构 4.4 串的应用 ;第5章 数组和广义表 5.1 数组 5.2 矩阵的压缩存储 5.3 广义表 5.4 多维数组的应用 ;第6章 树和二叉树 6.1 树的逻辑结构 6.2 树的顺序存储结构 6.3 二叉树的逻辑结构 6.4 二叉树的存储结构 6.5 线索二叉树 6.6 树、森林与二叉树的转换 6.7 树的应用;第7章 图 7.1 图的逻辑结构 7.2 图的存储结构 7.3 图的遍历 7.4 生成树和最小生成树 7.5 最短路径 7.6 DAG图及其应用 ;第8章 排序 8.1 概述 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内排序方法的比较和选择;第9章 查找 9.1 概述 9.2 线性表的查找 9.3 树表的查找 9.4 散列表的查找 附录 实验内容 ;第7章 图;7.1 图的逻辑结构;7.1.1图的定义;7.1.2 图的基本术语 ;若图G中的每条边都是没有方向的,则称G为无向图。 无向图中的边均是顶点的无序对,通常用圆括号表示。无序对(vi,vj)和(vj,vi)表示同一条边。 ;无向图G1,在该图中: V(G1)={v1,v2,v3,v4,v5} E(G1)={(v1,v2),(v1,v4),(v2,v3),(v2,v5) ,(v3,v4),(v3,v5) };有向图G2,该图的顶点集和边集分别为: V(G2)={v1,v2,v3,v4,v5} E(G2)={v1,v2,v1,v3,v3,v4,v4,v1};2. 稠密图和稀疏图 3. 边和顶点的关系 若(vi,vj)是一条无向边,则称顶点vi和vj互为邻接点(adjacent),或称vi和vj相邻接,并称(vi,vj)依附或关联(incident)于顶点vi和vj或称(vi,vj)与顶点vi和vj相关联。 若vi,vj是一条有向边,则称此边是顶点vi的一条出边,同时也是顶点vj的一条入边;称顶点vi邻接到(或邻接于)顶点vj,并称边vi,vj关联于vi和vj,或称vi,vj与顶点vi和vj相关联。 ;4. 顶点的度 ;5. 子图 ;6. 路径 ;7. 有根图和图的根 8. 无向图的连通图和连通分量 9. 有向图的强连通图和强连通分量 10. 网络 ;7.1.3 图的基本操作 ; 插入顶点:InsertVex(v) 在图中插入顶点v。 删除顶点:DeleteVex(v) 删除图中顶点v。 插入边或弧:Insert(v,w) 在图中插入一条边(v,w)或弧v,w,如是无向图,还应增加对称边(w, v)。 删除边或弧:Delete(v,w);7.2 图的存储结构 ;对于无向图,若从顶点vi到vj有一条无向边(vi,vj),则a[i][j]=1,a[j][i]=1;否则a[i][j]=0,a[j][i]=0,故无向图的邻接矩阵是一个对称矩阵。对于有向图,若从顶点vi到vj有一条有向边vi,v j,则a[i][j]=1;否则a[i][j]=0。 ;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.;基于邻接矩阵存储结构的图的类模板定义cx7_1.h ;邻接矩阵的基本操作及其实现:;7.2.2 邻接表 ;为每个顶点vi的邻接表设置一个头结点,头结点中包含两个域,其中一个是顶点域vertex,用来存放顶点vi的数据信息;另一个是指针域firstedge,它指向vi的邻接表的开始结点,相当于vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表,将所有头结点顺序存储在一个一维数组中,称为顶点表,将其中的头结点称为顶点表结点。这样就构成了图的邻接表表示。 ;Evaluation only. Created with Aspose.Slides f
显示全部
相似文档