第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