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

数据结构与应用;内容简介 ;教材目录;第1章 绪论 1.1 数据结构的产生和发展 1.2 数据结构研究的内容 1.3 基本概念和术语 1.4 算法 第2章　线性表 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较 2.5 线性表的应用;第３章　栈和队列 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