数据结构-图(1)

1、第第7章章 图图 电子科技大学电子科技大学第第7章章 图图 树的存储结构：树的存储结构：n双亲表示法双亲表示法n孩子表示法孩子表示法n孩子兄弟表示法孩子兄弟表示法思路：思路：用二叉链表来表示树，但链表中的两个指针域含义不同。用二叉链表来表示树，但链表中的两个指针域含义不同。n左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；n右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。 data firstChild nextSibling指向左孩子指向左孩子指向右兄弟指向右兄弟双亲只管长子双亲只管长子长子连接兄弟长子连接兄弟第第7章章 图图 树和二叉树之间的转换：树和二叉树

2、之间的转换：方法：方法：加线加线抹线抹线旋转旋转 abeidfhgcabeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左第第7章章 图图 二叉树还原为树二叉树还原为树abeidfhgc要点：要点：把所有右孩子变为兄弟！把所有右孩子变为兄弟！ abeidfhgc第第7章章 图图 l森林转换为二叉树：将森林中的每棵树转换成相应的二叉树，森林转换为二叉树：将森林中的每棵树转换成相应的二叉树，形成若干个二叉树的森林；第一棵二叉树不动，从第二棵二形成若干个二叉树的森林；第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树叉树开始，依次把后一棵二叉树的根结点作为前

3、一棵二叉树根结点的右孩子，根结点的右孩子， 当所有二叉树连在一起后，所得到的二叉当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。树就是由森林转换得到的二叉树。 l二叉树还原为森林：将二叉树中根结点与其右孩子连线，及二叉树还原为森林：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成一组沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成一组孤立的二叉树；将孤立的二叉树依次还原成树孤立的二叉树；将孤立的二叉树依次还原成树第第7章章 图图 树的遍历：树的遍历：n先根遍历先根遍历等同于转换的二叉树进行等同于转换的二叉树进行先序遍历先序遍历n后根遍历后

4、根遍历-等同于转换的二叉树进行等同于转换的二叉树进行中序遍历中序遍历森林的遍历：森林的遍历：n先序遍历先序遍历等同于转换的二叉树进行等同于转换的二叉树进行先序遍历先序遍历n中序遍历中序遍历等同于转换的二叉树进行等同于转换的二叉树进行中序遍历中序遍历第第7章章 图图 哈夫曼树（哈夫曼树（Huffman）树是一类带权路径长度）树是一类带权路径长度(WPL)最短的树最短的树构造构造 Huffman树算法树算法1) 以权值分别为以权值分别为W1,W2的各结点，构成的各结点，构成n棵棵二叉树二叉树T1,T2,Tn并组成森林并组成森林F=T1,T2,Tn,其中每棵二叉树其中每棵二叉树 Ti仅有一个权值为仅

5、有一个权值为 Wi的根结点；的根结点；2) 在在F中选取两棵根结点权值最小的树作为左右子树构造中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和；上根结点的权值之和；3) 从从F中删除这两棵二叉树，同时将新二叉树加入到中删除这两棵二叉树，同时将新二叉树加入到F中中;4) 重复重复2)-3)步直到步直到F中只含一棵二叉树为止，这棵二叉树中只含一棵二叉树为止，这棵二叉树就是就是Huffman 树。树。第第7章章 图图 第第7章章 图图 7.4 图的应用图的应用 -最小生成树最小生成树 (无向

6、图无向图) -拓扑排序拓扑排序 (有向图，简介有向图，简介) -最短路径最短路径 (无向图无向图)第第7章章 图图 7.1 图的定义和术语图的定义和术语 图图(Graph)G由两个集合由两个集合V(Vertex)和和E(Edge)组成组成, 记为记为G=(V,E),其中其中V是顶点的有限集合是顶点的有限集合, 记为记为V(G), E是连接是连接V中两个中两个不同顶点不同顶点(顶点对顶点对)的边的有限集合的边的有限集合, 记为记为E(G)。 在图在图G中中,如果代表边的顶点对是无序的如果代表边的顶点对是无序的,则称则称G为为无向图无向图,无无向图中代表边的无序顶点对，通常用圆括号括起来向图中代表

