《数据结构图和广义表》由会员分享，可在线阅读，更多相关《数据结构图和广义表（57页珍藏版）》请在金锄头文库上搜索。
1、数据结构的内容1图的特点 顶点的前驱和后继个数无限制 图的应用顶点之间的关系是任意的 图中任意两个顶点之间都可能相关 图（Graph）是一种非线性结构。 语 言 学逻 辑 学 物 理 化 学 电信工程 数 学 计算机科学计算机科学 多对多多对多 北京 西安 南京 杭州 开封 洛阳 27.1 基本术语7.2 存储结构7.3 图的遍历7.4 连通网的最小生成树7.5 单源最短路径7.6 拓朴排序7.7 关键路径7.8 广义表第第7 7章章 图和广义表图和广义表37.1 7.1 图的基本图的基本 术语术语 图：记为 G( V, E ) 其中：V 是G的顶点集合，是有穷非空集 ；E 是G的边集合，是有
2、穷集。问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。有向图： 无向图： 完全图：图G中的每条边都是有方向的； 图G中的每条边都是无方向的； 图G任意两个顶点都有一条边相连接；vv若若 n n 个顶点的无向图有个顶点的无向图有 n n( (n n-1)/2 -1)/2 条边条边, , 称为称为无向完全图无向完全图 vv若若 n n 个顶点的有向图有个顶点的有向图有n n( (n-n-1) 1) 条边条边, , 称为称为有向完全图有向完全图V=vertex E=edge4例：判断下列4种图形各属什么类型？无向图 无向图(树)有向图有向图n n( (n n-1)/2 -
3、1)/2 条边条边n n( (n n-1) -1) 条边条边完全图完全图5设有两个图 G(V, E) 和 G(V, E)。若 V V 且 E E, 则称 图G 是 图G 的子图。子 图：带 权 图 ：即边上带权的图。其中权是指每条边可以标上 具有某种含义的数值（即与边相关的数）。带权图（带权的有向图与无向图） 网 络：6顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。问：当有向图中仅1个顶点的入度为0,其余顶
4、点的 入度均为1，此时是何形状？答：是树！而且是一棵有向树！度 入 度 出 度7简单 路径 ：路径上各顶点 v1,v2,.,vm 均不互相重复。回 路：例：若路径上第一个顶点 v1 与最后一个顶点vm 重合 ，则称这样的路径为回路或环。路径：在图在图 GG( (V V, , E E) ) 中中, , 若从顶点若从顶点 v vi i 出发出发, , 沿一些边经过一些顶沿一些边经过一些顶 点点 v vp p1 1, , v vp p2 2, , , v vpmpm，到达顶点到达顶点v vj j。则称顶点序列则称顶点序列 ( ( v vi i v vp p1 1 v vp p2 2 . . v vp
5、mpm v vj j ) ) 为从顶点为从顶点v vi i 到顶点到顶点 v vj j 的的路径路径。它经过的边。它经过的边( (v vi i, , v vp p1 1) )、( (v vp p1 1, , v vp p2 2) )、. .、( (v vpmpm, , v vj j) )应当是属于应当是属于E E的边。的边。路径长度：非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数边的条数； 带权图的路径长度是指路径上带权图的路径长度是指路径上各边的权之和。各边的权之和。8在在无向无向图中图中, , 若从顶点若从顶点v v1 1到顶点到顶点v v2 2有路径有路径, , 则
6、称顶点则称顶点v v1 1与与v v2 2是是连通连通的。如果图中任意一对顶点都是连通的的。如果图中任意一对顶点都是连通的, , 则称此图是则称此图是连通图连通图。 非连通图的极大连通子图非连通图的极大连通子图叫做叫做连通分量连通分量。在在有向有向图中图中, , 若对于每一对顶点若对于每一对顶点v vi i和和v vj j, , 都存在一条从都存在一条从v vi i到到v vj j和和从从v vj j到到v vi i的路径的路径, , 则称此图是则称此图是强连通图强连通图。非强连通图的极大强连通子图非强连通图的极大强连通子图叫做叫做强连通分量强连通分量。强连通 图：连 通 图 ：生成树：是一个
7、是一个极小连通子图极小连通子图，它含有图中全部顶点，但只有，它含有图中全部顶点，但只有 n n-1-1条边条边。 vv如果在生成树上添加如果在生成树上添加1 1条边，必定构成一个环。条边，必定构成一个环。 vv若图中有若图中有n n个顶点，却少于个顶点，却少于n n-1-1条边，必为非连通图。条边，必为非连通图。生成森 林：由若干棵生成树组成，含全部顶点，但构成这些树由若干棵生成树组成，含全部顶点，但构成这些树 的边是最少的。的边是最少的。97.2 7.2 图的存储图的存储 结构结构 图的特点：非线性结构（m :n ） 邻接表 邻接多重表 十字链表设计为邻接矩阵链式存储结构：顺序存储结构： 无
8、！（多个顶点，无序可言） 但可用数组数组描述元素间关系。可用多重链表重点介绍：邻接矩阵邻接矩阵( (数组数组) )表示法表示法 邻接表邻接表( (链式链式) )表示法表示法107.2.1 7.2.1 邻接矩阵（数组）表邻接矩阵（数组）表 示法示法vv一个有一个有 n n 个顶点的图，可用个顶点的图，可用两个数组两个数组存储。其中一个存储。其中一个 一维一维 数组存储数据元素数组存储数据元素（顶点）（顶点）的信息，另一个的信息，另一个二维数组二维数组（邻接（邻接 矩阵）存储数据元素之间的矩阵）存储数据元素之间的关系关系（边或弧）的信息。（边或弧）的信息。 vv设图设图 G = (G = (V V
9、, , E E) ) 有有 n n 个顶点，则图的邻接矩阵是一个二维数个顶点，则图的邻接矩阵是一个二维数 组组 A A n n n n ，定义为：定义为：v1v2v3v5v4v4G例例1 1：邻接矩阵： A =（ v1 v2 v3 v4 v5 ） v1 v2 v3 v4 v50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0分析分析1 1：无向图的邻接矩阵是无向图的邻接矩阵是对称对称的；的； 分析分析2 2：顶点顶点i i 的的度度第第 i i 行行 ( (列列) ) 中中1 1 的个数的个数； 特别：特别：完全图完全图的邻接矩阵中，对角元素为的
10、邻接矩阵中，对角元素为0 0，其余全，其余全1 1。0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0顶点表：11例2 ：有向图的邻接 矩阵分析分析1 1：有向图的邻接矩阵可能是不对称的。 分析分析2 2：顶点的出度=第i行元素之和，OD( Vi )= A i j 顶点的入度=第i列元素之和。ID( Vi )= A j i 顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4G G邻接矩阵
11、： A=( v1 v2 v3 v4 ) v1 v2 v3 v40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表： 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 12容易实现图的操作，如：求某顶点的度、判断 顶点之间是否有边（弧）、顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率 为O(n2)。 对稀疏图而言尤其浪费空间。特别讨论 ： 网（即有权图）的邻接矩阵定义为
12、： A i j =Wij 或（vi, vj）VR 无边（弧）v1v2v3v4Nv5v65 48 9755613以有向网为例：邻接矩阵： N =( v1 v2 v3 v4 v5 v6 )邻接矩阵法优点：邻接矩阵法缺点：顶点表：5 7 4 8 95 65 3 1 5 7 4 8 9 5 6 5 3 1 13数据结构 第七章 图和广义表韶关学院数信学院图的数组（邻接矩阵）存储表示： #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图,
13、有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph; 数据结构 第七章 图和广义表韶关学院数信学院7.2.2 图的邻接表存储表示法（ 链式存储 ） 头结点 data firstarc 表结点 adjvex nextarc info v2 v1 v3 v4 v5 G2 v1 v3 v4 v2 v5 0 1 2 3 4 3 1 4 2 0 4 3 1 2 0 2 1 链域链域，指示下一条边或弧。 特点： 若无向图中有 n
