数据结构6图.ppt

图的基本概念及基本术语 图的存储结构 图的遍历 图的应用图属于非线性数据结构的一种。图属于非线性数据结构的一种。图属于非线性数据结构的一种。图属于非线性数据结构的一种。树结构中数据元素之间的关系：树结构中数据元素之间的关系：树结构中数据元素之间的关系：树结构中数据元素之间的关系：一对多一对多一对多一对多的关系。的关系。的关系。的关系。图结构中数据元素之间的关系：图结构中数据元素之间的关系：图结构中数据元素之间的关系：图结构中数据元素之间的关系：多对多多对多多对多多对多的关系。的关系。的关系。的关系。12/20/20221第第6章章 图图6.16.1、图的基本概念、图的基本概念 图是由结点集合图是由结点集合图是由结点集合图是由结点集合(vertex)(vertex)及结点间的关系及结点间的关系及结点间的关系及结点间的关系集合组成的一种数据结构集合组成的一种数据结构集合组成的一种数据结构集合组成的一种数据结构：GraphGraph(V V,E E)其中其中其中其中 V V=x x|x x 某个数据对象某个数据对象某个数据对象某个数据对象 是结点的有穷是结点的有穷是结点的有穷是结点的有穷非空集合；非空集合；非空集合；非空集合；E E=(=(x x,y y)|)|x x,y y V V 是结点之间关系的有是结点之间关系的有是结点之间关系的有是结点之间关系的有穷集合，也叫做边穷集合，也叫做边穷集合，也叫做边穷集合，也叫做边(edge)(edge)集合。集合。集合。集合。1.1.1.1.图：图：图：图：12/20/20222第第6章章 图图n n有向图有向图有向图有向图 GraphGraph(V V,E E)V V:是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；E E:有向有向边边边边(弧弧)集合。集合。集合。集合。弧是结点的有序对弧是结点的有序对.例例:表示表示ViVjn n无向图无向图无向图无向图 GraphGraph(V V,E E)V V:是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；是结点的有穷非空集合；E E:是结点的是结点的是结点的是结点的无向无向边边边边(无序对无序对无序对无序对)的集合的集合的集合的集合例例例例:(Vi,VjVi,Vj)ViVi与与VjVj相邻相邻;(Vi,VjVi,Vj)=()=(Vj,ViVj,Vi)VjVj:弧头弧头Vi:Vi:弧尾弧尾ViVj12/20/20223第第6章章 图图 ADT GraphADT Graph 数据对象数据对象V:V:一个集合，集合中所有元素具有相同的特性。一个集合，集合中所有元素具有相同的特性。数据关系数据关系R R：R=VRR=VR VR=x VR=|Py|P（x x，y y）（x x，yVyV）基本操作：基本操作：（1 1）CreateGraphCreateGraph（G G）：）：创建图创建图G G。（2 2）DestoryGraphDestoryGraph（G G）：）：销毁图销毁图G G。（3 3）LocateVertexLocateVertex（G G，v v）：确确定定顶顶点点v v在在图图G G中中的的位位置置。若图若图G G中没有顶点中没有顶点v v，则函数则函数值为值为“空空”。（4 4）GetVertexGetVertex（G G，i i）：取取出出图图G G中中的的第第i i个个顶顶点点的的值值。若若i i大于图大于图G G中顶点数，则函数值为中顶点数，则函数值为“空空”。12/20/20224第第6章章 图图 （5 5）FirstAdjVertexFirstAdjVertex（G G，v v）：求求图图G G中中顶顶点点v v的的第第一一个个邻邻接接点点。若若v v无无邻邻接接点点或或图图G G中中无无顶顶点点v v，则则函函数数值值为为“空空”。（6 6）NextAdjVertexNextAdjVertex（G G，v v，w w）：已已知知w w是是图图G G中中顶顶点点v v的的某某个个邻邻接接点点，求求顶顶点点v v的的下下一一个个邻邻接接点点（紧紧跟跟在在w w后后面面）。若若w w是是v v的最后一个邻接点，的最后一个邻接点，则函数值为则函数值为“空空”。（7 7）InsertVertexInsertVertex（G G，u u）：）：在图在图G G中增加一个顶点中增加一个顶点u u。（8 8）DeleteVertexDeleteVertex（G G，v v）：删除图）：删除图G G的顶点的顶点v v及与顶点及与顶点v v相关联的弧。相关联的弧。（9 9）InsertArcInsertArc（G G，v v，w w）：在图）：在图G G中增加一条从顶点中增加一条从顶点v v到顶点到顶点w w的弧。的弧。（1010）DeleteArcDeleteArc（G G，v v，w w）：）：删除图删除图G G中从顶点中从顶点v v到顶到顶点点w w的弧。的弧。（1111）TraverseGraphTraverseGraph（G G）：）：按照某种次序，按照某种次序，对图对图G G的的每个结点访问一次且仅访问一次。每个结点访问一次且仅访问一次。12/20/20225第第6章章 图图完全图完全图完全图完全图:对有对有n n个结点的图，个结点的图，无向图无向图:任意两结点都有一条边，即边数为任意两结点都有一条边，即边数为:n(n-1)/2n(n-1)/2，则称其为无向完全图；则称其为无向完全图；邻接结点邻接结点邻接结点邻接结点:无向图无向图:若（若（v vi i,v,vj j）E E，则称结点则称结点v vi i和和v vj j互为邻接点；互为邻接点；或称或称v vi i和和v vj j相邻接；或称边（相邻接；或称边（v vi i,v,vj j）关联于结点关联于结点v vi i和和v vj j；或；或称称边（边（v vi i,v,vj j）与结点与结点v vi i和和v vj j相关联。相关联。有向图：有向图：若若 E,E,则称结点则称结点v vj j 是是v vi i 的的邻接点。邻接点。2.2.基本概念基本概念12/20/20226第第6章章 图图结点的度：结点的度：结点的度：结点的度：一个结点一个结点一个结点一个结点v v的度是与它相关联的边的条数的度是与它相关联的边的条数的度是与它相关联的边的条数的度是与它相关联的边的条数 记作记作记作记作TD(TD(v v)。无向图：无向图：即为该结点相连的边的个数。即为该结点相连的边的个数。有向图：有向图：依附在某结点的弧的数目。依附在某结点的弧的数目。结点的入度结点的入度：以该结点为弧头的弧的数目。以该结点为弧头的弧的数目。是以是以是以是以 v v 为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数为终点的有向边的条数,记作记作记作记作 ID(ID(v v);结点的出度：结点的出度：以该结点为弧尾的弧的数目。以该结点为弧尾的弧的数目。是以是以是以是以 v v 为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数为始点的有向边的条数,记作记作记作记作 OD(OD(v v)。有向图：有向图：任意两结点都有两条方向相反的弧，任意两结点都有两条方向相反的弧，即弧数为即弧数为n(n-1)n(n-1)，则称其为有向完全图。则称其为有向完全图。12/20/20227第第6章章 图图TD(TD(v v)=ID(v)+OD(v)=ID(v)+OD(v)162543abcdefTD(1)=3 TD(2)=3TD(3)=3 TD(4)=2TD(5)=2 TD(6)=1ID(a)=1 OD(a)=2 TD(a)=3 ID(b)=1 OD(b)=2 TD(b)=3ID(c)=2 OD(c)=0 TD(c)=2 ID(d)=1 OD(d)=1 TD(d)=2ID(e)=0 OD(e)=1 TD(e)=1 ID(f)=1 OD(f)=0 TD(f)=112/20/20228第第6章章 图图子图子图子图子图 ：设有两个图设有两个图设有两个图设有两个图 GG(V V,E E)和和和和 GG(V V,E E)。若若若若 V V V V 且且且且 E E E E,则称则称则称则称 图图图图G G 是是是是 图图图图G G 的子图。的子图。的子图。的子图。0123(a)G1(a)G10123G1G1的子图的子图012G1G1的子图的子图0123G1G1的子图的子图01201201212(b)G2(b)G2G2G2的子图的子图G2G2的子图的子图G2G2的子图的子图12/20/20229第第6章章 图图路径路径路径路径:在图在图 G G(V V,E E)中中,若存在一个结点序列若存在一个结点序列 v vp p1 1,v vp p2 2,v vpmpm，使得使得(v vi i,v vp p1 1)、(v vp p1 1,v vp p2 2)、.、(v vpmpm,v vj j)均属于均属于E E，则称结点则称结点v vi i到到v vj j存在一存在一 条路径。若一条路径上除了条路径。若一条路径上除了v vi i 和和v vj j 可可以相同外，其余结点均不相同，则称此路径为一条以相同外，其余结点均不相同，则称此路径为一条简单路径简单路径 。起点和终点相同的路径称为。起点和终点相同的路径称为简单回路简单回路或简单环。或简单环。12/20/202210第第6章章 图图图的连通图的连通 在在无向图无向图G G中，若两个结点中，若两个结点v vi i和和v vj j之间有路径存之间有路径存在，则称在，则称v vi i 和和v vj j 是连通的。若是连通的。若G G中任意两个结点都是连通中任意两个结点都是连通的，则称的，则称G G为为连通图连通图。非连通图的极大连通子图叫做非连通图的极大连通子图叫做连通分连通分量量。强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中,若对于每一若对于每一 对结对结点点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图。非强连通图的极大强连通强连通图。非强连通图的极大强连通 子图叫做子图叫做强连通分量。强连通分量。权权权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。称之为权。网络网络网络网络 这种带权图叫做。这种带权图叫做。12/20/202211第第6章章 图图1345213452V=1,2,3,4,5E=(1,2),(1,3),(1,4),(2,4),(4,5)V=1,2,3,4,5E=,无向图无向图有向图有向图连通图连通图非连通图非连通图1345267H1H1连通分量连通分量H2H2连通分量连通分量12/20/202212第第6章章 图图132强连通图强连通图非强连通图非强连通图5134213425强连通分量强连通分量H1H1强连通分量强连通分量H2H212/20/202213第第6章章 图图12356874107966712315163045ABDCE6035804075网络网络12/20/202214第第6章章 图图 生成树生成树生成树生成树 一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在一个连通图的生成树是它的极小连通子图，在n n个个个个结点的情形下，有结点的情形下，有结点的情形下，有结点的情形下，有n n-1-1条边。条边。条边。条边。n n不予讨论的图不予讨论的图不予讨论的图不予讨论的图 包含结点到其自身的边；一条边包含结点到其自身的边；一条边包含结点到其自身的边；一条边包含结点到其自身的边；一条边在图中重复出现在图中重复出现在图中重复出现在图中重复出现12/20/202215第第6章章 图图6.2、图的存储结构、图的存储结构n n在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个在图的邻接矩阵表示中，有一个记录各个结点信息记录各个结点信息记录各个结点信息记录各个结点信息的的的的结点结点结点结点表；表；表；表；还有一个还有一个还有一个还有一个表示各个结点之间关系表示各个结点之间关系表示各个结点之间关系表示各个结点之间关系的的的的邻接矩阵邻接矩阵邻接矩阵邻接矩阵。n n设图设图设图设图 A=(A=(V V,E E)是一个有是一个有是一个有是一个有 n n 个结点的图，则图的邻接矩阵个结点的图，则图的邻接矩阵个结点的图，则图的邻接矩阵个结点的图，则图的邻接矩阵是一个二维数组是一个二维数组是一个二维数组是一个二维数组 A A.Edge.Edge n n n n，定义：定义：定义：定义：邻接矩阵邻接矩阵(Adjacency Matrix)1.顺序存储顺序存储12/20/202216第第6章章 图图0123A.Edge=01324567A.Edge=V=0,1,2,3V=0,1,2,3,4,5,6,712/20/202217第第6章章 图图网络的邻接矩阵网络的邻接矩阵12/20/202218第第6章章 图图w w无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的，无向图的邻接矩阵是对称的，w w有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。w w在无向图中在无向图中在无向图中在无向图中,统计第统计第统计第统计第i i i i 行行行行(列列列列)1)1)1)1的个数可得结点的个数可得结点的个数可得结点的个数可得结点i i i i 的度。的度。的度。的度。w w在有向图中在有向图中在有向图中在有向图中,统计第统计第统计第统计第i i i i 行行行行1 1 1 1的个数可得结点的个数可得结点的个数可得结点的个数可得结点i i i i的出度，统的出度，统的出度，统的出度，统计第计第计第计第j j j j 列列列列1 1 1 1的个数可得结点的个数可得结点的个数可得结点的个数可得结点j j j j 的入度。的入度。的入度。的入度。w w属于静态存储方法。不易扩充。属于静态存储方法。不易扩充。属于静态存储方法。不易扩充。属于静态存储方法。不易扩充。w w与结点个数有关，与边（弧）无关。会出现稀疏矩阵。与结点个数有关，与边（弧）无关。会出现稀疏矩阵。与结点个数有关，与边（弧）无关。会出现稀疏矩阵。与结点个数有关，与边（弧）无关。会出现稀疏矩阵。邻接矩阵的特点：邻接矩阵的特点：12/20/202219第第6章章 图图2.链接存储链接存储邻接表邻接表(Adjacency List):n顺序存储结构和链接存储结构结合顺序存储结构和链接存储结构结合n顺序存储每个结点。顺序存储每个结点。n把与某个结点邻接的所有结点都链接在一把与某个结点邻接的所有结点都链接在一个单链表上。个单链表上。结点数据结点数据指针指针结点号结点号指针指针12/20/202220第第6章章 图图无向图的邻接表无向图的邻接表ABCD12/20/202221第第6章章 图图把同一个结点发出的边链接在同一个边链表中，链表的把同一个结点发出的边链接在同一个边链表中，链表的把同一个结点发出的边链接在同一个边链表中，链表的把同一个结点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做每一个结点代表一条边，叫做每一个结点代表一条边，叫做每一个结点代表一条边，叫做边结点边结点边结点边结点，结点中保存有与，结点中保存有与，结点中保存有与，结点中保存有与该边相关联的另一结点的结点下标该边相关联的另一结点的结点下标该边相关联的另一结点的结点下标该边相关联的另一结点的结点下标 destdest 和指向同一链表和指向同一链表和指向同一链表和指向同一链表中下一个边结点的指针中下一个边结点的指针中下一个边结点的指针中下一个边结点的指针 linklink。有向图的邻接表有向图的邻接表ABCDE12/20/202222第第6章章 图图带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 costcost。结点结点结点结点 i i 的边链表的表头指针的边链表的表头指针的边链表的表头指针的边链表的表头指针 adjadj 在结点表的下标在结点表的下标在结点表的下标在结点表的下标为为为为 i i 的结点记录中，该记录还可保存该结点的其的结点记录中，该记录还可保存该结点的其的结点记录中，该记录还可保存该结点的其的结点记录中，该记录还可保存该结点的其它信息。它信息。它信息。它信息。在邻接表的边链表中，在邻接表的边链表中，在邻接表的边链表中，在邻接表的边链表中，各个边结点的链入顺序任意，各个边结点的链入顺序任意，各个边结点的链入顺序任意，各个边结点的链入顺序任意，视边结点输入次序而定。视边结点输入次序而定。视边结点输入次序而定。视边结点输入次序而定。设图中有设图中有设图中有设图中有 n n 个结点，个结点，个结点，个结点，e e 条边，则条边，则条边，则条边，则用邻接表表示无用邻接表表示无用邻接表表示无用邻接表表示无向图时向图时向图时向图时，需要，需要，需要，需要 n n 个结点，个结点，个结点，个结点，2 2e e 个边结点；用个边结点；用个边结点；用个边结点；用邻接表邻接表邻接表邻接表表示有向图时表示有向图时表示有向图时表示有向图时，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需，若不考虑逆邻接表，只需 n n 个结个结个结个结点，点，点，点，e e 个边结点。个边结点。个边结点。个边结点。12/20/202223第第6章章 图图邻接表邻接表特点：特点：n仍为结点之间邻接关系仍为结点之间邻接关系n节省空间节省空间n结点的度：结点的度：无向图：无向图：为该结点的单链表中结点数目。为该结点的单链表中结点数目。有向图：有向图：出度：出度：为该结点的单链表中结点数目。为该结点的单链表中结点数目。入度：入度：扫描整个邻接表的单链表，为该结扫描整个邻接表的单链表，为该结点出现的次数。点出现的次数。12/20/202224第第6章章 图图网络网络(带权图带权图)的邻接表的邻接表此外此外,十字链表和邻接多重表存储法十字链表和邻接多重表存储法.(.(自学自学)12/20/202225第第6章章 图图6.3、图的遍历、图的遍历n n从已给的从已给的从已给的从已给的连通图连通图连通图连通图中某一结点出发，沿着一些边访遍中某一结点出发，沿着一些边访遍中某一结点出发，沿着一些边访遍中某一结点出发，沿着一些边访遍图中所有的结点，且使每个结点仅被访问一次，就图中所有的结点，且使每个结点仅被访问一次，就图中所有的结点，且使每个结点仅被访问一次，就图中所有的结点，且使每个结点仅被访问一次，就叫做图的叫做图的叫做图的叫做图的遍历遍历遍历遍历 (Graph Traversal(Graph Traversal)。n n图中可能存在图中可能存在图中可能存在图中可能存在回路回路回路回路，且图的任一结点都可能与其它，且图的任一结点都可能与其它，且图的任一结点都可能与其它，且图的任一结点都可能与其它结点相通，在访问完某个结点之后可能会沿着某些结点相通，在访问完某个结点之后可能会沿着某些结点相通，在访问完某个结点之后可能会沿着某些结点相通，在访问完某个结点之后可能会沿着某些边又回到了曾经访问过的结点。边又回到了曾经访问过的结点。边又回到了曾经访问过的结点。边又回到了曾经访问过的结点。n n为了避免重复访问，可设置一个标志结点是否被访为了避免重复访问，可设置一个标志结点是否被访为了避免重复访问，可设置一个标志结点是否被访为了避免重复访问，可设置一个标志结点是否被访问过的辅助数组问过的辅助数组问过的辅助数组问过的辅助数组 visitedvisited ，它的初始状态为它的初始状态为它的初始状态为它的初始状态为 0 0，在图的遍历过程中，一旦某一个结点，在图的遍历过程中，一旦某一个结点，在图的遍历过程中，一旦某一个结点，在图的遍历过程中，一旦某一个结点 i i 被访问，被访问，被访问，被访问，就立即让就立即让就立即让就立即让 visitedvisited i i 为为为为 1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。12/20/202226第第6章章 图图1.深度优先搜索深度优先搜索DFS(Depth First Search)DFS DFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后，由后，由后，由后，由 v v 出发，访问出发，访问出发，访问出发，访问它的任一邻接顶点它的任一邻接顶点它的任一邻接顶点它的任一邻接顶点 ww1 1；再从；再从；再从；再从 ww1 1 出发，访问与出发，访问与出发，访问与出发，访问与 ww1 1邻接的还邻接的还邻接的还邻接的还没有访问过的顶点没有访问过的顶点没有访问过的顶点没有访问过的顶点 ww2 2；然后再从；然后再从；然后再从；然后再从 ww2 2 出发，进行类似的访问，出发，进行类似的访问，出发，进行类似的访问，出发，进行类似的访问，如此进行下去，直至到达结点如此进行下去，直至到达结点如此进行下去，直至到达结点如此进行下去，直至到达结点 u u的所有邻接结点都被访问的所有邻接结点都被访问的所有邻接结点都被访问的所有邻接结点都被访问过为止。接着，退回一步，退到前一次刚访问过的结点，看过为止。接着，退回一步，退到前一次刚访问过的结点，看过为止。接着，退回一步，退到前一次刚访问过的结点，看过为止。接着，退回一步，退到前一次刚访问过的结点，看是否还有其它没有被访问的邻接结点。如果有，则访问此结是否还有其它没有被访问的邻接结点。如果有，则访问此结是否还有其它没有被访问的邻接结点。如果有，则访问此结是否还有其它没有被访问的邻接结点。如果有，则访问此结点，之后再从此结点出发，进行与前述类似的访问；如果没点，之后再从此结点出发，进行与前述类似的访问；如果没点，之后再从此结点出发，进行与前述类似的访问；如果没点，之后再从此结点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中有，就再退回一步进行搜索。重复上述过程，直到连通图中有，就再退回一步进行搜索。重复上述过程，直到连通图中有，就再退回一步进行搜索。重复上述过程，直到连通图中所有结点都被访问过为止。所有结点都被访问过为止。所有结点都被访问过为止。所有结点都被访问过为止。12/20/202227第第6章章 图图深度优先搜索的示例深度优先搜索的示例ABCDFEGHI123456789搜索搜索回退回退ABCDFEGHI123456789连通图的深度优先搜索递归算法连通图的深度优先搜索递归算法:(1)(1)访问结点访问结点v v，做标记，做标记;(2)(2)查找结点查找结点v v的任一邻接结点的任一邻接结点w w；(3)(3)若结点若结点v v邻接结点邻接结点w w存在存在,则继续执行则继续执行,否则结束否则结束;(4)(4)若结点若结点w w尚未被访问尚未被访问,则递归访问结点则递归访问结点w.w.(5)(5)查找结点查找结点w w的下一邻接结点的下一邻接结点 ；转到；转到(3)(3)12/20/202228第第6章章 图图例子遍历结果：遍历结果：A A、C C、B B、D D遍历过程有回退操作，用栈或递归实现遍历过程有回退操作，用栈或递归实现12/20/202229第第6章章 图图2.广度优先搜索广度优先搜索BFS(Breadth First Search)n n使用广度优先搜索在访问了起始结点使用广度优先搜索在访问了起始结点使用广度优先搜索在访问了起始结点使用广度优先搜索在访问了起始结点 v v 之后，之后，之后，之后，由由由由 v v 出发，依次访问出发，依次访问出发，依次访问出发，依次访问 v v 的各个未曾被访问过的各个未曾被访问过的各个未曾被访问过的各个未曾被访问过的邻接结点的邻接结点的邻接结点的邻接结点 ww1 1,ww2 2,wwt t，n n然后再顺序访问然后再顺序访问然后再顺序访问然后再顺序访问 ww1 1,ww2 2,wwt t 的所有还未的所有还未的所有还未的所有还未被访问过的邻接结点。再从这些访问过的结被访问过的邻接结点。再从这些访问过的结被访问过的邻接结点。再从这些访问过的结被访问过的邻接结点。再从这些访问过的结点出发，再访问它们的所有还未被访问过的点出发，再访问它们的所有还未被访问过的点出发，再访问它们的所有还未被访问过的点出发，再访问它们的所有还未被访问过的邻接结点，邻接结点，邻接结点，邻接结点，如此做下去，如此做下去，如此做下去，如此做下去，n n直到图中所有结点都被访问到为止。直到图中所有结点都被访问到为止。直到图中所有结点都被访问到为止。直到图中所有结点都被访问到为止。12/20/202230第第6章章 图图广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程ABCDFEGHI312546897广度优先生成树广度优先生成树ABCDFEGHI12435768912/20/202231第第6章章 图图 广度优先搜索是一种分层的搜索过程，每向前走一步可广度优先搜索是一种分层的搜索过程，每向前走一步可广度优先搜索是一种分层的搜索过程，每向前走一步可广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批结点，不像深度优先搜索那样有往回退的情能访问一批结点，不像深度优先搜索那样有往回退的情能访问一批结点，不像深度优先搜索那样有往回退的情能访问一批结点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法况。因此，广度优先搜索不是一个递归的过程，其算法况。因此，广度优先搜索不是一个递归的过程，其算法况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。也不是递归的。也不是递归的。也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记为了实现逐层访问，算法中使用了一个队列，以记为了实现逐层访问，算法中使用了一个队列，以记为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的结点，以便于向下忆正在访问的这一层和上一层的结点，以便于向下忆正在访问的这一层和上一层的结点，以便于向下忆正在访问的这一层和上一层的结点，以便于向下一层访问。一层访问。一层访问。一层访问。与深度优先搜索过程一样，为避免重复访问，需要与深度优先搜索过程一样，为避免重复访问，需要与深度优先搜索过程一样，为避免重复访问，需要与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组一个辅助数组一个辅助数组一个辅助数组 visitedvisited ，给被访问过的结点加标记。给被访问过的结点加标记。给被访问过的结点加标记。给被访问过的结点加标记。12/20/202232第第6章章 图图 最小生成树最小生成树 在在一一个个连连通通网网的的所所有有生生成成树树中中，各各边边的的代代价价之之和和最最小小的的那那棵棵生生成成树树称称为为该该连连通通网网的的最最小小代代价价生生成成树树（Minimum Minimum Cost Cost Spanning TreeSpanning Tree），），简称为简称为最小生成树最小生成树(MST)(MST)。最小生成树有如下重要性质：最小生成树有如下重要性质：设设 N=(V,N=(V,E)E)是是一一连连通通网网，U U 是是顶顶点点集集V V的的一一个个非非空空子子集集。若若（u u,v v）是是一一条条具具有有最最小小权权值值的的边边，其其中中uUuU，vV-UvV-U，则存在一棵包含边（则存在一棵包含边（u,vu,v）的最小生成树。的最小生成树。6.4、图的应用、图的应用12/20/202233第第6章章 图图 反证法证明：反证法证明：假假设设不不存存在在这这样样一一棵棵包包含含边边（u u,v v）的的最最小小生生成成树树。任任取取一一棵棵最最小小生生成成树树T T，将将（u u,v v）加加入入T T中中。根根据据树树的的性性质质，此此时时T T中中必必形形成成一一个个包包含含（u u,v v）的的回回路路，且且回回路路中中必必有有一一条条边边（u,u,vv）的的权权值值大大于于或或等等于于（u u,v v）的的权权值值。删删除除（u,u,vv），则则得得到到一一棵棵代代价价小小于于等等于于T T的的生生成成树树TT，且且TT为为一一棵棵包包含含边边（u u,v v）的的最最小小生生成成树树。这这与与假假设设矛矛盾盾，故该性质得证。故该性质得证。利利用用MSTMST性性质质来来生生成成一一个个连连通通网网的的最最小小生生成成树树。普普里里姆姆（PrimPrim）算算法法和和克克鲁鲁斯斯卡卡尔尔（KruskalKruskal）算算法法便便是是利利用用了了这这个个性质。性质。12/20/202234第第6章章 图图 1.1.普里姆算法普里姆算法 假设假设N=(V,E)N=(V,E)是连通网，是连通网，TETE为最小生成树中边的集合。为最小生成树中边的集合。（1 1）初始初始U=uU=u0 0(u(u0 0V),TE=V),TE=；（2 2）在在所所有有uU,uU,vV-UvV-U的的边边中中选选一一条条代代价价最最小小的的边边（u u0 0，v v0 0）并入集合并入集合TETE，同时将同时将v v0 0并入并入U U；（3 3）重复（重复（2 2），），直到直到U=VU=V为止。为止。此此时时，TETE中中必必含含有有n-1n-1条条边边，则则T=T=（V V，TETE）为为N N的的最最小生成树。小生成树。可以看出，可以看出，普利姆算法逐步增加普利姆算法逐步增加U U中的顶点，中的顶点，可称为可称为“加点法加点法”。12/20/202235第第6章章 图图【普里姆算法普里姆算法构造最小生成树的过程构造最小生成树的过程】(a)(a)连通网连通网V1V2V4V6V5V31V1V2V4V6V5V314V1V2V4V6V5V3142V1V2V4V6V5V314253V1V2V4V6V5V31425V1V2V4V6V5V35615566243(b)V3(b)V3入网入网(c)V6(c)V6入网入网(d)(d)V4入入网网(e)(e)V2入入网网(f)(f)V5入入网网12/20/202236第第6章章 图图2.2.克鲁斯卡尔算法克鲁斯卡尔算法 假假设设N=(V,N=(V,E)E)是是连连通通网网，将将N N中中的的边边按按权权值值从从小小到到大大的的顺序排列顺序排列:(1)(1)将将n n个顶点看成个顶点看成n n个集合；个集合；(2)(2)按按权权值值由由小小到到大大的的顺顺序序选选择择边边，所所选选边边应应满满足足两两个个顶顶点点不不在在同同一一个个顶顶点点集集合合内内，将将该该边边放放到到生生成成树树边边的的集集合合中。同时将该边的两个顶点所在的顶点集合合并；中。同时将该边的两个顶点所在的顶点集合合并；(3)(3)重重复复(2),(2),直直到到所所有有的的顶顶点点都都在在同同一一个个顶顶点点集集合合内内。可可以以看看出出，克克鲁鲁斯斯卡卡尔尔算算法法逐逐步步增增加加生生成成树树的的边边，与与普普里姆算法相比，可称为里姆算法相比，可称为”加边加边法法”。12/20/202237第第6章章 图图 例如，对于上例图所示的连通网，将所有的边按权值从例如，对于上例图所示的连通网，将所有的边按权值从小到大的顺序排列为：小到大的顺序排列为：权值权值 1 2 3 4 51 2 3 4 5 边边 (v(v1 1,v,v3 3)(v)(v4 4,v,v6 6)(v)(v2 2,v,v5 5)(v)(v3 3,v,v6 6)(v)(v1 1,v,v4 4)5 5 6 6 6 5 5 6 6 6 (v (v2 2,v,v3 3)(v)(v3 3,v,v4 4)(v)(v1 1,v,v2 2)(v)(v3 3,v,v5 5)(v5,v6)V1V2V4V6V5V35615566243V1V2V4V6V5V31(a)(v1,v3)(a)(v1,v3)V1V2V4V6V5V3123V1V2V4V6V5V312(b)(v1,v3)(v4,v6)(b)(v1,v3)(v4,v6)(c)(v1,v3)(v4,v6)(v2,v5)(c)(v1,v3)(v4,v6)(v2,v5)12/20/202238第第6章章 图图3V1V2V4V6V5V3142(d)(v1,v3)(v4,v6)(v2,v5)(v3,v6)(d)(v1,v3)(v4,v6)(v2,v5)(v3,v6)(e)(v1,v3)(v4,v6)(v2,v5)(v3,v6)(v2,v3)(e)(v1,v3)(v4,v6)(v2,v5)(v3,v6)(v2,v3)3V1V2V4V6V5V31425(v1,v3)(v4,v6)(v2,v5)(v3,v6)(v2,v3)经过筛选所得到边的顺序为：经过筛选所得到边的顺序为：在在选选择择第第五五条条边边时时，因因为为v v1 1、v v4 4已已经经在在同同一一集集合合内内，如如果果选选（v v1 1，v v4 4），则则会会形形成成回回路，路，所以选（所以选（v2v2，v3v3）。）。12/20/202239第第6章章 图图 设设N=(V,E),N=(V,E),最小生成树的初态为最小生成树的初态为T=T=（V,V,）。）。（1 1）待待选选的的边边：(2,(2,3)-5,3)-5,(2,(2,4)-6,4)-6,(3,(3,4)-6,4)-6,(2,(2,6)-11,6)-11,(4,(4,6)-14,6)-14,(1,(1,2)-16,2)-16,(4,(4,5)-18,(1,5)-19,(1,6)-21,(5,6)-335)-18,(1,5)-19,(1,6)-21,(5,6)-33。顶点集合状态：顶点集合状态：11，22，33，44，55，66。最小生成树的边的集合：最小生成树的边的集合：。3124565616211118336141931245612/20/202240第第6章章 图图 （2)2)从待选边中选一条权值最小的边为从待选边中选一条权值最小的边为:(2,3)-5:(2,3)-5。待待选选的的边边变变为为：(2,(2,4)-6,4)-6,(3,(3,4)-6,4)-6,(2,(2,6)-11,6)-11,(4,(4,6)-14,6)-14,(1,(1,2)-16,2)-16,(4,(4,5)-18,5)-18,(1,(1,5)-19,(1,6)-21,(5,6)-335)-19,(1,6)-21,(5,6)-33。顶顶点点集集合合状状态态变变为为：11，22，33，44，55，66。最小生成树的边的集合：最小生成树的边的集合：(2,3)(2,3)。312456512/20/202241第第6章章 图图 （3 3）从待选边中选一条权值最小的边为）从待选边中选一条权值最小的边为:(2,4)-6:(2,4)-6。待待选选的的边边变变为为：(3,(3,4)-6,4)-6,(2,(2,6)-11,6)-11,(4,(4,6)-14,6)-14,(1,(1,2)-16,2)-16,(4,(4,5)-185)-18,(1,(1,5)-19,5)-19,(1,(1,6)-6)-21,(5,6)-3321,(5,6)-33。顶点集合状态变为：顶点集合状态变为：11，22，3 3，44，55，66。最小生成树的边的集合：最小生成树的边的集合：(2,3),(2,4)(2,3),(2,4)。3124565612/20/202242第第6章章 图图 （4 4）从从待待选选边边中中选选一一条条权权值值最最小小的的边边为为:(3,(3,4)-64)-6，由由于于3 3、4 4在在同同一一个个顶顶点点集集合合22，3 3，44内内，故故放放弃弃。重重新新从从待待选边中选一条