第9章图 9.1图的基本概念 9.2图的存储结构 9.3图的遍历 9.4生成树和最小生成树 9.5最短路径 9.6拓扑排序 9.7AOE网与关键路径 本章小结
9.1 图的基本概念 第9章 图 9.2 图的存储结构 9.3 图的遍历 9.4 生成树和最小生成树 9.5 最短路径 9.6 拓扑排序 本章小结 9.7 AOE网与关键路径
9.1图的基本概念 9.1.1图的定义 图( Graph)G由两个集合v( Vertex)和E(Edge)组成, 记为G=(V,E),其中V是顶点的有限集合记为VG,E是 连接中两个不同顶点(顶点对)的边的有限集合,记为 E(G 在图G中,如果代表边的顶点对是无序的则称G为 无向图无向图中代表边的无序顶点对通常用圆括号括 起来用以表示一条无向边。 如果表示边的顶点对是有序的则称G为有向图,在 有向图中代表边的顶点对通常用尖括号括起来
9.1 图的基本概念 9.1.1 图的定义 图(Graph)G由两个集合V(Vertex)和E(Edge)组成, 记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是 连接V中两个不同顶点(顶点对)的边的有限集合,记为 E(G)。 在图G中,如果代表边的顶点对是无序的,则称G为 无向图,无向图中代表边的无序顶点对通常用圆括号括 起来,用以表示一条无向边。 如果表示边的顶点对是有序的,则称G为有向图,在 有向图中代表边的顶点对通常用尖括号括起来
9.1.2图的基本术语 1.端点和邻接点 在一个无向图中若存在一条边 (vpy则称v和v为此边的两个端点, 并称它们互为邻接点 在一个有向图中,若存在一条边 vpv>,则称此边是顶点v的一条出 边同时也是顶点v的一条入边;称 0 v和v分别为些边的起始端点(简称 为起点和终止端点(简称终点);称 v和v互为邻接点。 (b)
9.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中,若存在一条边 (vi ,vj ),则称vi和vj为此边的两个端点, 并称它们互为邻接点。 在一个有向图中,若存在一条边 <vi ,vj>,则称此边是顶点vi的一条出 边,同时也是顶点vj的一条入边；称 vi和vj分别为此边的起始端点(简称 为起点)和终止端点(简称终点)；称 vi和vj互为邻接点。 1 2 3 0 4 1 2 3 0 4 (a) (b)
2.顶点的度、入度和出度 在无向图中,顶点所具有的边 的数目称为该顶点的度。 在有向图中以顶点v为终点的 4 入边的数目,称为该顶点的入度 以顶点v为始点的出边的数目,称为 (a) 该顶点的出度。一个顶点的入度与 出度的和为该顶点的度。 若一个图中有n个顶点和e条边, 3 0 每个顶点的度为d1≤i≤n则有: 2 ∑
2. 顶点的度、入度和出度 在无向图中,顶点所具有的边 的数目称为该顶点的度。 在有向图中,以顶点vi为终点的 入边的数目,称为该顶点的入度。 以顶点vi为始点的出边的数目,称为 该顶点的出度。一个顶点的入度与 出度的和为该顶点的度。 若一个图中有n个顶点和e条边, 每个顶点的度为di (1≤i≤n),则有： 1 2 3 0 4 1 2 3 0 4 (a) (b) = n i 1 di 2 1 e＝
3.完全图 若无向图中的每两个顶点之间都 存在着一条边有向图中的每两个顶 点之间都存在着方向相反的两条边, 则称此图为完全图。 显然完全无向图包含有条边完 全有向图包含有n(n-1)条边。例如 图(a)所示的图是一个具有4个顶点 的完全无向图共有6条边。图(b)所 示的图是一个具有4个顶点的完全有 (b) 向图共有12条边
3. 完全图 若无向图中的每两个顶点之间都 存在着一条边,有向图中的每两个顶 点之间都存在着方向相反的两条边, 则称此图为完全图。 显然,完全无向图包含有条边,完 全有向图包含有n(n-1)条边。例如, 图(a)所示的图是一个具有4个顶点 的完全无向图,共有6条边。图(b)所 示的图是一个具有4个顶点的完全有 向图,共有12条边。 1 2 0 3 1 2 0 3 (a) (b)