
第8章 图 提纲 CONTENTS 8.6拓扑排序 8.1图的基本概念 8.7 AOE网与关键路径 8.2图的存储结构 8.5最短路径 8.3图的遍历 作业 8.4生成树和最小生成树 上机实验题 1/40
CONTENTS 提纲 1/40

图的基本概念8.18.1.1图的定义图G(Graph)由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E)V是顶点的有限集合,记为V(G)。E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。2/40
图G(Graph)由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E)。 V是顶点的有限集合,记为V(G)。 E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。 2/40

抽象数据类型图的描述ADT Grapht数据对象:D={ai|≤i≤n-1,n≥0,a为int类型}//a为每个顶点的唯一编号数据关系:R=(r]r={|ai,a,ED,≤i≤n-1,0≤j≤n-1,其中a,可以有零个或多个前驱元素,可以有零个或多个后继元素基本运算:voidCreateGraph():根据相关数据建立一个图。voidDispGraph():输出一个图。7说明约定用i(0≤i≤n-1)表示第i个顶点的编号。3/40
ADT Graph { 数据对象: D={ai | 0≤i≤n-1,n≥0,ai为int类型} //ai为每个顶点的唯一编号 数据关系: R={r} r={ | ai,aj∈D,0≤i≤n-1,0≤j≤n-1,其中ai可以有零个 或多个前驱元素,可以有零个或多个后继元素 } 基本运算: void CreateGraph():根据相关数据建立一个图。 void DispGraph():输出一个图。 . } 抽象数据类型图的描述 说明 约定用i(0≤i≤n-1)表示第i个顶点的编号。 3/40

无向图和有向图在图G中,如果代表边的顶点对(或序偶)是无序的,则称G为无向图。无向图中代表边的无序顶点对通常用圆括号括起来,用以表示一条无向边。如(i,j)表示顶点i与顶点j的一条无向边,显然,(i,j)和(j,所代表的是同一条边。如果表示边的顶点对(或序偶)是有序的,则称G为有向图。在有向图中代表边的顶点对通常用尖括号括起来,用以表示一条有向边(又称为弧),如表示从顶点i到顶点的一条边。(a)一个无向图(b) 一个有向图4/40
在图G中,如果代表边的顶点对(或序偶)是无序的,则称G为无向图。 无向图中代表边的无序顶点对通常用圆括号括起来,用以表示一条无向 边。如(i,j)表示顶点i与顶点j的一条无向边,显然,(i,j)和(j, i)所代表的是同一条边。 如果表示边的顶点对(或序偶)是有序的,则称G为有向图。在有向图 中代表边的顶点对通常用尖括号括起来,用以表示一条有向边(又称为 弧),如表示从顶点i到顶点j的一条边。 无向图和有向图 1 2 3 0 4 1 2 3 0 4 (a)一个无向图 (b)一个有向图 4/40

数据结构中的图一般不重复出现一条边,如果允许重复边出个现,这样的图称为多重图,如一个无向图中顶点1和2之间出现两条或两条以上的边。本书中讨论的图均指非多重图。(a)多重无向图(b)多重有向图5/40
数据结构中的图一般不重复出现一条边,如果允许重复边出 现,这样的图称为多重图,如一个无向图中顶点1和2之间出 现两条或两条以上的边。本书中讨论的图均指非多重图。 1 2 0 3 1 2 0 3 (a)多重无向图 (b)多重有向图 5/40

图的基本术语8.1.2在一个无向图中,若存在一条边(i,j),则称顶点和顶点j为该边的两个端点,并称它们互为邻接点,即顶点是顶点的一个邻接点,顶点也是顶点的一个邻接点。在一个有向图中,若存在一条边,则称此边是顶点的一条出边同时也是顶点的一条入边。和分别为此边的起始端点(简称为起点)和终止端点(简称终点)。并称顶点是i的出边邻接点,顶点是j的入边邻接点。6/40
在一个无向图中,若存在一条边(i,j),则称顶点i和顶点j为该边的 两个端点,并称它们互为邻接点,即顶点i是顶点j的一个邻接点,顶 点j也是顶点i的一个邻接点。 在一个有向图中,若存在一条边,则称此边是顶点i的一条出边, 同时也是顶点j的一条入边。i和j分别为此边的起始端点(简称为起点) 和终止端点(简称终点)。并称顶点j是i的出边邻接点,顶点i是j的 入边邻接点。 6/40

在无向图中,顶点所具有的边的数目称为该顶点的度。在有向图中,顶点i的度又分为入度和出度,以顶点为终点的入边的数目,称为该顶点的入度。以顶点为起点的出边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。。若一个图(无论有向图或无向图)中有n个顶点和e条边,每个顶点的度为d;(o≤i≤n-1),则有:一di02i=07/40
在无向图中,顶点所具有的边的数目称为该顶点的度。在有向图中, 顶点i的度又分为入度和出度,以顶点i为终点的入边的数目,称为该 顶点的入度。以顶点i为起点的出边的数目,称为该顶点的出度。一 个顶点的入度与出度的和为该顶点的度。 若一个图(无论有向图或无向图)中有n个顶点和e条边,每个顶点的 度为di(0≤i≤n-1),则有: 7/40

【例8.1】一个无向图中有16条边,度为4的顶点有3个,度为3的顶点有4个,其余顶点的度均小于3,则该图至少有多少个顶点?解:设该图有n个顶点,图中度为i的顶点数为n;(0≤i≤4)。n4=3, n3=4。要使顶点数最少,该图应是连通的,即ng=0。n=n4+n3+n2+n1+ne=7+n2+n1,即n2+n1=n-7。度之和=4×3+3×4+2×n2+n1=24+2nz+n1≤24+2(n2+n1)=24+2X(n-7)=10+2n。而度之和=2e=32,所以有10+2n≥32,即n≥11。即这样的无向图至少有11个顶点。8/40
【例8.1】一个无向图中有16条边,度为4的顶点有3个,度为3的顶 点有4个,其余顶点的度均小于3,则该图至少有多少个顶点? 解:设该图有n个顶点,图中度为i的顶点数为ni(0≤i≤4)。 n4=3,n3=4。 要使顶点数最少,该图应是连通的,即n0=0。 n=n4+n3+n2+n1+n0=7+n2+n1,即n2+n1=n-7。 度之和=4×3+3×4+2×n2+n1=24+2n2+n1≤24+2(n2+n1)= 24+2×(n-7)=10+2n。 而度之和=2e=32,所以有10+2n≥32,即n≥11。 即这样的无向图至少有11个顶点。 8/40

完全无向图中的每两个顶点之间都存在着一条边。含有n个顶点的完全无向图有n(n-1)/2条边。完全有向图中的每两个顶点之间都存在着方向相反的两条边。含有n个顶点的完全有向图包含有n(n-1)条边。(b)一个完全有向图(a)一个完全无向图9/40
完全无向图中的每两个顶点之间都存在着一条边。含有n个顶点的 完全无向图有n(n-1)/2条边。 完全有向图中的每两个顶点之间都存在着方向相反的两条边。含有 n个顶点的完全有向图包含有n(n-1)条边。 1 2 0 3 1 2 0 3 (a)一个完全无向图 (b)一个完全有向图 9/40

当一个图接近完全图时,则称为稠密图。当一个图含有较少的边数(即无向图有e<<n(n-1)/2,有向图有e<<n(n-1))时,则称为稀疏图。10/40
当一个图接近完全图时,则称为稠密图。 当一个图含有较少的边数(即无向图有e<<n(n-1)/2,有向图有 e<<n(n-1))时,则称为稀疏图。 10/40