[工学]chapter12图-定义-存储

数据结构与算法,2010年秋季,Chapter12 图,中国地质大学信息工程学院,2018/1/12,12.1 图的基本概念和基本术语12.2 图的应用示例12.4 抽象数据类型Graph和Diagraph12.5-6 无向图、有向图及网络的描述12.7 图的类定义12.8 图的遍历12.10 图的搜索算法12.11 图的应用,内容提要,12.1 图的基本概念-图的定义,图是由数据元素的集合V(G)及数据元素间的关系集合E(G)组成的一种数据结构：,Graph（V，E）,其中： V(G)是图中顶点（vertex）的非空有限集合；,E(G)是图中边（edge）的集合。,图中至少有一个顶点，可以无边；图中两顶点之间有关系就有边，没有关系就无边。,在一个图中，如果任意两顶点之间构成了无序偶对（x,y），即顶点之间的连线没有方向性，称该图为无向图。,在无向图中，顶点之间的连线称为边（edge），用圆括号表示，（x,y）与（y,x）是同一条边。,图的基本术语-无向图,在一个图中，如果任意两顶点之间构成了有序偶对，即顶点之间的连线有方向性，称该图为有向图。,在有向图中，顶点之间的连线称为弧（arc），用尖括号表示，与不相同。,弧,弧尾（始点）,弧头（终点）,弧,弧头（终点）,弧尾（始点）, ,图的基本术语-有向图,例,V(G2)=1,2,3E(G2)=,G2,V(G1)=1,2,3,4E(G1)=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),G1,G3,树是图的特例，“树图”,【注意】本章不予讨论的图,（a）图中不能有从自身到自身的边；（b）与两个特定顶点相关联的边不能多于一条。,完全无向图和完全有向图都称为完全图。,在一个无向图中，如果任意两顶点之间都有一条边直接相连接，则称该图为完全无向图，在一个具有n个顶点的完全无向图中，一定存在n(n-1)/2条边。,在一个有向图中，如果任意两顶点之间都有方向相反的两条弧直接相连接，则称该图为完全有向图，在一个具有n个顶点的完全有向图中，一定存在n(n-1) 条弧。,完全图（complete graph）,在一个图中，边或弧可以附带一定的数据信息，称之为权。,权可以表示 从一个顶点到另一个顶点的距离 花费的代价 所需的时间 次数等。,带权的图称为网络或网。,图的基本术语-网络（network）,例: 铺设煤气管道,(a) 居民区示意图,邻接顶点（adjacent vertex）,如果 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻接顶点。,G1,G2,设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,例,1,G2的子图,G2,不是G2的子图,V(G2)=1,2,3E(G2)=,图的基本术语-子图（subgraph）,（1）无向图中的度（无入度、出度）,一个顶点v的度是与它相关联的边的条数。记作TD(v),（2）有向图中的度、入度、出度,顶点 v 的入度是以 v 为弧头（终点）的弧（有向边）的条数, 记作 ID(v);,顶点 v 的出度是以 v 为弧尾（始点）的弧（有向边）的条数, 记作 OD(v)。,顶点 v 的度等于该顶点入度与出度之和，记作TD(v)。,ID(2)=1,OD(2)=2,TD(2)=1+2=3,图的基本术语-度、入度、出度,无向图G（V,E）中，若存在一个从顶点Vp到顶点Vq的顶点序列（Vp,Vi1,Vi2,Vin,Vq），且满足（Vp,Vi1）， （Vi1,Vi2）， （Vin,Vq）E(G)， 则顶点序列（Vp,Vi1,Vi2,Vin,Vq）称为顶点Vp到顶点Vq的一条路径。,有向图G（V,E）中，若存在一个从顶点Vp到顶点Vq的顶点序列，且满足， ， E(G)， 则顶点序列称为顶点Vp到顶点Vq的一条路径。,图的基本术语-路径,对于不带权的图，Vp到Vq的路径上所具有的边（或弧）的数目，称为该路径的路径长度。 对于带权图，路径长度是指路径上各边的权之和。,例,（V1, V2, V4, V3）是V1到V3的一条路径，路径长度为3。,是V1到V3的一条路径，路径长度为2。,2,7,10,若为带权有向图，则该路径长度为2+10=12。,图的基本术语-路径长度,若在构成路径的顶点序列中所有的顶点都没有重复出现, 则称这样的路径为简单路径。,第一个顶点和最后一个顶点相同的路径，称为回路或环。,第一个顶点和最后一个顶点相同的简单路径，称为简单回路。（或：除第一个顶点和最后一个顶点外，其余顶点均没有重复出现的回路称为简单回路。）,例,（V1, V2, V4, V3）是一条简单路径；,（V1, V2, V4, V3 , V2 , V1 ）是一个回路，但不是简单回路；,（V1, V2, V4, V3 , V1 ）是一个简单回路。,图的基本术语-简单路径与回路,非连通图的极大连通子图叫做连通分量。,在无向图中, 若从顶点vi到顶点vj有路径， 则称顶点vi与vj是连通的。,如果图G中任意一对顶点都是连通的， 也就是说，图G中任意两个顶点之间都有路径，则称G为连通图，否则G为非连通图。,例,非连通图,连通图,图的基本术语-连通图与连通分量,若图G中，任意两顶点都是强连通的，则称有向图G是强连通图。,非强连通图的极大强连通子图叫做强连通分量。,在有向图中， 如果任意两个顶点vi，vj之间，从vi到vj有一条有向路径，从vj到vi也有一条有向路径，则称顶点vi和vj是强连通的。,例,3,非强连通图,强连通分量,图的基本术语-强连通图与强连通分量,非（强）连通图的极大（强）连通子图叫做（强）连通分量。,极大（强）连通子图：将所有能连通起来的顶点以及依附于它们的边都放到它的子图中。,一般情况下，非（强）连通图才求（强）连通分量。对于（强）连通图的（强）连通分量就是它本身。,此有向图是一个强连通图，所以其强连通分量就是它自身。,极小（强）连通子图：既能连通，又没有回路。,图的基本术语-（强）连通分量,一个连通图G的生成树是图G的一个极小连通子图。它含有图G的全部n个顶点，但仅有足以构成一棵树的n-1条边。,一棵有n个顶点的生成树有且仅有n-1条边。,连通图的生成树不是唯一的。,例,图的基本术语-连通图的生成树,若一个图有n个顶点和小于n-1条边，则是非连通图； 若一个图有n个顶点和多于n-1条边，则一定有环，但有n-1条边的图不一定是生成树。,12.2 图的应用示例,12.4 无向图的抽象数据类型,抽象数据类型Graph 实例 顶点集合V和边集合E操作Create (n)：创建一个具有n 个顶点、没有边的无向图Exist(i, j)：如果存在边（i, j）则返回true，否则返回falseEdges( )：返回图中边的数目Vertices ( )：返回图中顶点的数目Add(i, j)：向图中添加边（i, j）Delete(i, j)：删除边（ i, j）Degree(i)：返回顶点i 的度InDegree(i)：返回顶点i 的入度OutDegree(i)：返回顶点i 的出度,抽象数据类型Digraph 实例 顶点集合V和边集合E操作Create(n)：创建一个具有n个顶点、没有边的有向图Exist(i, j)：如果存在边（i, j）则返回true，否则返回falseEdges( )：返回图中边的数目Vertices( )：返回图中顶点的数目Add(i, j)：向图中添加边（i, j）Delete(i, j)：删除边（i, j）Degree(i)：返回顶点i 的度InDegree(i)：返回顶点i的入度OutDegree (i)：返回顶点i的出度,12.4 有向图的抽象数据类型,12.5 无向图、有向图和网的描述,邻接矩阵邻接压缩表邻接链表（邻接表）邻接多重表,12.5.1 邻接矩阵（Adjacency Matrix）,图G（V,E）有n个顶点，假设V=1,2,n，则表示G中各顶点相邻关系的矩阵为一个nn的方阵A，A的元素为：,A(i,j) =,1，若（ i,j ）E或 E,0，其它,例1：无向图G1及其邻接矩阵,B,无向图的邻接矩阵特征,是一个对称矩阵； 可以进行压缩存储，存储量为n(n+1)/2；（或n(n-1)/2 ） 顶点Vi的度为di = 第i行（列）非零元素个数 =,G1,A,顶点表,邻接矩阵,去对角线,B,有向图的邻接矩阵特征,不一定是对称矩阵，通常是非对称矩阵； 存储量为n2 （或 n(n-1) ）； 顶点i的入度：diin=第i列非零元素个数= 顶点i的出度：diout=第i行非零元素个数= 顶点i的度：di= diin+ diout,例2：有向图G2及其邻接矩阵,G2,A,A(i,j) =,Wij，若（ i, j ）E或 E 且Wij为该边或弧的权值,，否则（i!=j）,网的邻接矩阵：Page375,耗费邻接矩阵:,例,A,无向网时，为对称矩阵； 有向网时，不一定是对称矩阵。 ：表示NoEdge，INT_MAX#define INT_MIN (-2147483647 - 1) /* minimum (signed) int value */#define INT_MAX 2147483647 /* maximum (signed) int value */,#define MaxValue Int_Maxconst int NumEdges = 50; /边条数const int NumVertices = 10; /顶点个数typedef char VertexData; /顶点数据类型 typedef int EdgeData; /边上权值类型typedef struct VertexData vexListNumVertices; /顶点表 /邻接矩阵, 可视为边之间的关系 EdgeData EdgeNumVerticesNumVertices; /图中当前的顶点个数与边数 int n, e; MTGraph;,示例：邻接矩阵的结构定义,（1）优点,易于判断两顶点间是否有边、弧直接连接； 易于求顶点的度。,（2）缺点,是图的一种静态存储方法，建立这种存储结构时需预先知道图中顶点的个数，不适合作动态处理图； 若图中边或弧的数目很少，称为稀疏图，此时邻接矩阵中存储了大量的0元素，是稀疏矩阵，浪费空间。 解决方法：“位压缩”，Page373,邻接矩阵的优缺点,位压缩思想,以无向图为例： n(n-1)/2 假设采用short型存储，sizeof(short)=2字节存储空间： n(n-1) bytes【思想】每个矩阵元素采用一个二进制位，16个位合并为一个WORD类型压缩存储空间： n(n-1)/8引入问题：存储和检索元素的时间复杂度增加！,12.5.2 邻接压缩表,在G（G =(V,E)，| V |= n, | e |= e）的邻接压缩表的定义中，使用两个一维数组： h0:n+1：依次记录每个顶点的邻接顶点号 l0:x：记录每个顶点的在h中起始项下标 如果G是有向图，则x=e-1； 如果G是无向图，则x=2e-1。,邻接压缩表示例,l,h=0, 3, 5, 8, 10,h1,h2,h3,h4,h5,顶点1的邻接压缩表,h0:n+1：依次记录每个顶点的邻接顶点号l0:x：记录每个顶点的在h中起始项下标,12.5.3 邻接链表（linked-edjacency-list）,邻接链表是邻接矩阵的改进，把邻接矩阵的n行改为n个单链表，把同一个顶点发出的边链接在同一个称为边链表的单链表中。,邻接链表存储方法是一种顺序存储与链式存储相结合的存储方法；,顺序存储部分用来保存图中顶点的信息; 链式存储部分用来保存边或弧的信息。,#define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧指针 . / 该弧相关信息 ArcNode;typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode;,图的邻接表存储表示,typedef struct VNode *AdjList; Int vexnum, arcnum; /图的当前顶点数和弧数 Int kind; /图的种类标志ALGraph;,邻接链表表示方法,头节点数组：可使用一个Chain类型的数组h来跟踪邻接表；hi.first指向顶点i的邻接表中的第一个节点；邻接表作为链表保存，可用Chain来实现；如果x指向链表hi中的一个节点，则(i,x-data)是图中的一条边。,顶点,边节点,例（1）无向图的邻接链表表示,无向图的邻接表特征,若无向图有n个顶点，e条边，则其邻接表需要n个表头结点（顶点结点）和2e个边结点； 第i个顶点vi的度正好时第i个链表中边结点的个数。,例（2）有向图的邻接表表示,有向图的邻接表特征,若有向图有n个顶点，e条边，则其邻接表需要n个表头结点（顶点结点）和e个边结点； 第i个顶点vi的出度OD(vi)为第i个链表中边结点的个数； 若求第i个结点vi的入度ID(vi)，则需遍历整个邻接表，统计所有链表中data域为i的边结点的个数。,例（3）网的邻接链表表示,（1）优点,当图G中顶点数n多，而边数e少时，采用邻接链表比邻接矩阵节省空间；,对无向图易确定顶点的度。,（2）缺点,对有向图，计算其顶点的入度需另设一逆邻接表；,半动态的存储结构；,无向图中一条边存储了两次，对一条边操作需搜索邻接表两次，处理边结点两次。,邻接链表的优缺点,为了便于确定顶点的入度，可以建立有向图的逆邻接表,即对有向图中每个顶点，建立以Vi为弧头的一个单链表；,逆邻接表的结构和邻接表的结构相同，只是每个单链表中的dest域存放的是: 该边结点所表示的弧尾顶点在一维数组中的序号。,逆邻接表中，第i个顶点Vi的入度ID(Vi)为第i个链表中边结点的个数。,课后练习,Page375：练习10，画图练习14：无向图的邻接矩阵“位压缩”,邻接多重表是对邻接表的一种改进：边重复存储,在邻接多重表中，与邻接表相同，使用一维数组存储图中顶点的信息。,data域 存放与该顶点相关的信息； Firstout域 指向与该顶点相关联的第一个边结点。,1、无向图的邻接多重表,