第七章数据结构中的图.ppt
文本预览下载声明
数据结构与应用;内容简介 ;教材目录;第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
显示全部