第8章图 8.1图 8.2图的存储结构 8.3图的实现 8.4图的遍历 8.5最小生成树 8.6最短路径
1 8.1 图 8.2 图的存储结构 8.3 图的实现 8.4 图的遍历 8.5 最小生成树 8.6 最短路径 第8章 图
8.1图 图的基本概念 图:由结点集合及结点间的关系集合组成的一种数据结构 记为G=(V,E),其中:是顶点集合,是有穷非空集;E 是的边集合,是有穷集。 2、有向图:图G中的每条边都是有方向的; 3、无向图:图G中的每条边都是无方向的; 4、完全图:图G任意两个顶点都有一条边相连接; 若n个顶点的无向图有m(n-1)2条边,称为无向完全图 若n个顶点的有向图有n(m-1)条边,称为有向完全图 v2 53 (a)有向图(b)有向图(c)无向完全(d
2 ８.1 图 一、图的基本概念 １、图：由结点集合及结点间的关系集合组成的一种数据结构。 记为G＝( V, E )，其中：V是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。 v1 v2 v3 v4 v5 v1 v2 v3 v4 2、有向图：图G中的每条边都是有方向的； ３、无向图：图G中的每条边都是无方向的； ４、完全图：图G任意两个顶点都有一条边相连接； ❖若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 ❖若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 (a)有向图 (b)有向图 (c)无向完全图 (d)有向完全图 1 2 3 1 4 2 3 4
子图:设有两个图G=(H,E1)和G2=(2,E2)。若g V且E2cE,则称图G2是图G1的子图。 (2 (a)图1 (b)图2 6、带权图:指边上带权的图。其中权是指每条边标上具有与 该边相关的数据信息。 7、路径:在图G=(E中,若从顶点v出发,沿一些边经过 顶点 V,到达顶点v。则称顶点序列(v,V,V… pl 为从顶点v到顶点v的路径 路径长度:非带权图的路径长度是指此路径上边的条数; 带权图的路径长度是指路径上各边的权之和。 8、简单路径:路径上各顶点Ⅵ1,V2…Vm均不互相重复。 9、回路:若路径上第一个顶点v1与最后一个顶点vm重合,则 称这样的路径为回路或环
3 5、子图：设有两个图G1＝(V1, E1) 和 G2＝(V2, E2)。若 V2 V1 且 E2 E1, 则称 图G2 是 图G1 的子图。 (a)图1 (b)图２ ７、路径：在图G＝(V, E)中,若从顶点 vi 出发,沿一些边经过 一顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi,vp1,vp2,…, vpm ,vj ) 为从顶点vi 到顶点 vj 的路径。 路径长度：非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。 6、带权图：指边上带权的图。其中权是指每条边标上具有与 该边相关的数据信息。 ８、简单路径：路径上各顶点 v1 ,v2 ,...,vm 均不互相重复。 ９、回路：若路径上第一个顶点 v1 与最后一个顶点vm 重合，则 称这样的路径为回路或环
10、连通图:在无向图中,若从顶点到顶点v有路径,则称顶 点n与吃是连通的。如果图中任意一对顶点都是连通的,则称此 图是连通图。 非连通图的极大连通子图叫做连通分量 11、强连通图:在有向图中,若对于每一对顶点v和v,都存在 条从v到v;和从v到v的路径,则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 12、生成树:是一个极小连通子图,它含有图中全部n个顶点,但 只有m1条边。 13、结点的度:结点v的度是与它相关联的边的条数。记作TD(v) 在有向图中,结点的度等于该结点的入度与出度之和。其中结点 ⅴ的入度是以ⅴ为终点的有向边的条数,记作1D(v);结点v的 出度是以v为始点的有向边的条数,记作0D(v)。 14、邻接结点:若(u,v)是E(G)中的一条边,则称u与v互为邻 接结点
4 10、连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶 点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此 图是连通图。 非连通图的极大连通子图叫做连通分量。 11、强连通图：在有向图中, 若对于每一对顶点vi和vj, 都存在 一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。 12、生成树：是一个极小连通子图，它含有图中全部n个顶点，但 只有n-1条边。 13、结点的度：结点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 结点的度等于该结点的入度与出度之和。其中结点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);结点 v 的 出度是以 v 为始点的有向边的条数, 记作 OD(v)。 14、邻接结点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻 接结点
图的抽象数据类型 数据集合:由一组结点集合{;}和一组边集合{e}组成。当为 带权图时每条边上权w构成权集合{w} 操作集合: 1)初始化 Initiate(G,n) (2)插入结点 InsertVertex( G, vertex) (3)插入边 InsertEdge(Gv1,v2, weight) (4)删除边 Delete Edge〔GvL,v2) (5删除结点 Deete vertex( G, vertex) (6)第一个邻接结点 GetFirstVex(Gv) (7)下一个邻接结点 GetNextVex(GV1v2)
5 数据集合：由一组结点集合｛v i ｝和一组边集合{ej }组成。当为 带权图时每条边上权wi构成权集合{wi }。 操作集合： (1)初始化Initiate(G,n) (2)插入结点InsertVertex(G,vertex) (3)插入边InsertEdge(G,v1,v2,weight) (4)删除边DeleteEdge（G,v1,v2) (5)删除结点DeeteVertex(G,vertex) (6)第一个邻接结点GetFirstVex(G,v) (7)下一个邻接结点GetNextVex(G,v1,v2) 二、图的抽象数据类型
8.2图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种 图的邻接矩阵 1、无权值的有向图的邻接矩阵 设有向图具有n个结点,则用n行n列的布尔矩阵A表示该有向图; 并且A[=1,如果i至j有一条有向边;A[,=0,如果i至j没有一条有向边 有向图 邻接矩阵
6 8.2 图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 一、图的邻接矩阵 1、无权值的有向图的邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图； 并且 A[i,j] = 1 , 如果i 至 j 有一条有向边；A[I,j]=0，如果 i 至 j 没有一条有向边。 有向图 邻接矩阵 B A D C E = E D C B A V = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 A (b) (a)
2、无权值的无向图的邻接矩阵 设无向图具有n个结点,则用n行n列的布尔矩阵A表示该无向图; 并且A[Li=1,如果至j有一条无向边;A[j=0,如果i至j没有一条无向边 无向图 邻接矩阵 3、有向图的加权邻接矩阵 设有向图具有n个结点,则用n行n列的矩阵A表示该有向图; 并且A[]=a,如果i至j有一条有向边且它的权值为a。A[i=空或其它标 志;如果i至j没有一条有向边。 带权图 接矩阵
7 2、无权值的无向图的邻接矩阵 设无向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该无向图； 并且 A[i,j]=1 , 如果i 至 j 有一条无向边；A[I,j]=0，如果 i 至 j 没有一条无向边。 无向图 邻接矩阵 2 1 4 3 5 6 = 80 0 70 0 40 50 0 70 80 30 0 50 20 0 40 0 20 30 A = 6 5 4 3 2 1 V (a) (b) 20 40 30 50 70 80 3、有向图的加权邻接矩阵 设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图； 并且 A[i,j]=a , 如果i 至 j 有一条有向边且它的权值为a。A[i,j] = ‘空 或其它标 志；如果 i 至 j 没有一条有向边。 带权图 邻接矩阵 2 1 4 3 5 = 5 4 3 2 1 V = 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 1 1 A (b) (a)
例1、无向图的邻接矩阵如何表示? 顶点表:V=(v1v2w3v4v5) A v2 邻接矩阵:A 345 分析1:无向图的邻接矩阵是对称的 分析2:顶点的度=第i行(列)中的个数 特别:完全图的邻接矩阵中,对角元素为0,其余全1
8 （ v1 v2 v3 v4 v5 ） v1 v2 v3 v4 v5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 分析1：无向图的邻接矩阵是对称的； 分析2：顶点i 的度＝第 i 行 (列) 中1 的个数； 特别：完全图的邻接矩阵中，对角元素为0，其余全1。 顶点表： V= 例1、无向图的邻接矩阵如何表示？ v1 v2 v3 v4 v5 A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 邻接矩阵： A=
例2:有向图的邻接矩阵如何表示? 顶点表:(v1v2v3v4) A 邻接矩阵: 234 注:在有向图的邻接矩阵中 第行含义:以结点v为尾的弧(即出度边); 第列含义:以结点v为头的弧(即入度边)。 分析1:有向图的邻接矩阵可能是不对称的。 分析2:顶点v的出度=第i元素之和,ODM)= A/illi 顶点v的入度=第列元素之和。IDM)=EAj∥ 顶点的度=第许行元素之和+第列元素之和 即:TD(v)=OD(ⅵ)+ID(v)
9 例2 ：有向图的邻接矩阵如何表示？ 分析1：有向图的邻接矩阵可能是不对称的。 分析2：顶点vi的出度=第i行元素之和，OD(vi )= A[ i ][j ] 顶点vi的入度=第i列元素之和。ID(vi )= A[ j ][i ] 顶点的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ) v1 v2 v3 v4 A 邻接矩阵： A= ( v1 v2 v3 v4 ) v1 v2 v3 v4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 注：在有向图的邻接矩阵中， 第i行含义：以结点vi为尾的弧(即出度边）； 第i列含义：以结点vi为头的弧(即入度边）。 顶点表： 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0
例3:有权图(即网络)的邻接矩阵如何表示? 顶点表:(v1v2v3v4v5v6 4邻接矩阵: 5 A 3 2 6 A 8 v4 G 5 5 5 v6 邻接矩阵法实现图的操作,如:求某顶点的度、判断顶点之 间是否有边〔弧)、找顶点的邻接点等等。 邻接矩阵个点需要m个单元存储边弧)空间效率为O(2) 对稀疏图而言尤其浪费空间
10 容易实现图的操作，如：求某顶点的度、判断顶点之 间是否有边（弧）、找顶点的邻接点等等。 n个顶点需要n*n个单元存储边(弧);空间效率为O(n2 )。 例3 ： 有权图（即网络）的邻接矩阵如何表示？ v1 v2 v3 v4 A v5 v6 5 8 4 9 7 5 5 6 1 3 以有向网为例： 邻接矩阵： ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ A = ( v1 v2 v3 v4 v5 v6 ) 邻接矩阵法优点： 邻接矩阵法缺点： 顶点表： 5 7 4 8 9 5 6 5 3 1 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 对稀疏图而言尤其浪费空间