数据结构图结构.ppt
数据结构课程的内容数据结构课程的内容多对多多对多（m:n)特点：特点：非线性结构，是研究数据元素之非线性结构，是研究数据元素之间的多对多的关系。在这种结构中，任间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元之间的关系可以是任意的，图中任意元素之间都可能相关。素之间都可能相关。 图的应用极为广泛，已渗入到诸如语图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。算机科学以及数学的其它分支。7.1 7.1 基本术语基本术语7.2 7.2 存储结构存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的其他运算图的其他运算7.5 7.5 图的应用图的应用图：图：记为记为 G( V, E ) 其中：其中：V 是是G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E 是是G的边的边集合，是有穷集。集合，是有穷集。问：问：当当E(G)E(G)为空时，图为空时，图G G存在否？存在否？答：答：还存在！但此时图还存在！但此时图G G只有顶点而没有边。只有顶点而没有边。有向图：有向图：无向图：无向图：完全图：完全图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；图图G G任意两个顶点都有一条边相连接；任意两个顶点都有一条边相连接；V=vertex E=edge证明：例：例：判断下列判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向G1G1的顶点集合为的顶点集合为V(G1)V(G1)=0,1,2,3=0,1,2,3边集合为边集合为E(G1)E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全图完全图完全图完全图稀疏图：稠密图： 设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。子 图：边较少的图。通常边数边较少的图。通常边数n2边很多的图。无向图中，边数接近边很多的图。无向图中，边数接近有向图中，边数接近有向图中，边数接近带权图：带权图：即边上带权的图。其中即边上带权的图。其中权权是指每条边可以标上是指每条边可以标上具有某种含义的数值（即与边相关的数）。具有某种含义的数值（即与边相关的数）。连通图：连通图：带权图带权图强连通图：强连通图：网网 络：络：有两类图形有两类图形不在本章讨不在本章讨论之列：论之列：邻接点：有向边有向边(u, v)称为弧，边的始点称为弧，边的始点u叫叫弧尾弧尾，终点，终点v叫叫弧头弧头 顶点顶点v的度的度是与它相关联的边的条数。记作是与它相关联的边的条数。记作TD(v)。 在在有向图有向图中中, 顶点的度等于该顶点的顶点的度等于该顶点的入度入度与与出度出度之和。之和。 顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度的出度是以是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。若若 (u, v) 是是 E(G) 中的一条边，则称中的一条边，则称 u 与与 v 互为互为邻接顶点邻接顶点弧头和尾：度、入度和出度：问：问：当有向图中仅当有向图中仅1 1个顶点的入度为个顶点的入度为0,0,其余顶点的入其余顶点的入度均为度均为1 1，此时是何形状？，此时是何形状？答：答：是树！而且是一棵有向树！是树！而且是一棵有向树！生成树：生成树：生成森林：生成森林：简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为则称这样的路径为回路或环回路或环。路径：路径长度：ADT Graph 数据对象数据对象V V：v v是具有相同特性的数据元素的集合，称为顶点集。是具有相同特性的数据元素的集合，称为顶点集。数据关系数据关系R R：R=VRR=VR；VR=VR= |v,wV |v,wV 且且 P(v,w)P(v,w), , 表示从表示从v v到到w w的弧，的弧， 谓词谓词P(v,w)P(v,w)定义了弧定义了弧的意义或信息的意义或信息 基本操作基本操作P P： CreatGraph ( &G, V,VR); 初始条件：初始条件：V V是图的顶点是图的顶点集集，VRVR是图中弧的集合。是图中弧的集合。 操作结果：操作结果：按按V V和和VRVR的定义构造图的定义构造图G G。 InsertVex ( &G, v); 初始条件：初始条件：图图G G存在，存在，v v和图中顶点有相同特征。和图中顶点有相同特征。 操作结果：操作结果：在图在图G G中添加新顶点。中添加新顶点。 （参见（参见P156-257P156-257） 注意：注意：V V 的的大小写含义大小写含义不同！不同！图的特点：非线性结构（图的特点：非线性结构（m :n m :n ） 邻接表邻接表 邻接多重表邻接多重表 十字链表十字链表设计为邻接矩设计为邻接矩阵阵链式存储结构：链式存储结构：顺序存储结构：顺序存储结构： 无！无！（多个顶点，无序可言）（多个顶点，无序可言）但可但可用用数组数组描述元素间关系。描述元素间关系。可用多重链表可用多重链表重点介绍：重点介绍： , ),( , , .否否则则或或者者如如果果01AEjiEjijiEdgev1v2v3v5v4v4AA.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0例例2 ：有向图的邻接矩阵有向图的邻接矩阵有向图的邻接矩阵有向图的邻接矩阵可能是不对称可能是不对称的。的。顶点的出度顶点的出度=第第i行元素之和行元素之和，OD( Vi )= A.Edge i j 顶点的入度顶点的入度=第第i列元素之和列元素之和。ID( Vi )= A.Edge j i 顶点的度顶点的度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和, , 即：即：TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为尾的弧为尾的弧( (即出度边）；即出度边）； 第第i i列含义：以结点列含义：以结点v vi i为头的弧为头的弧( (即入度边）。即入度边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 容易实现图的操作，如：求某顶点的度、判断容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。顶点之间是否有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要n n* *n n个单元存储边个单元存储边( (弧弧););空间效率空间效率为为O(nO(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。特别讨论特别讨论 ：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义为： A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：邻接矩阵： N.Edge =( v1 v2 v3 v4 v5 v6 )邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点：顶点表：顶点表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 注：注：用两个数组分别存储顶点表和邻接矩阵用两个数组分别存储顶点表和邻接矩阵#define INFINITY INT_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /假设的最大顶点数假设的最大顶点数Typedef enum DG, DN, AG,AN GraphKind; /有向有向/ /无向图，有向无向图，有向/ /无向网无向网Typedef struct ArcCell /弧（边）弧（边）结点的定义结点的定义 VRType adj; /顶点间关系，无权图取顶点间关系，无权图取1 1或或0 0；有权图取权值类型；有权图取权值类型 InfoType *info; /该弧相关信息的指针该弧相关信息的指针ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;Typedef struct /图的定义图的定义VertexType vexs MAX_VERTEX_NUM ; /顶点表，用一维向量即可顶点表，用一维向量即可AdjMatrix arcs; /邻接矩阵邻接矩阵Int Vernum, arcnum; /顶点总数，弧（边）总数顶点总数，弧（边）总数GraphKind kind; /图的种类标志图的种类标志Mgraph; 图的邻接矩阵存储表示图的邻接矩阵存储表示（参见教材（参见教材P161）对于对于n n个顶点的图或网，空间效率个顶点的图或网，空间效率=O(n=O(n2 2) )Status CreateUDN(Mgraph &G) /无向网的构造，用邻接矩阵表示无向网的构造，用邻接矩阵表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /输入总顶点数，总弧数和信息输入总顶点数，总弧数和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );/);/输入顶点值，存入一维向量中输入顶点值，存入一维向量中for(i=0; iG.vexnum; +i) /对邻接矩阵对邻接矩阵n n* *n n个单元初始化，个单元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL; for(k=0;kG.arcnum;+k) /给邻接矩阵有关单元赋初值给邻接矩阵有关单元赋初值( (循环次数弧数循环次数弧数 scanf(&v1, &v2, &w); /输入弧的两顶点以及对应权值输入弧的两顶点以及对应权值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到两顶点在矩阵中的位置找到两顶点在矩阵中的位置(n(n次次? ? G.arcsij.adj=w; /输入对应权值输入对应权值 If(IncInfo) Input(*G.arcsij.info); /如果弧有信息则填入如果弧有信息则填入 G.arcsji = G.arcs i j； /无向网是对称矩阵无向网是对称矩阵 return OK; / CreateUDN/ CreateUDN 例：例：用邻接矩阵用邻接矩阵生成无向网生成无向网的算法的算法（参见教材（参见教材P162）对于对于n n个顶点个顶点e e条弧的网，条弧的网，建网时间效率建网时间效率 = O(n= O(n2 2+n+e+n+e* *n)n)adjvex nextarcinfodatafirstarc邻接点域，邻接点域，表表示示v vi i一个邻接一个邻接点的位置点的位置链域，链域，指向指向vivi下一个边下一个
