1、1第第1111章章 图图数据结构与算法分析23456图的应用 为计算机与通信网络的互连建模为计算机与通信网络的互连建模 把一张地图表示为一组位置以及位置之间的距离，把一张地图表示为一组位置以及位置之间的距离，以求得位置之间得最短路径以求得位置之间得最短路径 为网络的流量能力建模为网络的流量能力建模 寻找从开始状态到目标状态得路径，如人工智能问寻找从开始状态到目标状态得路径，如人工智能问题的求解题的求解 为计算机算法建模，显示程序状态的变化为计算机算法建模，显示程序状态的变化 为复杂活动各子任务的完成寻找较优顺序，如大型为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造建筑的建造 为家族、商
2、业或军事组织和自然科学分类中的各种为家族、商业或军事组织和自然科学分类中的各种关系建模关系建模7网型结构小节 客观世界客观世界中广泛存在网状结构中广泛存在网状结构 图结构也在图结构也在计算科学领域计算科学领域中被广泛的中被广泛的（创造和）应用（创造和）应用以上各例的数据(信息)组织形式，均称为网状结构。8图的定义和基本术语9图Graphs图可以用 G = (V, E) 来表示来表示,每个图都包括一每个图都包括一个顶点集个顶点集(vertices) V, 和一个边集合和一个边集合(edges) E, 其中其中E中的每条边都是 V 中某一对顶点之间的连接.顶点总数记为顶点总数记为 |V|, 边的总
3、数记为边的总数记为 |E|.10图Graphs 如果图中的边限定为从一个顶点指向另一个顶点, 则此图称为有向图(directed graph或digraph)。如果图中的边没有方向, 则称之为无向图(undirected graph)。如果图中各顶点均带有标号, 则称之为标号图(labeled graph)。 一条边所连接的两个顶点是相邻的(adjacent), 称为邻接点(neighbors)。连接一对邻接点u、v的边被称为与顶点u、v相关联(incident)的边, 记作(u,v)。每条边都可能附有值或权(weight)。边上标有权的图称为带权图(weighted graph)11顶点的度
4、 在无向图中，与顶点vi(viV(G)相关联的边的条数称为vi的度，记为TD(vi) 在有向图中，顶点的度为顶点的入度、出度之和 入度等于以vi为头的弧的数目 出度等于以vi为尾的弧的数目1( )2nii ieTD v=n为图G的顶点数12路径Paths 和回路 Cycles路径路径: 如果顶点序列如果顶点序列 v1, v2, , vn 从从 vi 到到 vi+1 (1 = i n) 的边均存在，则称顶点序列的边均存在，则称顶点序列v1, v2, , vn 构构成一条长度为成一条长度为 n-1 的路径的路径(path).如果路径上的各个顶点都不同，则称这个路径为如果路径上的各个顶点都不同，则称
5、这个路径为简简单路径单路径(simple path).一条路径将某个顶点一条路径将某个顶点vi 连接到它本身，且其长度大连接到它本身，且其长度大于或等于于或等于3，则称此路径为，则称此路径为回路回路(cycle).如果构成回路的路径是简单路径如果构成回路的路径是简单路径,除了首尾两个顶点除了首尾两个顶点相同以外其他顶点均不同相同以外其他顶点均不同,则称此回路为则称此回路为简单回路简单回路(simple cycle).13图 (2)14子图 子图(subgraph)S是指由图G中选出其顶点集的一个子集VS以及与VS中顶点相关联的一些边所构成的图15连通分量Connected Components
6、如果一个无向图中任意一个顶点到其他任意如果一个无向图中任意一个顶点到其他任意顶点都至少存在一条路径顶点都至少存在一条路径, 则称此无向图为则称此无向图为连通的连通的(connected).无向图的无向图的极大极大连通子图称为连通子图称为连通分量连通分量(connected component).16无环图 和 有向无环图 不带回路的图称为无环图(acyclic graph) 不带回路的有向图称为有向无环图(directed acyclic graph或DAG) 一棵自由树(free tree)就是一个不带有简单回路的无向图, 它是连通的, 且有|V|-1条边17对比对比网型结构网型结构和和树型
7、结构树型结构的结构特点的结构特点18网状结构网状结构树型结构树型结构 根结点根结点 ( (无前驱无前驱) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) ) 所有的结点的所有的结点的特征一致特征一致 ( (顶点顶点) )结点可以和结点可以和多个的其它结点多个的其它结点 关联关联 ( (边边) )19图的ADT20 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成构成的数据结构。的数据结构。 Graph = (V , R )其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v
8、 为弧头弧头，w 为弧尾弧尾。 谓词 P(v,w) 定义了弧 的意义或信息。图的ADT定义21Graph ADTclass Graph / Graph abstract classpublic: virtual int n() =0; / # of vertices virtual int e() =0; / # of edges / Return index of first, next neighbor virtual int first(int) =0; virtual int next(int, int) =0; / Store new edge virtual void setEdg
9、e(int, int, int) =0; / Delete edge defined by two vertices virtual void delEdge(int, int) =0; / Weight of edge connecting two vertices virtual int weight(int, int) =0; virtual int getMark(int) =0; virtual void setMark(int, int) =0;22结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和
10、删除弧插入和删除弧图的ADT定义（2）23CreatGraph(&G, V, VR): / 按定义(V, VR) 构造图DestroyGraph(&G): / 销毁图结构的建立和销毁24对顶点的访问操作LocateVex(G, u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置位置” ；否则返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 对 v 赋值value。25对邻接点的操作FirstAdjVex(G, v); / 返回 v 的“第一个邻接点第一个邻接点” 。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdj
11、Vex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻接下一个邻接/ 点点”。若 w 是 v 的最后一个邻接点，则/ 返回“空”。26插入或删除顶点InsertVex(&G, v); /在图G中增添新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。27插入和删除弧InsertArc(&G, v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。DeleteArc(&G, v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。28遍 历DFSTraverse(G, v, Visit(); /从顶点v起深度优先深度优先遍历图G，
12、并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。29图的实现（物理数据结构）30图 的表示法 邻接矩阵(adjacency matrix)表示法 图的邻接矩阵是一个|V|V|矩阵。 如果从vi到vj存在一条边, 则对第i行的第j个元素做标记, 否则不做标记 邻接矩阵的空间代价为(|V|2) 邻接表(adjacency list)表示法 邻接表是一个以链表为元素的数组。该数组包含|V|个元素, 其中第i个元素存储的是指向顶点vi的链表的指针, 这个链表是由顶点v
13、i的邻接点构成 邻接表的空间代价为(|V|+|E|)31有向图的表示法32无向图的表示法33表示法的空间代价Adjacency Matrix邻接矩阵邻接矩阵:Adjacency List邻接链表邻接链表:哪种表示法存储效率更高取决于图中边的数哪种表示法存储效率更高取决于图中边的数目目34十字链表 十字链表是有向图的另一种链式存储结构十字链表是有向图的另一种链式存储结构. . 可以看成将有向图的邻接表和逆邻接表结合可以看成将有向图的邻接表和逆邻接表结合起来得到的一种链表起来得到的一种链表. . 在十字链表中，对应于有向图中每一条弧有在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也
14、有一个结点一个结点，对应于每个顶点也有一个结点. .V1V2V3V4V1V2V3V4012320303132230102datafirstinfirstouttailvexheadvexhlinktlinkinfo35邻接多重表 邻接多重表是无向图的另一种链式存储结构邻接多重表是无向图的另一种链式存储结构 在邻接表中每一条边（在邻接表中每一条边（vi，vj）有两个结点，分别在第有两个结点，分别在第i个和第个和第j个链表中，这给某些图的操作带来不便个链表中，这给某些图的操作带来不便 在邻接多重表中，每一条边用一个结点表示，每一个在邻接多重表中，每一条边用一个结点表示，每一个顶点也用一个结点表示顶
15、点也用一个结点表示36相邻矩阵实现（1）class Graphm : public Graph /Implement adjacency matrixprivate: int numVertex, numEdge;/Store number of vertices edges int *matrix; / Pointer to adjacency matrix int *mark; / Pointer to mark arraypublic: Graphm(int numVert) / Make graph w/ numVert vertices int i, j; numVertex = n
16、umVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=0; inumVertex; i+) marki = UNVISITED; matrix = (int*) new int*numVertex; / Make matrix for (i=0; inumVertex; i+) matrixi = new intnumVertex; for (i=0; i numVertex; i+)/Edges start w/0 weight for (int j=0; jnumVertex; j+) matr
17、ixij = 0; 37相邻矩阵实现（2）int first(int v)/ Return vs first neighbor int i; for (i=0; inumVertex; i+) if (matrixvi != 0) return i; return i; / Return n if noneint next(int v1, int v2)/ Get v1s neighbor after v2 int i; for(i=v2+1; i0, Illegal weight value); if (matrixv1v2 = 0) numEdge+; matrixv1v2 = wgt;v
18、oid delEdge(int v1, int v2) / Delete edge (v1, v2) if (matrixv1v2 != 0) numEdge-; matrixv1v2 = 0;int weight(int v1, int v2) return matrixv1v2; int getMark(int v) return markv; void setMark(int v, int val) markv = val; 39邻接表实现（1）class Edge public: int vertex, weight; Edge() vertex = -1; weight = -1;
19、Edge(int v, int w) vertex = v; weight = w; ;class Graphl : public Graph / Implement adjacency listprivate: int numVertex, numEdge; / Number of vertices, edges List* vertex; / List headers int *mark; / Pointer to mark arraypublic: Graphl(int numVert)/ Make graph with numVert vertices int i, j; numVer
20、tex = numVert; numEdge = 0; mark = new intnumVert; / Initialize mark array for (i=0; inumVertex; i+) marki = UNVISITED; / Create and initialize adjacency lists vertex = (List*) new List*numVertex; for (i=0; inumVertex; i+) vertexi = new LList();40邻接表实现（2）int first(int v) / Return first neighbor of v
21、 Edge it; vertexv-setStart(); if (vertexv-getValue(it) return it.vertex; else return numVertex; / Return n if noneint next(int v1, int v2) / Gete v1s neighbor after v2 Edge it; vertexv1-getValue(it); if (it.vertex = v2) vertexv1-next(); else / Start from beginning of list vertexv1-setStart(); while
22、(vertexv1-getValue(it) & (it.vertex next(); if (vertexv1-getValue(it) return it.vertex; else return numVertex; / Return n if none41邻接表实现（3） / Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt) Assert(wgt0, Illegal weight value); Edge it(v2, wgt); Edge curr; vertexv1-getValue(curr); if (cu
23、rr.vertex != v2) / If not already there, search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) / Clear out the current one vertexv1-remove(curr); else numEdge+; vertexv1-insert(it);42邻接表实现（4）void delEdge(int v1, int v2) / Delete
24、edge (v1, v2) Edge curr; vertexv1-getValue(curr); if (curr.vertex != v2) /If not already there,search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) / If not,then there is none vertexv1-remove(curr); numEdge-; 43邻接表实现（5） int weig
25、ht(int v1, int v2) / Return weight of (v1, v2) Edge curr; vertexv1-getValue(curr); if (curr.vertex != v2) /If not already there, search for (vertexv1-setStart(); vertexv1-getValue(curr); vertexv1-next() if (curr.vertex = v2) break; if (curr.vertex = v2) return curr.weight; else return 0; / No such edgeint getMark(int v) return markv; void setMark(int v, int val) markv = val; 44要点回顾要点回顾 图型结构是一种动态的，非线性的，可描述结构网状特性的数据结构 图ADT的设计，包括图ADT和图的顶点ADT的设计 图的结构性质和特征是很重要的45图的遍历。 课后预习课后预习
