本章主要内容 图的基本概念 ■图的存储表示 图的遍历与连通性 最小生成树 最短路径
本章主要内容 ◼ 图的基本概念 ◼ 图的存储表示 ◼ 图的遍历与连通性 ◼ 最小生成树 ◼ 最短路径 2
图的基本概念 定义 口图是由顶点及顶点之间的关系集合组成的数据结构 Graph=(V, E V是顶点的有穷非空集,V={(xX∈某个对象} E是顶点之间关系,称为边(edge的有穷非穷集, E={(Xy)|xy∈v}
图的基本概念 ◼ 定义 图是由顶点及顶点之间的关系集合组成的数据结构 Graph = ( V, E ) ➢ V是顶点的有穷非空集，V={x | x∈某个对象} ➢ E是顶点之间关系，称为边(edge)的有穷非穷集， E={(x,y) | x,y∈V} 3
图的基本概念 n有向图与无向图 口有向图中,顶点对(xy)是有序的 口无向图中,顶点对(xy)是无序的 完全图 nn个顶点的无向图有n(n-1)2条边该图为完全图 n个顶点的有向图有n(n1)条边该图为完全有向图 6 8 4)(5)(6 2 完全无向图 无向图(自由树) 有向图 完全有向图
图的基本概念 ◼ 有向图与无向图 有向图中，顶点对(x,y)是有序的 无向图中，顶点对(x,y)是无序的 ◼ 完全图 n个顶点的无向图有n(n-1)/2条边,该图为完全图 n个顶点的有向图有n(n-1)条边,该图为完全有向图 4 1 2 3 0 1 2 4 0 完全无向图 6 8 3 5 6 7 无向图(自由树) 1 2 0 有向图 完全有向图
图的基本概念 邻接顶点 (u,v)是E中的一条边,则称u与v互为邻接顶点 子图 设有两个图G=(V,E和G=(V,E)。若V≌V 且E≌E,则称G是G的子图 0 0 子图 3 权:边附带的权重,称这样的图称为带权图
图的基本概念 ◼ 邻接顶点 (u, v)是E中的一条边，则称u与v互为邻接顶点 ◼ 子图 设有两个图 G＝(V, E) 和 G’＝(V’, E’)。若 V’ V 且 E’E, 则称G’是G 的子图 ◼ 权：边附带的权重，称这样的图称为带权图 5 1 2 3 0 1 3 0 1 2 3 1 2 3 0 子图
图的基本概念 顶点v的度 与v为端点的边条数,记作D(y) 口入度:有向图中以v为终点的边的条数记作D() 口出度:有向图中以v为始点的边的条数记作OD() 有向图中v的度为入度与出度的和 ■路径 图G=(V,E)中,从顶点v出发沿一些边经过 些顶点vp,v2…,vpm,到达顶点v则称顶点序 列( Vi vp v2…Vpmy)为从顶点v到顶点v的路 径。它经过的边(vp小)、(vpn,vp2)、…( Vomy v) 应是属于E的边
图的基本概念 ◼ 顶点v的度 与v为端点的边条数，记作D(v) 入度：有向图中,以v为终点的边的条数,记作ID(v) 出度：有向图中,以v为始点的边的条数,记作OD(v) 有向图中v的度为入度与出度的和 ◼ 路径 图 G＝(V, E) 中, 从顶点 vi 出发, 沿一些边经过一 些顶点 vp1, vp2, …, vpm，到达顶点vj。则称顶点序 列 (vi vp1 vp2 ... vpm vj )为从顶点vi 到顶点 vj 的路 径。它经过的边(vi , vp1)、(vp1, vp2)、...、(vpm, vj ) 应是属于E的边。 6