东南大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 图

本章主要内容 图的基本概念 ■图的存储表示 图的遍历与连通性 最小生成树 最短路径

本章主要内容 ◼ 图的基本概念 ◼ 图的存储表示 ◼ 图的遍历与连通性 ◼ 最小生成树 ◼ 最短路径 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

图的基本概念 路径长度 口非带权图的路径长度是指此路径上边的条数 口带权图的路径长度是指路径上各边的权之和 简单路径 口路径上各顶点v1V2,…,Vm均不互相重复 回路 口路径上第一个顶点v1与最后一个顶点vm重合

图的基本概念 ◼ 路径长度  非带权图的路径长度是指此路径上边的条数  带权图的路径长度是指路径上各边的权之和 ◼ 简单路径  路径上各顶点 v1 ,v2 ,...,vm均不互相重复 ◼ 回路  路径上第一个顶点 v1 与最后一个顶点vm重合 7

图的基本概念 连通图与连通分量 口无向图中,从顶点v倒到顶点v2有路径,则称顶点v1与 2是连通的。 口若图中任意一对顶点都是连通的则此图是连通图 a非连通图的极大连通子图叫连通分量 5 3 3 连通图 非连通图(有2个连通分量

图的基本概念 ◼ 连通图与连通分量  无向图中, 从顶点v1到顶点v2有路径, 则称顶点v1与 v2是连通的。  若图中任意一对顶点都是连通的, 则此图是连通图  非连通图的极大连通子图叫连通分量 8 1 2 3 0 4 连通图 5 1 2 3 0 4 非连通图(有2个连通分量) 5

图的基本概念 强连通图与强连通分量 口在有向图中若对于每一对顶点v和v都存在一条 从v到y和从到v的路径则称此图是强连通图 口非强连通图的极大强连通子图叫做强连通分量 n生成树 个连通图的生成树是其极小连通子图,在n个 顶点的情形下,有n-1条边

图的基本概念 ◼ 强连通图与强连通分量  在有向图中, 若对于每一对顶点vi和vj , 都存在一条 从vi到vj和从vj到vi的路径, 则称此图是强连通图  非强连通图的极大强连通子图叫做强连通分量 ◼ 生成树  一个连通图的生成树是其极小连通子图，在 n 个 顶点的情形下，有n-1条边。 9

图的存储衰示 ■邻接矩阵 口一个有n个顶点的图G=(V,E),图的邻接矩阵 是一个二维数组 A edgell 1,若(i,j)∈E edge[il10.否则 0 010 010 Edge 010 Edge=101 2 无向图的邻接矩阵是对称的 有向图的邻接矩阵可能不对称 10

图的存储表示 ◼ 邻接矩阵  一个有 n 个顶点的图G = ( V, E )， 图的邻接矩阵 是一个二维数组A.edge[n][n] 10 1 2 0 有向图的邻接矩阵可能不对称 1 2 3 0     = 否 则 若 , , 0 1 ( , ) Edge[ ][ ] i j E i j         = 0 0 0 1 0 1 0 1 0 Edge           = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 Edge 无向图的邻接矩阵是对称的

图的存储表示 ■邻接矩阵 口网络(带权图)的邻接矩阵 W(G,j),若i≠沮或,j)∈E Edge[门 若i≠沮或i)E 若i==j 6 Edge ∞092 5 3508 11

图的存储表示 ◼ 邻接矩阵  网络(带权图)的邻接矩阵 11      = =      = i j i j i , j W i j i j i , j i j 若 若 且 或 若 且 或 , , ( ) ( , ), ( ) [ ][ ] 0 E E Edge               = 6 0 3 5 0 8 0 9 2 0 1 4 Edge 2 3 0 1 8 6 3 9 5 2 1 4