第七章图
第七章 图
7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4最小生成树 7.5 最短路径 7.6有向无环图及其应用
7.1 图的基本概念 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.5 最短路径 7.6 有向无环图及其应用
图的基本概念 图(Graph)是由顶点集合(Vertex)及顶点间的关系集 合(Edge)组成的一种数据结构： Graph=(V,E) 其中V={x|x某个数据对象} 是顶点的有穷非空集合 E=x,y)Ix,y∈V} 或E=x,yp|xy∈V&&.Path(x,y} 是顶点之间关系的有穷集合
图（Graph）是由顶点集合(Vertex)及顶点间的关系集 合(Edge)组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x 某个数据对象} 是顶点的有穷非空集合 E = {(x, y) | x, y V } 或E = { | x, y V && Path (x, y)} 是顶点之间关系的有穷集合 图的基本概念
。 有向图与无向图 在有向图中，顶点对Sx,y>是有序的： 在无向图中，顶点对（仪，y)是无序的。 2 3 5 3 V4
◼ 有向图与无向图 在有向图中，顶点对 是有序的； 在无向图中，顶点对(x, y)是无序的。 v1 v3 v4 v5 v2 v1 v2 v3 v4
。完全图 若有n个顶点的无向图有n(n-1)/2条边，即 如果图中任意两个顶点之间都存在一条边，则此 图为完全无向图。 若有n个顶点的有向图有n(n-1)条边，即图 中任意两个顶点之间都存在方向相反的两条弧， 则此图为完全有向图
◼ 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 即 如果图中任意两个顶点之间都存在一条边，则此 图为完全无向图。 若有 n 个顶点的有向图有n(n-1) 条边, 即图 中任意两个顶点之间都存在方向相反的两条弧， 则此图为完全有向图
0 ②
0 0 0 0 1 1 1 2 1 2 3 3 4 5 6 2 2
.子图设有两个图G=(V,目和G=(V, E)。若V∈V且EsE,则称图G'是图G 的子图。 子图 20 权图的边（或弧)具有与它相关的数，称 之为权。这种带权图叫做网（Network)
◼ 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。 ◼ 权 图的边（或弧）具有与它相关的数, 称 之为权。这种带权图叫做网（Network）。 0 1 2 3 子图 0 1 3 0 1 2 3 0 2 3
顶点的度一个顶点的度是与它相关联的边的条 数。记作TD()。在有向图中，顶点的度等于该顶 点的入度ID(W)与出度OD(W)之和。 以顶点v为始 以顶点v为终 点的有向边的 点的有向边的 条数 条数 路径在图G=(V,E中，若从顶点V,出发，沿一 些边经过一些顶点Vp,Vp2,,Vpm,到达顶点y 则称顶点序列(，V1Vp2…Vpmy)为从顶点v,到 顶点y的路径。它经过的边(VnVp1以(Vp1, Vp2小、(Vpmy）应是属于E的边
◼ 顶点的度 一个顶点v的度是与它相关联的边的条 数。记作TD(v)。在有向图中, 顶点的度等于该顶 点的入度ID(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 为终 点的有向边的 条数 以 顶点v 为始 点的有向边的 条数
。路径长度非带权图的路径长度是指此路径上边 的条数。带权图的路径长度是指路径上各边的权 之和。 回路若路径上起始点和终止点重合，则称这样的 路径为回路或环
◼ 路径长度 非带权图的路径长度是指此路径上边 的条数。带权图的路径长度是指路径上各边的权 之和。 ◼ 回路 若路径上起始点和终止点重合, 则称这样的 路径为回路或环。 0 1 2 3 0 1 2 3 0 1 2 3
连通图与连通分量； 在无向图中，若从顶点V到 顶点V2有路径，则称顶点V与V2是连通的。如果 图中任意一对顶点都是连通的，则称此图是连通 图。非连通图的极大连通子图叫做连通分量。 强连通图与强连通分量在有向图中，若对于每 一对顶点V和y,都存在一条从v到y和从v到v的 路径，则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树一个连通图的生成树是其极小连通子图， 在n个顶点的情形下，有n-1条边
◼ 连通图与连通分量 在无向图中, 若从顶点v1到 顶点v2有路径, 则称顶点v1与v2是连通的。如果 图中任意一对顶点都是连通的, 则称此图是连通 图。非连通图的极大连通子图叫做连通分量。 ◼ 强连通图与强连通分量 在有向图中, 若对于每 一对顶点vi和vj , 都存在一条从vi到vj和从vj到vi的 路径, 则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 ◼ 生成树 一个连通图的生成树是其极小连通子图， 在n个顶点的情形下，有n-1条边