第八章 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络
◼ 图的基本概念 ◼ 图的存储表示 ◼ 图的遍历与连通性 ◼ 最小生成树 ◼ 最短路径 ◼ 活动网络
图的基本概念 图定义图是由顶点集合 vertex)及顶点间 的关系集合组成的一种数据结构: Graph=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合 E={(x,y)|x,y∈ 或E={x,y>|x,y∈W&&Pamh(x,y)} 是顶点之间关系的有穷集合,也叫做边 (edge)集合。Pamh(x,y)表示从x到y的 条单向通路,它是有方向的
图的基本概念 ◼ 图定义 图是由顶点集合(vertex)及顶点间 的关系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x 某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y V } 或 E = { | x, y V && Path (x, y)} 是顶点之间关系的有穷集合，也叫做边 (edge)集合。Path (x, y)表示从 x 到 y 的一 条单向通路, 它是有方向的
有向图与无向图在有向图中,顶点对是有序的。在无向图中,顶点对(x,y是 无序的。 完全图若有n个顶点的无向图有n(n-1)/2 条边,则此图为完全无向图。有n个顶点的 有向图有m(n-1)条边,则此图为完全有向图。 ①2g9⑦ 3③④⑤(②
◼ 有向图与无向图 在有向图中，顶点对 是有序的。在无向图中，顶点对(x, y)是 无序的。 ◼ 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的 有向图有n(n-1) 条边, 则此图为完全有向图。 0 0 0 0 1 1 1 2 1 2 3 3 4 5 6 2 2
邻接顶点如果(,y)是E(G)中的一条边, 则称与v互为邻接顶点。 子图设有两个图G=(V,E和G=(V”, E)。若V且EE,则称图G”是图G 的子图。 0 子图 0((0 ①②2①①②|②2 3 3 3 3 权某些图的边具有与它相关的数,称之为 权。这种带权图叫做网络
◼ 邻接顶点 如果 (u, v) 是 E(G) 中的一条边， 则称 u 与 v 互为邻接顶点。 ◼ 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。 ◼ 权 某些图的边具有与它相关的数, 称之为 权。这种带权图叫做网络。 0 1 2 3 子图 0 1 3 0 1 2 3 0 2 3
顶点的度一个顶点v的度是与它相关联的 边的条数。记作TD)。在有向图中顶点 的度等于该顶点的入度与出度之和 顶点ν的入度是以v为终点的有向边的条 数,记作I(吵);顶点v的出度是以v为始点 的有向边的条数,记作OD(v) 路径在图G=(VE)中,着从顶点v出发, 沿一些边经过一些顶点vV2 °°"pnr 到 为从顶页点到页点的路径。它经过的边 (vyn)、("n;"2)、…、(my)应是属于E 的边
◼ 顶点的度 一个顶点v的度是与它相关联的 边的条数。记作TD(v)。在有向图中, 顶点 的度等于该顶点的入度与出度之和。 ◼ 顶点 v 的入度是以 v 为终点的有向边的条 数, 记作 ID(v); 顶点 v 的出度是以 v 为始点 的有向边的条数, 记作 OD(v)。 ◼ 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点vp1 , vp2 , …, vpm，到 达顶点vj。则称顶点序列(vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边 (vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj ) 应是属于E 的边
路径长度非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指略径 上各边的权之和。 简单路径着路径上各顶点v,V2y,Vm均不 互相重复,则称这样的路径为简单路径。 回路若路径上第一个顶点v与最后一个 顶点vm重合,则称这样的路径为回路或环。 0 (0 2 3 3
◼ 路径长度 非带权图的路径长度是指此路径 上边的条数。带权图的路径长度是指路径 上各边的权之和。 ◼ 简单路径 若路径上各顶点 v1 ,v2 ,...,vm 均不 互相重复, 则称这样的路径为简单路径。 ◼ 回路 若路径上第一个顶点 v1 与最后一个 顶点vm 重合, 则称这样的路径为回路或环。 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量在无向图中,若从顶点 v到顶点v有路径,则称顶点v与v2是连通 的。如果图中任意一对顶点都是连通的,则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 强连通图与强连通分量在有向图中,若对 于每一对顶点和v都存在一条从到y和 从v到v的路径,则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量 生成树一个连通图的生成树是其极小连 通子图,在n个顶点的情形下,有n-1条边
◼ 连通图与连通分量 在无向图中, 若从顶点 v1到顶点v2有路径, 则称顶点v1与v2是连通 的。如果图中任意一对顶点都是连通的, 则 称此图是连通图。非连通图的极大连通子 图叫做连通分量。 ◼ 强连通图与强连通分量 在有向图中, 若对 于每一对顶点vi和vj , 都存在一条从vi到vj和 从vj到vi的路径, 则称此图是强连通图。非 强连通图的极大强连通子图叫做强连通分 量。 ◼ 生成树 一个连通图的生成树是其极小连 通子图，在n个顶点的情形下，有n-1条边
图的抽象数据类型 class graph i public Graph (; void Insert Vertex( Type vertex void InsertEdge( int vl, int v2, int weight ) void Remove Vertex (int v ) void RemoveEdge(int vl, int v2 )i int Is Empty ( Type Get Weight( int vl, int v2 ); int Get FirstNeighbor( intv) int GetNextNeighbor( int vI, int v2)
图的抽象数据类型 class Graph { public: Graph ( ); void InsertVertex ( Type & vertex ); void InsertEdge ( int v1, int v2, int weight ); void RemoveVertex ( int v ); void RemoveEdge ( int v1, int v2 ); int IsEmpty ( ); Type GetWeight ( int v1, int v2 ); int GetFirstNeighbor ( int v ); int GetNextNeighbor ( int v1, int v2 ); }
图的存储表示 邻接矩阵( Adjacency Matrix) 在图的邻接矩阵表示中,有一个记录各个 顶点信息的顶点表,还有一个表示各个顶 点之间关系的邻矩阵。 设图A=(V,E)是一个有n个顶点的图,图 的邻接矩阵是一个二维数组 A eugeniin 定义: A Edgell 如果∈E或者(ij∈E 0,否则
图的存储表示 ◼ 在图的邻接矩阵表示中，有一个记录各个 顶点信息的顶点表，还有一个表示各个顶 点之间关系的邻接矩阵。 ◼ 设图 A = (V, E)是一个有 n 个顶点的图, 图 的邻接矩阵是一个二维数组A.edge[n][n]， 定义： 邻接矩阵 (Adjacency Matrix) = , , , ( , ) . [ ][ ] 否 则 如 果 或 者 0 1 A i j E i j E Edge i j
④0 ①② Aedge=1010 ③3 1010 「010 Aedge=101 000 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的
◼ 无向图的邻接矩阵是对称的; ◼ 有向图的邻接矩阵可能是不对称的。 0 1 2 3 = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 A.edge 0 1 2 = 0 0 0 1 0 1 0 1 0 A.edge