《图的定义和术语.ppt》由会员分享，可在线阅读，更多相关《图的定义和术语.ppt（28页珍藏版）》请在三一办公上搜索。
1、第7章 图,线性结构：是研究数据元素之间的一对一关系。在这种结构中，除第一个和最后一个元素外，任何一个元素都有唯一的一个直接前驱和直接后继。树结构：是研究数据元素之间的一对多的关系。在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。,图(Graph)是一种比线性表和树更为复杂的数据结构。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。,7.1 图的定义和术语,V1,V3,V2,V4,V1,V2,V5,V4,V3,图7.1 图的
2、示例(a)有向图G1(b)无向图G2,(a),(b),图的定义和术语顶点（Vertex)：在图中的数据元素通常称为顶点（Vertex)。约定V表示顶点的有穷非空集合，VR表示两个顶点之间的关系的集合。弧（Arc）：表示两个顶点v和w之间存在一个关系，用表示顶点v到w的一条弧。且称v为弧尾（Tail）或初始点，称w为弧头（Head）或终端点。此时的图称为有向图（Digraph）。其中，顶点偶对的v和w之间是有序的。,无向图(Undigraph)：若图关系集合中，顶点偶对的v和w之间是无序的，称图G是无向图。若属于VR，必有属于VR，即VR是对称的。那么用（v,w）代替这两个有序对，表示v和w的一
3、条边（Edge）。,如图7.1：设有向图G1和无向图G2，形式化定义分别是：G1=(V1，A1)V1=v1,v2,v3,v4A1=,G2=(V2，E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v1),(v3,v5),V1,V3,V2,V4,V1,V2,V5,V4,V3,图7.1 图的示例(a)有向图G1(b)无向图G2,(a),(b),完全无向图：对于无向图，若图中顶点数为n，用e表示边的数目，则e 0，n(n-1)/2。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图另外的定义是：对于无向图G=(V，E)，若v
4、i，vj V，当vivj时，有(vi,vj)E，即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。,完全有向图：对于有向图，若图中顶点数为n，用e表示弧的数目，则e0，n(n-1)。具有n(n-1)条边的有向图称为完全有向图。完全有向图另外的定义是：对于有向图G=(V，E)，若vi，vjV，当vi vj时，有E并且E，即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。,有很少边或弧的图（enn）的图称为稀疏图，反之称为稠密图。权(Weight)：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图称为网。,子图和生成子图：设有图G
5、=(V，E)和G=(V，E)，若VV且EE，则称图G是G的子图；若V=V且EE，则称图G是G的一个生成子图。P7.2,对于无向图G=(V，E)，若边(v,w)E，则称顶点v和w 互为邻接点，即v和w相邻接。边(v,w)依附(incident)于顶点v和w，或者说(v,w)和顶点v和w相关联。图G中和v相关联的边的数目称为顶点v的度(degree)，记为TD(v)。例如无向图G2。TD(V1)，TD(V2)，TD(V3)，TD(V4)，TD(V5),V1,V2,V5,V4,V3,G2,对于有向图G=(V，E)，若有向弧E，则称顶点v“邻接到”顶点w，顶点w“邻接自”顶点v，弧 与顶点v和w“相关
6、联”。对有向图G=(V，E)，若vi V，图G中以顶点v作为尾或初始的有向边(弧)的数目称为顶点v的出度(Outdegree)，记为OD(v)；以v作为头或终点的有向边(弧)的数目称为顶点v的入度(Indegree)，记为ID(v)。顶点v的出度与入度之和称为v的度，记为TD(v)。即TD(v)=OD(v)+ID(v),例如图7.1所示的无向图。OD(v1)，ID(,1)，TD(v1)；OD(v3)，ID(,3)，TD(v1),V1,V3,V2,V4,(G1),一般地，如果顶点vi在的度记为TD(vi)，那么一个有n个顶点，e条边或弧的图，满足：TD(vi)=2e,路径(Path)：对无向图G
7、=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边(弧)能到达vj。,路径的长度：路径上边或有向边(弧)的数目称为该路径的长度。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。,连通图、图的连通分量：对无向图G=(V，E)，若vi，vj V，又称顶点vi到vj有路径，即vi和vj是连通的，则称图G是连通图，否则称为
8、非连通图。若G是非连通图，则极大的连通子图称为G的连通分量。例如图7.1(b)中的G2就是一个连通图。再例如图7.3所示。P159,V1,V2,V5,V4,V3,G2,对有向图G=(V，E)，若vi，vj V，都有以vi为起点，vj 为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大的强连通子图称为G的强连通分量。“极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。例如图7.1(a)。,V1,V3,V2,V4,(G1),V1,V3,V2,V4,强连通分量,生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，
9、它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。如图7.5所示。,关于无向图的生成树的几个结论：一棵有n个顶点的生成树有且仅有n-1条边；如果一个图有n个顶点和小于n-1条边，则是非连通图；如果多于n-1条边，则一定有环；有n-1条边的图不一定是生成树。,如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树，如图7-3所示。有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。网：每个边(或弧)都附加一个权值的图，称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。如图7-4所示。,7.1.2 图的抽象数据类型定义,图的抽象
10、数据类型定义如下：ADT Graph数据对象V：具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且P(v,w)，表示 从v到w的弧，P(v,w)定义了弧的信息,基本操作P：CreateGraph(&G,V,VR)：图的创建操作。初始条件：无。操作结果：按V和VR的定义构造树G。GetVex(G,v)：求图中的顶点v的值。初始条件：图G存在，v是图中的一个顶点。操作结果：返回v的值。,LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在 图中“位置”；否则返回其它信息PutVex(初始条件：图G存在，v是G中某个顶点。操作结果：对 v 赋值value。ADT Graph 详见p156157。,习 题 七,分析并回答下列问题：图中顶点的度之和与边数之和的关系?有向图中顶点的入度之和与出度之和的关系?具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图?具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的?为什么?,设一有向图G=(V,E)，其中V=a,b,c,d,e，E=,请画出该有向图，并求各顶点的入度和出度。,
