图的定义和术语共72页

图（有向图、无向图）1．图的定义图1所示的⑴，⑵，⑶均为图(Graph)，它有若干个不同的点v1，v2，…，v n，在其中一些点之间用直线或曲线连接。

图中的这些点被称为顶点(vertex)或结点，连接顶点的曲线或直线称为边(edge)。

通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为图，顶点通常被称作是图中的数据元素。

图1在线性结构中每个元素只有一个前趋和一个后续，而图1中的各个图则与之不同，它是一种较为复杂的非线性数据结构，在图结构中的任意两个元素之间都可能相互联系，即每个元素都可能有多个前趋或多个后续。

图作为一种数据结构，通常又可被定义为：graph=(V，E)或G=(V，E)，即一个图是由顶点的集合V和边的集合E组成。

在图1中⑴图中的边没有方向，这类图称为无向图(undirected graph)。

在记录无向图时，(v1，v2 )等价于(v2，v1)。

在图1中⑵图中的边上有一个箭头，它表示边的方向，这类图称为有向图(directed graph)。

在记录有向图时，<v1，v2 >与<v2，v1 >是两条不同的边。

图1中⑴图的顶点集合为：V ＝｛v1，v2，v3，v4｝边集合为：E ＝｛（v1，v2），（v1，v3），（v2，v3），（v2，v4），（v3，v4）｝图1中⑵图的顶点集合为：V ＝｛v1，v2，v3，v4｝边集合为：E ＝｛<v1，v2 >，<v1，v3 >，<v1，v4 >，<v2，v1 >，<v4，v2 >}2 ．图的常用术语环(cycle)：图1中⑶图中的v1点本身也有边相连，这种边称为环。

有限图：顶点与边数均为有限的图，如图1中的三个图均属于有限图。

简单图：没有环且每两个顶点间最多只有一条边相连的图，如图1中的⑴图。

邻接与关联：当（v1，v2）∈E，或<v1，v2 >∈E，即v1，v2间有边相连时，则称v1和v2是相邻的，它们互为邻接点（adjacent），同时称（v1，v2）或<v1，v2 >是与顶点v1、v2相关联的边。

一、图的定义一、图的定义图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。

图是数据元素的集合，这些数据元素被相互连接以形成网络。

其形式化定义为：G=（V，E）V={Vi|Vi∈某个数据元素集合}E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)}其中，G表示图，V是顶点的集合，E是边或弧的集合。

在集合E 中，P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。

二、图的术语顶点集：图中具有相同特性的数据元素的集合称为顶点集。

边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧。

弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个。

弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。

度：在无向图中的顶点的度是指连那个顶点的边的数量。

在有向图中，每个顶点有两种类的的度：出度和入度。

入度：顶点的入度是指向那个顶点的边的数量。

出度：顶点的出度是由那个顶点出发的边的数量。

权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边（或弧）的权（weigh）。

三、图的分类有向图：在一个图中，如果任意两顶点构成的偶对（Vi,Vj）是有序的，那么称该图为有向图。

这里Vi是弧尾，Vj是弧头。

这表示有一个从顶点Vi到顶点 Vj的路径。

但是从Vj到Vi是不可能的。

无向图：在一个图中，如果有任意两顶点构成的边（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的。

在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。

无向完全图又称完全图。

在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。

有很少条边或弧的图称为稀疏图，反之称为稠密图。

四、图的基本操作1.SetNode()：在图中增加一个新的顶点2.GetNode()：获取图中指定顶点3.SetEdge()：在两个顶点之间添加指定权值的边或弧4.GetEdge()：获取两个顶点之间的边5.DelEdge()：删除两个顶点之间的边或弧6.GetNumOfVertex()：获取邻接矩阵顶点数7.GetNumOfEdge()：获取邻接矩阵边或弧的数目8.GetIndex()：获取指定顶点在数组中的索引9.IsEdge()：判断两个顶点之间是否存在边或弧10.IsNode()：判断指定结点是否是图的顶点。

图的基本概念及基本术语基本数据结构线性表结构：线性关系除了起始结点与终⽌结点外，每个结点只有⼀个直接前驱和⼀个直接后继树形结构：层次关系除了根结点外，每个结点只有⼀个⽗结点，但可以有多个⼉⼦结点图：⾮线性结构更加复杂每个结点(顶点)既可以有前驱结点也可以有后继结点，且个数不加限制。

图的其它分类简单图:不考虑顶点到其⾃⾝的边,即(u,v)是图G的边，则u≠v；且，如果图中没有相同的边,则称图为简单图。

完全图:设|V|=n, |E|=e。

对有向图G，若e=n(n-1)，则称G为完全有向图;对⽆向图G，若e=n(n-1)/2;则称G为完全⽆向图。

稀疏图: 有很少条边的图（e<nlogn）稠密图: 相反于稀疏图的图。

赋权图：若⽆向图的每条边都带⼀个权，则称相应的图为赋权⽆向图。

若有向图的每条边都带⼀个权，则称相应的图为赋权有向图。

通常，权是具有某种实际意义的数，⽐如，2个顶点之间的距离，耗费等。

⽹：带权的图称为赋权图或⽹。

顶点的度⽆向图顶点的度：关联于该顶点的边的数⽬，记为D(v)。

有向图顶点：以顶点v为终点的边的数⽬，称为v的⼊度，记为ID(v)；以顶点v为起点的边的数⽬，称为v的出度，记为OD(v)；顶点v的度则定义为该顶点的⼊度与出度之和，即D(v)=ID(v)+OD(v)。

基本操作：1. CreateGraph(G): 创建图G.2. DestroyGraph(G): 销毁图G.3. LocateVertex(G,v): 返回顶点v在图G中的位置，若没有顶点v，则返回值为“空”（-1）.4. GetVertex(G,i):返回图G中第i个顶点的值，若i⼤于图G中顶点数，则返回值为“空”(－1).5. FirstAdjVertex(G,v): 图G中顶点v的第⼀个邻接点。

若v⽆邻接点或图G中⽆顶点v，则返回值为“空”(-1)。

6. NextAdjVertex(G,v,w): 图G中顶点v的下⼀个邻接点紧跟在w后⾯）。