7、边的无序顶点对，通常用圆括号括起来,用以表示一用以表示一条无向边。条无向边。 如：如：(vi,vj) 如果表示边的顶点对是有序的如果表示边的顶点对是有序的,则称则称G为为有向图有向图,在有向图中在有向图中代表边的顶点对，通常用尖括号括起来代表边的顶点对，通常用尖括号括起来 (称为称为弧弧)。如：。如： 1. 图的定义图的定义 ViVjViVj弧头弧头弧尾弧尾第第7章章 图图 有向图、无向图示例有向图、无向图示例 第第7章章 图图 本章不予讨论的图本章不予讨论的图第第7章章 图图 Internet 网分布图网分布图脑网络图脑网络图蛋白质相互作用图蛋白质相互作用图第第7章章 图图 2. 基本术语基

8、本术语 l完全图完全图(边达到最大边达到最大)、稀疏图与稠密图、稀疏图与稠密图n:图中顶点的个数图中顶点的个数; e:图中边或弧的数目。图中边或弧的数目。无向图其边数无向图其边数e的取值范围是的取值范围是0n(n-1)/2。 无向完全图无向完全图：有：有n(n-1)/2条边的无向图。条边的无向图。有向图其边数有向图其边数e的取值范围是的取值范围是0n(n-1)。 有向完全图有向完全图：有：有n(n-1)条边的有向图。条边的有向图。 稀疏图稀疏图：对于有很少条边或弧的图：对于有很少条边或弧的图(enlogn)， 反之称为反之称为稠密图稠密图。 第第7章章 图图 l子图子图有两个图有两个图G=(V

9、, E)和图和图G=(V, E), 若若V V且且E E, 则称图则称图G为为G的子图。的子图。l邻接点邻接点 :边的两个顶点对边的两个顶点对 (vi,vj) 和和 n无向图：无向图：vi和和vj互为邻接点互为邻接点；n有向图：有向图：vi和和vj互为邻接点互为邻接点，弧顶，弧顶(vj)是是弧尾弧尾(vi)的的出边邻接点出边邻接点，弧尾，弧尾(vi)是弧顶是弧顶(vj)的是的的是的入边邻接点入边邻接点； 1 3 0 2 4 (a) (b) 1 3 0 2 4 1 3 0 2 4 (c) 第第7章章 图图 l顶点的度、入度和出度顶点的度、入度和出度n在在无向图无向图中中,顶点所具有的边的数目称为

