第7章图 7.1图的基本概念 人路共施图世 7.11图的定义 图G( Graph)由两个集合V Vertex)和E(Edge)组成,记为 G=(V,E),其中Ⅴ是顶点的有限集 记为v(G),E是连接V中两个不同顶 点(顶点对)的边的有限集合,记为 一幅图 E(G)
第7章 图 7.1 图的基本概念 7.1.1 图的定义 图G（Graph）由两个集合V （Vertex）和E（Edge）组成，记为 G=(V,E)，其中V是顶点的有限集合， 记为V(G)，E是连接V中两个不同顶 点（顶点对）的边的有限集合，记为 E(G)。 一幅图
抽象数据类型图的定义如下: ADT Grap h 数据对象: D={a11≤i≤n,n>0,a为int类型} /:为每个顶点的唯一编号 数据关系: R={ r=(,2|aa1∈D,1Kn,1≤n,其中a可以有零个或多个 前驱元素,可以有零个或多个后继元素} 基本运算 void CreateMGraph0:根据相关数据建立一个图。 string DispMgrapho:输出一个图 int Getn(:求图中顶点个数。 int Gete:求图中边数。 int Degree(intv):求顶点v的度。 DFS(ⅴ):从顶点v出发深度优先遍历图 BFS():从顶点v出发广度优先遍历图
抽象数据类型图的定义如下： ADT Graph { 数据对象： D={ai | 1≤i≤n,n≥0,ai为int类型} //ai为每个顶点的唯一编号 数据关系： R={r} r={ | ai ,aj∈D,1≤i≤n，1≤j≤n，其中ai可以有零个或多个 前驱元素，可以有零个或多个后继元素} 基本运算： void CreateMGraph()：根据相关数据建立一个图。 string DispMGraph()：输出一个图。 int Getn()：求图中顶点个数。 int Gete()：求图中边数。 int Degree(int v)：求顶点v的度。 DFS(v)：从顶点v出发深度优先遍历图。 BFS(v)：从顶点v出发广度优先遍历图。 … }
说明:对于n个顶点的图,对每个顶点连续编号,即顶 点的编号为0-n-1。通过编号唯一确定一个顶点。 在图G中,如果代表边的顶点对是无序的,则称G为无向 图,无向图中代表边的无序顶点对通常用圆括号括起来,用 以表示一条无向边。 如果表示边的顶点对是有序的,则称G为有向图,在有向 图中代表边的顶点对通常用尖括号括起来
说明：对于n个顶点的图，对每个顶点连续编号，即顶 点的编号为0－n-1。通过编号唯一确定一个顶点。 在图G中，如果代表边的顶点对是无序的，则称G为无向 图，无向图中代表边的无序顶点对通常用圆括号括起来，用 以表示一条无向边。 如果表示边的顶点对是有序的，则称G为有向图，在有向 图中代表边的顶点对通常用尖括号括起来
图(a)是一个无向图G1,其顶点集合(G1)={0,1,2,3,4},边 集合E(G1)={(1,2)2(1,3,1,0)、2,3),(3,0),(2,4),(3,4),(4,0)} 图2(b)是一个有向图G2,其顶点集合v(G2)={0,1,2,3,4} 边集合E(G2)=(,,,,-0,3>,,,}。 (a)一个无向图 (b)一个有向图
1 2 3 0 4 1 2 3 0 4 （a）一个无向图 （b）一个有向图 图（a）是一个无向图G1，其顶点集合V(G1 )={0,1,2,3,4}，边 集合E(G1 )={(1,2),(1,3),(1,0),(2,3),(3,0),(2,4),(3,4),(4,0)}。 图2（b）是一个有向图G2，其顶点集合V(G2 )={0,1,2,3,4}， 边集合E(G2 )={,,,,,,,}
712图的基本术语 1.端点和邻接点 在一个无向图中,着存在一条边 j,则称顶点和顶点为此边的两个端点, 并称它们互为邻接点。 在一个有向图中,若存在一条边< 户,则称此边是顶点)的一条出边,同时 也是顶忘一条入边;称顶点顶点 分别为此边的起始端点(简称为起点)(2 和终止端点(简称终点);称顶点和 顶忘互为邻接点
7.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中，若存在一条边(i， j)，则称顶点i和顶点j为此边的两个端点， 并称它们互为邻接点。 在一个有向图中，若存在一条边，则称此边是顶点i的一条出边，同时 也是顶点j的一条入边；称顶点i和顶点j 分别为此边的起始端点（简称为起点） 和终止端点（简称终点）；称顶点i 和 顶点j 互为邻接点。 1 2 3 0 4 (a) 1 2 3 0 4 (b)
2.顶点的度、入度和出度 在无向图中,顶点所具有的边的数 目称为该顶点的度。 在有向图中,以顶点终点的入边 的数目,称为该顶点的入度。以项点为 始点的出边的数目,称为该顶点的出度 一个顶点的入度与出度的和为该顶点的 若一个图中有n个顶点和e条边,每 个顶点的度为d,(I≤还n),则有:
2. 顶点的度、入度和出度 在无向图中，顶点所具有的边的数 目称为该顶点的度。 在有向图中，以顶点i为终点的入边 的数目，称为该顶点的入度。以顶点i为 始点的出边的数目，称为该顶点的出度。 一个顶点的入度与出度的和为该顶点的 度。 若一个图中有n个顶点和e条边，每 个顶点的度为di（1≤i≤n），则有： = n i i e d 1 2 1 ＝ 1 2 3 0 4 (a) 1 2 3 0 4 (b)
例71一个无向连通图中有16条边,所有顶点的度均小于5, 度为4的顶点有3个,度为3的顶点有4个,度为2的顶点有2个, 则该图有个顶点。 A.10 B 11 C.12 D.13 解:设该图有n个顶点,图中度为的顶点数为吗 (0≤i≤4),显然n=0,n=3+42+n1+n=9+m1,而度之和 =4x3+3×4+2×2+n1=28+n1,而度之和=2e=32,所以有 28+n1=32,得m1=4,n=9+n1=13。本题答案为D
例7.1 一个无向连通图中有16条边，所有顶点的度均小于5， 度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个， 则该图有 个顶点。 A.10 B.11 C.12 D.13 解：设该图有n个顶点，图中度为i的顶点数为ni （0≤i≤4），显然n0=0，n=3+4+2+n1+n0=9+n1，而度之和 =4×3+3×4+2×2+n1=28+n1，而度之和=2e=32，所以有 28+n1=32，得n1=4，n=9+n1=13。本题答案为D
3完全图 若无向图中的每两个顶点之间都存 2 0 在着一条边,有向图中的每两个顶点之 间都存在着方向相反的两条边,则称此 图为完全图。 3 显然,完全无向图包含有条边,完 全有向图包含有n(n-1)条边。例如,图 (a所示的图是一个具有4个顶点的完全 无向图,共有6条边。图(b所示的图是 一个具有4个顶点的完全有向图,共有 0 12条边。 3 (b)
3. 完全图 若无向图中的每两个顶点之间都存 在着一条边，有向图中的每两个顶点之 间都存在着方向相反的两条边，则称此 图为完全图。 显然，完全无向图包含有条边，完 全有向图包含有n(n-1)条边。例如，图 (a)所示的图是一个具有4个顶点的完全 无向图，共有6条边。图(b)所示的图是 一个具有4个顶点的完全有向图，共有 12条边。 (b) 1 2 0 3 1 2 0 3 (a)
4.稠密图、稀疏图 当一个图接近完全图时,则称 3 0 为稠密图。相反,当一个图含有 较少的边数(即当e<m(m-1))时, 4 则称为稀疏图。 5.子图 设有两个图G=(V,E)和(2 3 0)(b) G=(V,E),着V是Ⅴ的子集, 即VcV,且E是E的子集,即 E’E,则称G是G的子图。例如 图(b是图(a)的子图,而图(c)不是 图(a)的子图 2 3 0 注意:G中V的子集和E的子集并 不一定构成G的子图
4 . 稠密图 、稀疏图 当一个图接近完全图时 ，则称 为稠密图 。相反 ，当一个图含有 较少的边数 （即当e<< n ( n - 1 ) ） 时 ， 则称为稀疏图 。 5 . 子图 设有两个图 G=(V ， E) 和 G’=(V’ ，E’) ， 若V’ 是 V的子集 ， 即V’ V ， 且E’ 是 E的子集 ， 即 E’ E ，则称G’ 是 G 的子图 。例如 图(b)是图(a)的子图 ，而图(c)不是 图(a)的子图 。 (a) 1 2 3 0 41 2 3 0 4 (b) 1 2 3 0 4 (c) 注意： G 中 V的子集和 E的子集并 不一定构成 G的子图
6.路径和路径长度 在一个图G=(V,E中,从顶点倒顶忘 的一条路径是一个顶点序列(i;12…,im 着此图G是无向图,则边(i,i),(1),… (m1in),(n)属于E(G);若此图是有向图, 则,1>,…,可m1>3,m→>属于(2 E(G)。 路径长度是指一条路径上经过的边的数 目。若一条路径上除开始点和结束点可以相 同外,其余顶点均不相同,则称此路径为简 单路径。例如,有图中,(0,2,1)就是一条 简单路径,其长度为2
6 . 路径和路径长度 在一个图G=(V ，E) 中 ，从顶点 i到顶点j 的一条路径是一个顶点序列 ( i , i 1 , i 2 , … , im ,j) ， 若此图 G是无向图 ，则边 ( i , i 1 ) ， ( i 1 , i 2 ) ， … ， ( im - 1 , im ) ， ( im ,j)属于E(G)；若此图是有向图 ， 则 ， ， … ， ， 属于 E(G) 。 路径长度是指一条路径上经过的边的数 目 。若一条路径上除开始点和结束点可以相 同外 ，其余顶点均不相同 ，则称此路径为 简 单路径 。例如 ，有图中 ， ( 0 ， 2 ， 1 )就是一条 简单路径 ，其长度为 2 。 1 2 0 3