第九章 9图的基本概念 92图的存储结构 93图的遍历 94生成树和最小生成树 95最短路径
启迪管理课程 1 9.1 图的基本概念 9.2 图的存储结构 9.3 图的遍历 9.4 生成树和最小生成树 9.5 最短路径 第九章 图
91图的基本概念的定义 图G的定义:由顶点( Vertex)或结点 Node)的一个非空有限集和一个边 (edge)或弧(Arc)的有限集组成。 是否存在“空图”? ●仄点:图中的数据元素,用v表示顶点 的有限非空集 边:两顶点之间的关系,用E表示边的 有限集 ●有向图:图G中的每条边都是有方向的, 则称图为有向图。否则称为无向图
启迪管理课程 2 9.1 图的基本概念－－图的定义 ⚫ 图(G)的定义：由顶点（Vertex)或结点 （Node)的一个非空有限集和一个边 （edge)或弧（Arc)的有限集组成。 是否存在“空图”？ ⚫ 顶点：图中的数据元素，用V表示顶点 的有限非空集 ⚫ 边：两顶点之间的关系，用E表示边的 有限集 ⚫ 有向图：图G中的每条边都是有方向的， 则称图为有向图。否则称为无向图。 V1 V2 V3 V4 G1 V1 V2 V4 V5 V3 G2
91图的基本概念的定义 在有向图,一条边是由两个顶点组成的 有序对,用尖括号表示,如G1中的。 这样的边又称为弧,v1为弧的起点,称为弧 尾(Tai);v2为弧的终点,称为弧头Head) 则图G可表示为:G1(V1,E 其中Vv12V3V4} E{,,V3,v4>,V4V1 注:<x,y表示优到的一条弧ar,x为弧(taiD y为弧义(head
启迪管理课程 3 在有向图中，一条边是由两个顶点组成的 有序对，用尖括号表示，如G1中的 。 这样的边又称为弧，v1为弧的起点，称为弧 尾（Tail)；v2为弧的终点，称为弧头(Head)。 则图G1可表示为：G1=(V1 ,E1 ) 其中:V1={v1 ,v2 ,v3 ,v4 } E1={,,,} v1 v2 v3 v4 G1 9.1 图的基本概念－－图的定义 注：表示从x到y的一条弧(arc),x为弧尾(tail)， y为弧头(head)
91图的基本概念的定义 而在无向图中,一条边是由两个顶点的无序对组成, 用圆括号表示,如G2中的(V1,V2) 图G2可表示为:G2=(v2,E2) 其中:V2={v12345} E2={(v1,2),(v1,v4),(v2,v3),(v2v5),(V3,v4),(3,5) 注:(,y表示从到之门的一条连线,称为边eg A注意:① ⑩ ①②
启迪管理课程 4 v1 v2 v4 v5 v3 G2 而在无向图中，一条边是由两个顶点的无序对组成， 用圆括号表示 ,如G2中的(V1 , V2 )。 图G2可表示为：G2=(V2 ,E2 ) 其中：V2={v1 ,v2 ,v3 ,v4 ,v5 } E2={(v1 ,v2 ),(v1 ,v4 ),(v2 ,v3 ),(v2 ,v5 ),(v3 ,v4 ),(v3 ,v5 )} 9.1 图的基本概念－－图的定义 注：(x, y)表示从x到y之间的一条连线，称为边(edge)
91图的基本概念的基本术语 完全图 假设∈E,(则诮,即无顶点到自身的弧;(2) 两顶点间没有多条边的情况 ●有向完全图:有向图中的每两个顶点之间都存在着 方向相反的两条边有n个顶点的有向完全图有n(n-1)边 无向完全图:无向图中的每两个顶点之间都存在着 条边。有n个顶点的无向完全图有mn-1)2边 °稠密图、帮图 3 3 当一个图接近完全图时,则称为稠密图相反,当一个 图含有较少的边数(即当e<<n(n-1)时,则称为稀硫图
启迪管理课程 5 假设∈E，(1)则i≠j，即无顶点到自身的弧;(2) 两顶点间没有多条边的情况 ⚫ 有向完全图：有向图中的每两个顶点之间都存在着 方向相反的两条边. ⚫ 无向完全图：无向图中的每两个顶点之间都存在着 一条边。 2 1 3 2 1 3 有向完全图 无向完全图 有n个顶点的有向完全图有 边 有n个顶点的无向完全图有n(n-1)/2 边 n(n-1) 9.1 图的基本概念－－图的基本术语 完全图 当一个图接近完全图时，则称为稠密图。相反，当一个 图含有较少的边数(即当e<<n(n-1))时，则称为稀疏图。 稠密图、稀疏图
91图的基本概念的基本术语 端点獲接点,项点的度入度出度 对于无向图G=(V,E) 端点,接点:若存在边(v,v) ∈E,则称v和v为该边的两个端点, 并称他们互为新点。 边(vy则依附于顶点v和y,或者说 (vy)和顶点v和v相关联。 质点的度:和顶点相关联的边的数目, 记为d
启迪管理课程 6 9.1 图的基本概念－－图的基本术语 端点、邻接点；顶点的度、入度和出度 对于无向图G=(V,E), 端点、邻接点：若存在边（vi ,vj） ∈E,则称vi和vj为该边的两个端点， 并称他们互为邻接点。 边（vi ,vj )则依附于顶点vi和vj ,或者说 （vi ,vj ) 和顶点vi和vj 相关联。 顶点的度：和顶点相关联的边的数目， 记为d(V) 。 v1 v2 v4 v5 v3 G1
91图的基本概念的基本术语 对手有向图G=(VA),如果弧∈A, 则称顶点V邻接到顶点v,顶点v邻接自v。 入度:以顶点v为弧头的弧的数目,记为 id(v)。 出度:以顶点为孤尾的孤的数目,记为父 od (v)o ●顶点的度d=入度id+出度od 图的边与顶点的度的关系: e=2(m)
启迪管理课程 7 9.1 图的基本概念－－图的基本术语 对于有向图G=(V,A)，如果弧∈A， 则称顶点v邻接到顶点v’，顶点v’邻接自v。 ⚫ 入度：以顶点v为弧头的弧 的数目，记为 id(v)。 ⚫ 出度：以顶点v为弧尾的弧的数目，记为 od(v)。 ⚫ 顶点的度d=入度id+出度od ⚫ 图的边与顶点的度的关系： v1 v2 v3 v4 G1 = = n i i e d v 1 ( ) 2 1
91图的基本概念的基本术语 △°权和网 ●权( weight:与图的边或弧相关的数称之为权 ●网( Networκ):带权的图 △°子图 ●子图( Subgraph):假设有两个图G=(V,E和 2 G=(V,E),如果V≌V,E'≌E,则称G为G的子图。 ④ G (b) 8
启迪管理课程 8 9.1 图的基本概念－－图的基本术语 权和网 子图 ⚫ 权（weight) ：与图的边或弧相关的数称之为权 ⚫ 网（Nerwork）：带权的图 v1 v2 v3 5 1 2 ⚫子图（Subgraph)：假设有两个图G=(V,E)和 G’=(V’,E’), 如果V’V，E’ E，则称G’为G的子图。 3 5 6 2 4 5 1 3 6 2 1 2 4 G (a) (b) (c)
91图的基本概念的基本术语 席经和路经长度 路经:在无向图中,着存在一个顶点序列(v1v10, v1,v12…,MmY)其中v1,)∈E,1sm,则称页 点v到v存在一条路径。如果G是有向图,则路径也是 有向的,顶点序列应满足≮v1V1∈E,1≤m。 ●路经长度:路径上的边或弧的数目
启迪管理课程 9 9.1 图的基本概念－－图的基本术语 路径和路径长度 ⚫ 路径：在无向图中，若存在一个顶点序列(vi ,vi,0, vi,1,vi,2,…,vi,m,vj ),其中(vi,j-1 ,vi,j)∈E，1≤j≤m,则称顶 点v到v’存在一条路径。如果G是有向图，则路径也是 有向的，顶点序列应满足∈E, 1≤j≤m 。 ⚫ 路径长度：路径上的边或弧的数目。 v1 v2 v4 v5 v3 G2 v1 v2 v3 v4 G1
91图的基本概念的基本术语 回路豆环 ●回路(环):第一个顶点和最后一个(y 顶点相同的路径。 篇单路经:若一条路径上除开始点和 结束点可以相同外,其余顶点均不相同,(v 则称此路径为简单路径。 G 简单回路(环):除了第一个顶点和 最后一个顶点之外,其余顶点不重复出 现的回路。 10
启迪管理课程 10 9.1 图的基本概念－－图的基本术语 回路或环 ⚫ 回路（环）：第一个顶点和最后一个 顶点相同的路径。 ⚫ 简单路径：若一条路径上除开始点和 结束点可以相同外，其余顶点均不相同， 则称此路径为简单路径。 ⚫ 简单回路（环）：除了第一个顶点和 最后一个顶点之外，其余顶点不重复出 现的回路。 v1 v2 v4 v5 v3 G2 v1 v2 v3 v4 G1