10、该顶点所具有的边的数目称为该顶点的度顶点的度。n在在有向图有向图中中,以顶点以顶点v为头的弧的数目为头的弧的数目,称为该顶点的称为该顶点的入度入度。以顶点以顶点v为尾的弧的数目为尾的弧的数目,称为该顶点的称为该顶点的出度出度。一个顶点的。一个顶点的入度与出度的和为该顶点的入度与出度的和为该顶点的度度。n一般地，若图一般地，若图G中有中有n个顶点，个顶点，e条边或弧，则图中顶点的条边或弧，则图中顶点的度与边的关系如下：度与边的关系如下： 2)(1niivTDeWhy?一个边被两个顶点分，一个边被两个顶点分，对于度来说有两次贡献对于度来说有两次贡献第第7章章 图图 l 权与网权与网 在实际应用中，

11、有时图的边或弧上往往与具有一定意义的在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做将这种带权的图叫做赋权图赋权图或或网网。 带权无向图的例子带权无向图的例子第第7章章 图图 l路径与回路路径与回路 无向图无向图G=(V,E)中从顶点中从顶点v到到v的路径是一个顶点序列的路径是一个顶点序列(v=vi0,vi1,vi2,vin=v)其中其中(vij-1, vij)E, 1

12、jn。如果图如果图G是有向图，是有向图，则路径也是有向的则路径也是有向的，顶点序列应满足，顶点序列应满足E， 1jn。n路径的长度路径的长度: 路径上经过的弧或边的数目；路径上经过的弧或边的数目；n回路回路或或环环: 第一个顶点和最后一个顶点相同时；第一个顶点和最后一个顶点相同时；n简单路径简单路径:表示路径的顶点序列中的顶点各不相同；表示路径的顶点序列中的顶点各不相同；n简单回路简单回路:除了第一个和最后一个顶点外，其余各顶点均不除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路。重复出现的回路。 n例例4：在图：在图a中，中，V0,V1,V2,V3 是简单路径；是简单路径； V0,V

13、1,V2,V4,V1不是简不是简单路径；在图单路径；在图b中，中， V0,V2,V3,V0是简单回路，也是一个环。是简单回路，也是一个环。V0V3V2V1V0V4V3V1V2(a)(b)第第7章章 图图 l连通图连通图: 无向图中任意两个顶点都连通无向图中任意两个顶点都连通连通分量连通分量:无向图中的极大连通子图。无向图中的极大连通子图。l强连通图强连通图: 有向图每对顶点之间都存在路径有向图每对顶点之间都存在路径强连通分量强连通分量: 有向图的极大强连通子图。有向图的极大强连通子图。 V0V4V3V1V2连通图V0V4V3V1非连通图V2V0V4V3V1强连通图V0V4V3V1非强连通图第第

14、7章章 图图 l生成树生成树: 连通图的生成树是一个连通图的生成树是一个，它含有图，它含有图中全部顶点，但只有足以构成一棵树的中全部顶点，但只有足以构成一棵树的n-1条边。条边。 en-1 一定有回路一定有回路 e=n-1 不一定都是图的生成树不一定都是图的生成树 第第7章章 图图 例例2：有：有n个顶点的有向强连通图最多需要多少条边？最少需要个顶点的有向强连通图最多需要多少条边？最少需要多少条边？多少条边？ 答案：有答案：有n个顶点的有向强连通图最多有个顶点的有向强连通图最多有n(n-1)条边条边( (构成构成一个有向完全图的情况一个有向完全图的情况) )；最少有；最少有n条边条边( (n个

15、顶点依次首尾相接个顶点依次首尾相接构成一个环的情况构成一个环的情况) )。 例例1：G是是非连通无向图非连通无向图，共，共28条边，至少有多少个顶点？（条边，至少有多少个顶点？（注注意审题意审题）答案：答案：9个顶点个顶点第第7章章 图图 7.2 图的存储结构图的存储结构1. 邻接矩阵表示法（数组表示法）邻接矩阵表示法（数组表示法） l图图G是一个具有是一个具有n个顶点的无权图，个顶点的无权图，G的邻接矩阵是具有如下的邻接矩阵是具有如下性质的性质的nn矩阵矩阵A： 1, ,), , 0, ijijv vv vVA i j若(或其它l若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具有如

16、下性个顶点的网，则它的邻接矩阵是具有如下性质的质的nn矩阵矩阵A：, ,), , , ijijijwv vv vVA i j若(或其它第第7章章 图图 第第7章章 图图 第第7章章 图图 邻接矩阵表示法类型描述邻接矩阵表示法类型描述 :define MAX_VERTEX_NUM 20 define INFINITY INT_MAX typedef enumDG, DN, UDG, UDN GraphKind; typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX

17、_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; GraphKind kind; MGraph;第第7章章 图图 n图的邻接矩阵图的邻接矩阵。的邻接矩阵一定是一个的邻接矩阵一定是一个。存储可采用。存储可采用。n弱邻接矩阵是一个弱邻接矩阵是一个, ,可以采用可以采用表的方法存储邻接矩阵。表的方法存储邻接矩阵。对于无向图对于无向图, ,邻接矩阵的第邻接矩阵的第i i行行( (或第或第i i列列) )非零元素非零元素( (或或非非元素元素) )的个数正好是第的个数正好是第i

18、i个顶点个顶点v vi i的度。对于有向图的度。对于有向图, ,邻接矩阵的邻接矩阵的第第i i行行( (或第或第i i列列) )非零元素非零元素( (或非或非元素元素) )的个数正好是第的个数正好是第i i个顶点个顶点v vi i的的出度出度( (或入度或入度) )。用邻接矩阵方法存储图用邻接矩阵方法存储图, ,容易确定图中任意两个顶点之间是容易确定图中任意两个顶点之间是否有边相连。但是否有边相连。但是, ,要确定图中有多少条边要确定图中有多少条边, ,则必须按行、按列对每则必须按行、按列对每个元素进行检测个元素进行检测, ,所花费的时间代价很大。所花费的时间代价很大。第第7章章 图图 2.2

19、.邻接表存储方法：图的链式存储结构邻接表存储方法：图的链式存储结构 在邻接表中在邻接表中, ,对图中每个顶点建立一个单链表对图中每个顶点建立一个单链表, ,第第i i个单链个单链表中的结点表示依附于顶点表中的结点表示依附于顶点v vi i的边的边( (对有向图是以顶点对有向图是以顶点v vi i为尾为尾的弧的弧) )。每个单链表上附设一个表头结点。表结点和表头结点。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：的结构如下：adjvexnextarcinfodatafirstarc表结点表结点表头结点表头结点ndata存储顶点存储顶点vi的名称或其他信息的名称或其他信息; first

20、arc指向链表中第一指向链表中第一个结点。个结点。n adjvex指示与顶点指示与顶点vi邻接的点在图中的位置邻接的点在图中的位置;nextarc指示下指示下一条边或弧的结点一条边或弧的结点; info存储与边或弧相关的信息存储与边或弧相关的信息,如权值等。如权值等。第第7章章 图图 第第7章章 图图 邻接表存储结构的类型定义：邻接表存储结构的类型定义：typedef struct ArcNode/表结点结构类型表结点结构类型int adjvex; /该弧该弧(边边)的终点位置的终点位置 struct ArcNode *nextarc; /指向下一条弧的指针指向下一条弧的指针 InfoType

21、 info; /该弧的相关信息，如权重该弧的相关信息，如权重 ArcNode;typedef struct Vnode /头结点的类型头结点的类型Vertex data; /顶点信息顶点信息 ArcNode *firstarc; /指向第一条弧指向第一条弧 VNode, AdjListMAX_VERTEX_NUM;typedef struct /邻接表邻接表 AdjList vertices; int vexnum, arcnum; /图中顶点数图中顶点数n和边数和边数e int kind; /图的类型图的类型 ALGraph; 第第7章章 图图 邻接表的特点如下邻接表的特点如下：n邻接表邻接

22、表。这是因为在每个顶点对应的单链表中。这是因为在每个顶点对应的单链表中, ,各各边结点的链接次序可以是任意的边结点的链接次序可以是任意的, ,取决于建立邻接表的算法以取决于建立邻接表的算法以及边的输入次序。及边的输入次序。n对于有对于有n个顶点和个顶点和e条边的无向图条边的无向图, ,其邻接表有其邻接表有n个头结点和个头结点和2e个个表结点。显然表结点。显然, ,在总的边数小于在总的边数小于n(n-1)/2的情况下的情况下, ,邻接表比邻邻接表比邻接矩阵要接矩阵要。n对于对于, ,邻接表的顶点邻接表的顶点vi对应的第对应的第i i个链表的表结点数目正个链表的表结点数目正好是顶点好是顶点vi的的

23、。n对于对于, ,邻接表的顶点邻接表的顶点vi对应的第对应的第i i个链表的表结点数目仅个链表的表结点数目仅仅是仅是vi的的。其入度为邻接表。其入度为邻接表中所有中所有adjvex域值为域值为i的表结点数目。（的表结点数目。（）第第7章章 图图 图图G1的逆邻接表表示法的逆邻接表表示法 3. 十字链表十字链表 (课后自学课后自学) 4. 邻接多重表邻接多重表 (课后自学课后自学)第第7章章 图图 7.3 图图 的的 遍遍 历历 n图遍历的概念图遍历的概念: :从给定图中任意指定的顶点从给定图中任意指定的顶点( (称为初始点称为初始点) )出发出发, ,按照某种按照某种搜索方法沿着图的边访问图中

24、的所有顶点搜索方法沿着图的边访问图中的所有顶点, ,使每个顶点仅被访问一次使每个顶点仅被访问一次, ,这这个过程称为个过程称为图的遍历图的遍历。n对于图遍历，需注意以下两点：对于图遍历，需注意以下两点：n如果给定图是连通的无向图或者是强连通的有向图如果给定图是连通的无向图或者是强连通的有向图, ,则遍历过程则遍历过程一次就能完成一次就能完成, ,并可按访问的先后顺序得到由该图所有顶点组成并可按访问的先后顺序得到由该图所有顶点组成的一个序列。的一个序列。n为避免同一顶点被访问多次为避免同一顶点被访问多次, ,设一个辅助数组设一个辅助数组visited0.n-1,visited0.n-1,它的初始

25、值置为它的初始值置为0,0,一旦访问了顶点一旦访问了顶点vi,vi,便置便置visitedivisitedi为为1 1或者为或者为被访问时的次序号被访问时的次序号n根据搜索方法的不同根据搜索方法的不同, ,图的遍历方法有两种：图的遍历方法有两种：n深度优先搜索法深度优先搜索法DFS(Depth-First Search)n广度优先搜索法广度优先搜索法BFS (Breadth-First Search) 第第7章章 图图 深度优先搜索遍历深度优先搜索遍历( (过程过程) )：n访问指定的某顶点访问指定的某顶点V V，将，将V V作为当前顶点作为当前顶点n访问当前顶点的下一未被访问过的邻接点访问当

26、前顶点的下一未被访问过的邻接点n重复重复1 1和和2 2，直到当前顶点的所有邻接点都被访问点。，直到当前顶点的所有邻接点都被访问点。n沿搜索路径回退，退到尚有邻接点未被访问过的某沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点作为当前结点，重复以上步骤，直结点，将该结点作为当前结点，重复以上步骤，直到所有顶点被访问过的为止。到所有顶点被访问过的为止。显然显然, ,这个遍历过程是个递归过程。这个遍历过程是个递归过程。第第7章章 图图 图的深度优先搜索过程图示图的深度优先搜索过程图示 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1例：求图例：求图G G以以

27、V0V0起点的的起点的的深深度优先序列：度优先序列：l V0,V1,V3,V7,V4,V2,V5,V6这是其中一种遍历这是其中一种遍历方案所经过的路径方案所经过的路径 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4深到底深到底V0V1V3V7V4（V7V3V1均已访问）均已访问）深到底深到底V2V5V6回退回退深到底深到底回退回退访问访问u 由于没有规定访问邻接点的顺序，深度优先由于没有规定访问邻接点的顺序，深度优先遍历序列不唯一遍历序列不唯一u 如果将图顶点的邻接点看作二叉树结点的左、如果将图顶点的邻接点看作二叉树结点的左、右孩子，深度优先遍历与先序遍历很类似

28、右孩子，深度优先遍历与先序遍历很类似第第7章章 图图 int visitedMAX; void DFSTraverse(Graph G) for (v=0; vG.vexnum; +v) visitedv = FALSE ; for( v=0; v=0; w=) if(!visitedw) DFS(G,w); 返回返回v的临邻接点，返回的临邻接点，返回v的相对于的相对于w的邻接点的邻接点第第7章章 图图 算法分析算法分析:n假设图中有假设图中有 n 个顶点，个顶点，e 条边。遍历过程实质上是对每个顶条边。遍历过程实质上是对每个顶点查找邻接点的过程。点查找邻接点的过程。n如果用邻接表表示图，沿如果用邻接表表示图，沿 firsarc链可以找到某个顶点链可以找到某个顶点 v 的所的所有邻接顶点有邻接顶点 w。由于总共有。由于总共有 2e 个边结点，所以扫描边的时间个边结点，所以扫描边的时间为为O(e)。所以遍历图的时间复杂性为。所以遍历图的时间复杂性为O(n+e)。n如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为需时间为O(n)，则遍历图中所有的