数据结构图总结课件

图(Graph)图图的基本概念图的基本概念图的存储表示图的存储表示图的遍历与连通性图的遍历与连通性 最小生成树最小生成树最短路径最短路径 活动网络活动网络 图的基本概念图的基本概念n n图定义图定义 图是由顶点集合图是由顶点集合(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 的一条单向通的一条单向通路路,它是有方向的。它是有方向的。图的基本概念图的基本概念n n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无是有序的。在无向图中，顶点对向图中，顶点对(x,y)是无序的。是无序的。n n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点的有个顶点的有向图有向图有n(n-1)条边条边,则此图为完全有向图则此图为完全有向图00001111222265433 图的基本概念图的基本概念n n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。n n子图子图 设有两个图设有两个图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子的子图。图。n n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为称之为权。这种带权图叫做网络。权。这种带权图叫做网络。0123子图子图0130123023图的基本概念图的基本概念n n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的边的的度是与它相关联的边的条数。记作条数。记作TD(v)。在有向图中在有向图中,顶点的度等于顶点的度等于该顶点的入度与出度之和。该顶点的入度与出度之和。n n顶点顶点 v 的入度是以的入度是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度是以的出度是以 v 为始点的有为始点的有向边的条数向边的条数,记作记作 OD(v)。n n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1,vp2,vpm，到达到达顶点顶点vj。则称顶点序列则称顶点序列(vi vp1 vp2.vpm vj)为为从顶点从顶点vi 到顶点到顶点 vj 的路径。它经过的边的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的边。的边。图的基本概念图的基本概念n n路径长度路径长度 非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边边的条数。带权图的路径长度是指路径上各边的权之和。的权之和。n n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互相重复互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个与最后一个顶点顶点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。012301230123图的基本概念图的基本概念n n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到到顶点顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。如果是连通的。如果图中任意一对顶点都是连通的图中任意一对顶点都是连通的,则称此图是则称此图是连通连通图图。非连通图的极大连通子图叫做。非连通图的极大连通子图叫做连通分量连通分量。n n强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中,若对于若对于每一对顶点每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是则称此图是强连通图强连通图。非强连通图的极。非强连通图的极大强连通子图叫做大强连通子图叫做强连通分量强连通分量。n n生成树生成树 一个连通图的生成树是其极小连通子图，一个连通图的生成树是其极小连通子图，在在n个顶点的情形下，有个顶点的情形下，有n-1条边。条边。图的抽象数据类型图的抽象数据类型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)n n在图的邻接矩阵表示中，有一个记录各个顶点信息在图的邻接矩阵表示中，有一个记录各个顶点信息在图的邻接矩阵表示中，有一个记录各个顶点信息在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接的顶点表，还有一个表示各个顶点之间关系的邻接的顶点表，还有一个表示各个顶点之间关系的邻接的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。矩阵。矩阵。矩阵。n n设图设图设图设图 A=(V,E)A=(V,E)是一个有是一个有是一个有是一个有 n n 个顶点的图个顶点的图个顶点的图个顶点的图,图的邻图的邻图的邻图的邻接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组接矩阵是一个二维数组 A A.edgeedgen n n n，定义：定义：定义：定义：无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。n n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得的个数可得顶点顶点 i 的的出度出度，统计第，统计第 j 列列 1 的个数可的个数可得顶点得顶点 j 的的入度入度。n n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个的个数可得顶点数可得顶点i 的的度度。网络（带权图）的邻接矩阵网络（带权图）的邻接矩阵631295420318邻接表邻接表(Adjacency List)n n无向图的邻接表无向图的邻接表同一个顶点发出的边链接在同一个边链表同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边中，每一个链结点代表一条边(边结点边结点),结点中有另一顶点的下标结点中有另一顶点的下标 dest 和指针和指针 link。ABCDdata adjABCD0123dest linkdest link 130210 有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABCdata adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻接表逆邻接表(入边表入边表)102 011 网络网络(带权图带权图)的邻接表的邻接表BACD9528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)6n n带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 costcost。n n顶点顶点顶点顶点 i i 的边链表的表头指针的边链表的表头指针的边链表的表头指针的边链表的表头指针 adjadj 在顶点表的下标为在顶点表的下标为在顶点表的下标为在顶点表的下标为 i i 的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的datadata信息。信息。信息。信息。n n在邻接表的边链表中，各个边结点的链入顺序任意，在邻接表的边链表中，各个边结点的链入顺序任意，在邻接表的边链表中，各个边结点的链入顺序任意，在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。视边结点输入次序而定。视边结点输入次序而定。视边结点输入次序而定。n n设图中有设图中有设图中有设图中有 n n 个顶点，个顶点，个顶点，个顶点，e e 条边，则用邻接表表示无向条边，则用邻接表表示无向条边，则用邻接表表示无向条边，则用邻接表表示无向图时，需要图时，需要图时，需要图时，需要 n n 个顶点结点，个顶点结点，个顶点结点，个顶点结点，2 2e e 个边结点个边结点个边结点个边结点(同一条边同一条边同一条边同一条边会出现两次会出现两次会出现两次会出现两次)；用邻接表表示有向图时，若不考虑逆用邻接表表示有向图时，若不考虑逆用邻接表表示有向图时，若不考虑逆用邻接表表示有向图时，若不考虑逆邻接表，只需邻接表，只需邻接表，只需邻接表，只需 n n 个顶点结点，个顶点结点，个顶点结点，个顶点结点，e e 个边结点。个边结点。个边结点。个边结点。邻接多重表邻接多重表(Adjacency Multilist)n n在邻接多重表中在邻接多重表中,每一条边只有一个边结点。每一条边只有一个边结点。为有关边的处理提供了方便。为有关边的处理提供了方便。n n无向图的情形无向图的情形uu边结点的结构边结点的结构 mark vertex1 vertex2 path1 path2其中其中,mark 是记录是否处理过的标记是记录是否处理过的标记;vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接指域是链接指针针,指向下一条依附顶点指向下一条依附顶点vertex1的边；的边；path2 是是指向下一条依附顶点指向下一条依附顶点vertex2的边链接指针。的边链接指针。需要时还可设置一个存放与该边相关的权值的域需要时还可设置一个存放与该边相关的权值的域 cost。uu顶点结点的结构顶点结点的结构 存储顶点信息的结点表以顺序表方式组织存储顶点信息的结点表以顺序表方式组织,每一个顶点结点有两个数据成员：其中，每一个顶点结点有两个数据成员：其中，data 存放与该顶点相关的信息，存放与该顶点相关的信息，Firstout 是指示第是指示第一条依附该顶点的边的指针。在邻接多重表中一条依附该顶点的边的指针。在邻接多重表中,所有依附同一个顶点的边都链接在同一个单链所有依附同一个顶点的边都链接在同一个单链表中。表中。data Firstout从顶点从顶点从顶点从顶点 i i 出发出发出发出发,可以循链找到所有依附于该顶可以循链找到所有依附于该顶可以循链找到所有依附于该顶可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。有向图的情形有向图的情形n n在用邻接表表示有向图时在用邻接表表示有向图时,有时需要同时使有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重用邻接表和逆邻接表。用有向图的邻接多重表表(十字链表十字链表)可把两个表结合起来表示。可把两个表结合起来表示。uu边结点的结构边结点的结构其中，其中，mark是处理标记；是处理标记；vertex1和和vertex2指明该有向边始顶点和终顶点的位置。指明该有向边始顶点和终顶点的位置。mark vertex1 vertex2 path1 path2path1path1是指向是指向是指向是指向始顶点与该边相同始顶点与该边相同始顶点与该边相同始顶点与该边相同的下一条边的指针；的下一条边的指针；的下一条边的指针；的下一条边的指针；path2path2是指向是指向是指向是指向终顶点与该边相同终顶点与该边相同终顶点与该边相同终顶点与该边相同的下一条边的指针。需的下一条边的指针。需的下一条边的指针。需的下一条边的指针。需要时还可有权值域要时还可有权值域要时还可有权值域要时还可有权值域costcost。uu顶点结点的结构顶点结点的结构 每个顶点有一个结点，它相当于出边表和入边表每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员的表头结点：其中，数据成员data存放与该顶点相存放与该顶点相关的信息，指针关的信息，指针Firstout 指示以该顶点为始顶点的指示以该顶点为始顶点的出边表的第一条边，出边表的第一条边，Firstin指示以该顶点为终顶指示以该顶点为终顶点的入边表的第一条边。点的入边表的第一条边。data Firstin Firstout邻接多重表的结构邻接多重表的结构mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE在有向图的十字链表中，从顶点结点的firstout指针域出发，沿边结点中的path1域的链一直走到底正好是原来的邻接表结构。统计链中边结点的个数可求得该顶点的出度。从顶点结点的firstin指针域出发，沿边结点中的path2域的链一直走到底正好是原来的逆邻接表结构。统计链中边结点的个数可求得该顶点的入度。图的遍历与连通性图的遍历与连通性n n从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一从已给的连通图中某一顶点出发，沿着一 些边访遍些边访遍些边访遍些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历叫做图的遍历叫做图的遍历叫做图的遍历(Graph Traversal)Graph Traversal)。n n图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。边又回到了曾经访问过的顶点。n n为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标志顶点是否被访为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组问过的辅助数组问过的辅助数组问过的辅助数组 visitedvisited 。初始状态为初始状态为初始状态为初始状态为0 0，在遍历，在遍历，在遍历，在遍历的过程中如果顶点的过程中如果顶点的过程中如果顶点的过程中如果顶点ViVi被访问，就立即让被访问，就立即让被访问，就立即让被访问，就立即让visitedVivisitedVi为为为为1 1，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。，防止它被多次访问。图的遍历的分类图的遍历的分类:uu深度优先搜索深度优先搜索 DFS(Depth First Search)uu广度优先搜索广度优先搜索 BFS(Breadth First Search)深度优先搜索深度优先搜索DFS(Depth First Search)n nDFSDFS 在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点在访问图中某一起始顶点 v v 后后后后,由由由由 v v 出发出发出发出发,访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点访问它的任一邻接顶点 ww1 1;再从再从再从再从 ww1 1 出发出发出发出发,访问与访问与访问与访问与 ww1 1邻邻邻邻 接但还没有访问过的顶点接但还没有访问过的顶点接但还没有访问过的顶点接但还没有访问过的顶点 ww2 2;然后再从然后再从然后再从然后再从 ww2 2 出发出发出发出发,进行类似的访问进行类似的访问进行类似的访问进行类似的访问,如此进行下去如此进行下去如此进行下去如此进行下去,直直直直至到达所有的邻接顶点都被访问过的顶点至到达所有的邻接顶点都被访问过的顶点至到达所有的邻接顶点都被访问过的顶点至到达所有的邻接顶点都被访问过的顶点 u u 为止。为止。为止。为止。接着接着接着接着,退回一步退回一步退回一步退回一步,退到前一次刚访问过的顶点退到前一次刚访问过的顶点退到前一次刚访问过的顶点退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有看是否还有其它没有被访问的邻接顶点。如果有看是否还有其它没有被访问的邻接顶点。如果有看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点则访问此顶点则访问此顶点则访问此顶点,之后再从此顶点出发之后再从此顶点出发之后再从此顶点出发之后再从此顶点出发,进行与前进行与前进行与前进行与前述类似的访问述类似的访问述类似的访问述类似的访问;如果没有如果没有如果没有如果没有,就再退回一步进行搜就再退回一步进行搜就再退回一步进行搜就再退回一步进行搜索。重复上述过程索。重复上述过程索。重复上述过程索。重复上述过程,直到连通图中所有顶点都被直到连通图中所有顶点都被直到连通图中所有顶点都被直到连通图中所有顶点都被访问过为止。访问过为止。访问过为止。访问过为止。深度优先搜索深度优先搜索DFS(Depth First Search)深度优先搜索的示例深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树图的深度优先搜索算法图的深度优先搜索算法template void Graph :DFS()int*visited=new int NumVertices;for(int i=0;i NumVertices;i+)visited i=0;/访问数组 visited 初始化 DFS(0,visited);/从顶点0出发开始搜索 delete visited;/释放 visited 图的深度优先搜索算法图的深度优先搜索算法template void Graph :DFS(const int v,int visited )cout GetValue(v);/访问顶点 v visitedv=1;/顶点 v 作访问标记 int w=GetFirstNeighbor(v);/取 v 的第一个邻接顶点 w while(w!=-1)/若邻接顶点 w 存在 if(!visitedw)DFS(w,visited);/若顶点 w 未访问过,递归访问顶点 w w=GetNextNeighbor(v,w);/取顶点 v 排在 w 后的下一个邻接顶点 Avisited0=1w=1DFS(1,visited)w=3DFS(3,visited)w=-1Bvisited1=1w=0w=2DFS(2,visited)w=-1Cvisited2=1w=1w=-1Dvisited3=1w=0w=-1DFS（0，visited）ABCD0123广度优先搜索广度优先搜索BFS(Breadth First Search)广度优先搜索的示例广度优先搜索的示例ACDEGBFIHACDEGBFH123456789123456789广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树I广度优先搜索广度优先搜索BFS(Breadth First Search)n nBFSBFS在访问了起始顶点在访问了起始顶点在访问了起始顶点在访问了起始顶点 v v 之后之后之后之后,由由由由 v v 出发出发出发出发,依次访依次访依次访依次访问问问问 v v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 ww1 1,ww2 2,wwt t,然后再顺序访问然后再顺序访问然后再顺序访问然后再顺序访问 ww1 1,ww2 2,wwt t 的所有还未被访问过的所有还未被访问过的所有还未被访问过的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问的邻接顶点。再从这些访问过的顶点出发，再访问的邻接顶点。再从这些访问过的顶点出发，再访问的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，它们的所有还未被访问过的邻接顶点，它们的所有还未被访问过的邻接顶点，它们的所有还未被访问过的邻接顶点，如此做下如此做下如此做下如此做下去，直到图中所有顶点都被访问到为止。去，直到图中所有顶点都被访问到为止。去，直到图中所有顶点都被访问到为止。去，直到图中所有顶点都被访问到为止。n n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程,每向前走一每向前走一每向前走一每向前走一步可能访问一批顶点步可能访问一批顶点步可能访问一批顶点步可能访问一批顶点,不像深度优先搜索那样有往不像深度优先搜索那样有往不像深度优先搜索那样有往不像深度优先搜索那样有往回退的情况。因此回退的情况。因此回退的情况。因此回退的情况。因此,广度优先搜索不是一个递归的广度优先搜索不是一个递归的广度优先搜索不是一个递归的广度优先搜索不是一个递归的过程。过程。过程。过程。广度优先搜索广度优先搜索BFS(Breadth First Search)n n为了实现逐层访问为了实现逐层访问,算法中使用了一个队算法中使用了一个队列列,以记忆正在访问的这一层和上一层的顶以记忆正在访问的这一层和上一层的顶点点,以便于向下一层访问。以便于向下一层访问。n n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。给被访问过的顶点加标记。template void Graph :BFS(int v)int*visited=new intNumVertices;for(int i=0;i NumVertices;i+)visitedi=0;/visited初始化 cout GetValue(v);visitedv=1;Queue q;q.EnQueue(v);/进队列 while(!q.IsEmpty()/队空搜索结束 v=q.DeQueue();int w=GetFirstNeighbor(v);while(w!=-1)/若邻接顶点 w 存在 if(!visitedw)/未访问过 cout GetValue(w);visitedw=1;q.EnQueue(w);w=GetNextNeighbor(v,w);/内层内层whilewhile循环循环重复检测 v v 的所有邻接顶点 /外层while循环，判队列空否 delete visited;例子给出下图从顶点1出发进行深度优先搜索得到的深度优先生成树给出下图从顶点2出发进行广度优先搜索得到的广度优先生成树连通分量连通分量(Connected component)当无向图为非连通图时当无向图为非连通图时当无向图为非连通图时当无向图为非连通图时,从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发从图中某一顶点出发,利利利利用深度优先搜索算法或广度优先搜索算法用深度优先搜索算法或广度优先搜索算法用深度优先搜索算法或广度优先搜索算法用深度优先搜索算法或广度优先搜索算法不可能遍不可能遍不可能遍不可能遍历到图中的所有顶点历到图中的所有顶点历到图中的所有顶点历到图中的所有顶点,只能访问到该顶点所在的最只能访问到该顶点所在的最只能访问到该顶点所在的最只能访问到该顶点所在的最大连通子图大连通子图大连通子图大连通子图(连通分量连通分量连通分量连通分量)的所有顶点的所有顶点的所有顶点的所有顶点。n n若从无向图的每一个连通分量中的一个顶点出发进若从无向图的每一个连通分量中的一个顶点出发进若从无向图的每一个连通分量中的一个顶点出发进若从无向图的每一个连通分量中的一个顶点出发进行遍历行遍历行遍历行遍历,可求得无向图的所有连通分量。可求得无向图的所有连通分量。可求得无向图的所有连通分量。可求得无向图的所有连通分量。n n在算法中在算法中在算法中在算法中,需要对图的每一个顶点进行检测：若需要对图的每一个顶点进行检测：若需要对图的每一个顶点进行检测：若需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连已被访问过，则该顶点一定是落在图中已求得的连已被访问过，则该顶点一定是落在图中已求得的连已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，通分量上；若还未被访问，则从该顶点出发遍历图，通分量上；若还未被访问，则从该顶点出发遍历图，通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。可求得图的另一个连通分量。可求得图的另一个连通分量。可求得图的另一个连通分量。n n对于非连通的无向图，所有连通分量的生成树组成对于非连通的无向图，所有连通分量的生成树组成对于非连通的无向图，所有连通分量的生成树组成对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林了非连通图的生成森林了非连通图的生成森林了非连通图的生成森林。ACDEIBFOGHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图的连通分量ABCDEFGHIJKLMNO01234567891011121314432150065064154989787131211141014101012110ACDEBFGIHJONMLK非连通无向图的邻接表表示确定连通分量的算法确定连通分量的算法template void Graph :Components()int*visited=new intNumVertices;for(int i=0;i NumVertices;i+)visitedi=0;/visited 初始化 for(i=0;i NumVertices;i+)if(!visitedi)/检测顶点是否访问过 DFS(i,visited);/未访问,出发访问 OutputNewComponent();/连通分量 delete visited;最小生成树最小生成树(minimum cost spanning tree)n n使用不同的遍历图的方法，可以得到不同的生使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的生成树。生成树。n n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1 条边。条边。n n构造最小生成树的准则构造最小生成树的准则n n必须使用且仅使用该网络中的必须使用且仅使用该网络中的n-1 条边来联条边来联结网络中的结网络中的 n 个顶点；个顶点；n n不能使用产生回路的边；不能使用产生回路的边；n n各边上的权值的总和达到最小。各边上的权值的总和达到最小。克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点个顶点,没有边没有边的非连通图的非连通图 T=V,图中每个顶点自成图中每个顶点自成一个连通分量。当在一个连通分量。当在 E 中选到一条具有最小中选到一条具有最小权值的边时权值的边时,若该边的两个顶点落在不同的连若该边的两个顶点落在不同的连通分量上，则将此边加入到通分量上，则将此边加入到 T 中中;否则将此否则将此边舍去，重新选择一条权值最小的边。如此重边舍去，重新选择一条权值最小的边。如此重复下去复下去,直到所有顶点在同一个连通分量上为直到所有顶点在同一个连通分量上为止止应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程10504613228102514242216181250461325046132原图 (a)(b)1012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n算法的框架算法的框架算法的框架算法的框架利用最小堆利用最小堆利用最小堆利用最小堆(MinHeap)MinHeap)和并查集和并查集和并查集和并查集(DisjointSets)DisjointSets)来实现克鲁斯卡尔算法。来实现克鲁斯卡尔算法。来实现克鲁斯卡尔算法。来实现克鲁斯卡尔算法。n n首先首先首先首先,利用最小堆来存放利用最小堆来存放利用最小堆来存放利用最小堆来存放E E中的所有的边中的所有的边中的所有的边中的所有的边,堆中每个堆中每个堆中每个堆中每个结点的格式为结点的格式为结点的格式为结点的格式为n n在构造最小生成树过程中在构造最小生成树过程中在构造最小生成树过程中在构造最小生成树过程中,利用利用利用利用并查集并查集并查集并查集的运算检查依的运算检查依的运算检查依的运算检查依附一条边的两顶点附一条边的两顶点附一条边的两顶点附一条边的两顶点tailtail、headhead 是否在同一连通分量是否在同一连通分量是否在同一连通分量是否在同一连通分量(即即即即并查集的同一个子集合并查集的同一个子集合并查集的同一个子集合并查集的同一个子集合)上上上上,是则舍去这条边；否则将是则舍去这条边；否则将是则舍去这条边；否则将是则舍去这条边；否则将此边加入此边加入此边加入此边加入 T T,同时将这两个顶点放在同一个连通分量上。同时将这两个顶点放在同一个连通分量上。同时将这两个顶点放在同一个连通分量上。同时将这两个顶点放在同一个连通分量上。tail head cost 边的两个顶点位置 边的权值克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合中,各各各各连通分量也在逐步合并连通分量也在逐步合并连通分量也在逐步合并连通分量也在逐步合并,直到形成一个连通分量直到形成一个连通分量直到形成一个连通分量直到形成一个连通分量为止。为止。为止。为止。const int MAXNUM=机器可表示的机器可表示的,问题中问题中 不可能出现的大数不可能出现的大数class MinSpanTree;/最小生成树的前视类声明最小生成树的前视类声明class MSTEdgeNode /生成树边结点类friend class MinSpanTree;private:int tail,head;/生成树各边的两顶点 float cost;/生成树各边的权值public:MSTEdgeNode()/构造函数 :tail(-1),head(-1),cost(0)；最小生成树类定义最小生成树类定义最小生成树类定义最小生成树类定义class MinSpanTree protected:MSTEdgeNode*edgevalue;/边值数组边值数组 int MaxSize,n;public:MinSpanTree(int sz=NumVertices-1):MaxSize(sz),n(0)/数组最大元素个数和当前个数数组最大元素个数和当前个数 edgevalue=new MSTEdgeNodeMaxSize;int Insert(MSTEdgeNode&item);void Graph:Kruskal(MinSpanTree&T)MSTEdgeNode e;/边结点辅助单元 MinHeap H(NumEdges);int NumVertices=VerticesList.last;/顶点数 UFSets F(NumVertices);/并查集 for(int u=0;u NumVertices;u+)for(int v=u+1;v NumVertices;v+)if(Edgeuv!=MAXNUM)e.tail=u;e.head=v;/插入堆 e.cost=Edgeuv;H.Insert(e);利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树int count=1;/最小生成树加入边数计数 while(count NumVertices)H.RemoveMin(e);/从堆中退出一条边 u=F.Find(e.tail);/检测两端点的根 v=F.Find(e.head);if(u!=v)/根不在同一连通分量 F.Union(u,v);/合并 T.Insert(e);/该边存入最小生成树 count+;并查集邻接矩阵表示-2-2-2-2-1-1-1-1-1-1-1-1-1-1-1-102-1-1-10-2200000 1 2 3 4 5 6-21-11-2-1-421-2-51211-711211F 0 1 2 3 4 5 6 0 28 10 028 0 16 14 1 16 0 12 2 12 0 22 18 3 22 0 25 24 410 25 0 5 14 18 24 0 65046132281025142422161812Kruskal的算法复杂度建立最小堆检测邻接矩阵O(n2)e次堆插入操作O(elog2e)e次出堆操作O(elog2e)2e次并查集find操作O(elog2n)n-1次union操作O(n)复杂度为O(elog2e+elog2n+n2+n)例子采用kruskal算法求下图的最小生成树，并给出求解过程中堆，并查集和最小生成树的变化12345671110957861234567111095786建最小堆建最小堆1234567111095786建最小堆建最小堆并查集并查集并查集并查集31-6335123456并查集并查集1234567957631-63350123456普里姆普里姆(Prim)算法算法n n普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络从连通网络从连通网络 N N=V V,E E 中的某一顶点中的某一顶点中的某一顶点中的某一顶点 u u0 0 出发出发出发出发,选选选选择与它关联的具有最小权值的边择与它关联的具有最小权值的边择与它关联的具有最小权值的边择与它关联的具有最小权值的边(u u0 0,v v),),将其顶将其顶将其顶将其顶点加入到生成树顶点集合点加入到生成树顶点集合点加入到生成树顶点集合点加入到生成树顶点集合U U中。中。中。中。以后每一步从一个顶点在以后每一步从一个顶点在以后每一步从一个顶点在以后每一步从一个顶点在 U U 中中中中,而另一个顶点不而另一个顶点不而另一个顶点不而另一个顶点不在在在在 U U 中的各条边中选择权值最小的边中的各条边中选择权值最小的边中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u u,v v),),把它把它把它把它的顶点加入到集合的顶点加入到集合的顶点加入到集合的顶点加入到集合 U U 中。如此继续下去中。如此继续下去中。如此继续下去中。如此继续下去,直到网直到网直到网直到网络中的所有顶点都加入到生成树顶点集合络中的所有顶点都加入到生成树顶点集合络中的所有顶点都加入到生成树顶点集合络中的所有顶点都加入到生成树顶点集合 U U 中为中为中为中为止。止。止。止。n n采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。采用邻接矩阵作为图的存储表示。252510504613228102514242216185046132504613210原图 (a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212普里姆普里姆(Prim)算法算法n n在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组：在构造过程中，还设置了两个辅助数组：uu lowcost lowcost 存存存存放放放放生生生生成成成成树树树树顶顶顶顶点点点点集集集集合合合合内内内内顶顶顶顶点点点点到到到到生成树外各顶点的各边上的当前最小权值；生成树外各顶点的各边上的当前最小权值；生成树外各顶点的各边上的当前最小权值；生成树外各顶点的各边上的当前最小权值；uu nearvex nearvex 记记记记录录录录生生生生成成成成树树树树顶顶顶顶点点点点集集集集合合合合外外外外各各各各顶顶顶顶点点点点距离集合内哪个顶点最近距离集合内哪个顶点最近距离集合内哪个顶点最近距离集合内哪个顶点最近(即权值最小即权值最小即权值最小即权值最小)。5046132281025142422161812普里姆普里姆(Prim)算法算法若选择从顶点若选择从顶点若选择从顶点若选择从顶点0 0出发，即出发，即出发，即出发，即u u0 0=0=0，则两个辅助数则两个辅助数则两个辅助数则两个辅助数组的初始状态为：组的初始状态为：组的初始状态为：组的初始状态为：0 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 65046132281025142422161812然后反复做以下工作然后反复做以下工作然后反复做以下工作然后反复做以下工作1.1.在在在在 lowcost lowcost 中选择中选择中选择中选择 nearvexi nearvexi -1&lowcosti1&lowcosti最最小小的边的边的边的边,用用用用 v v 标记它。则选中的权值最小的边为标记它。则选中的权值最小的边为标记它。则选中的权值最小的边为标记它。则选中的权值最小的边为(nearvexv,v),nearvexv,v),相应的权值为相应的权值为相应的权值为相应的权值为 lowcostvlowcostv。2.2.将将将将 nearvexv nearvexv 改为改为改为改为-1,1,表示它已加入生成树顶点集表示它已加入生成树顶点集表示它已加入生成树顶点集表示它已加入生成树顶点集合合合合,将边将边将边将边(nearvexv,v,lowcostv)nearvexv,v,lowcostv)加入生成树的边集加入生成树的边集加入生成树的边集加入生成树的边集合。合。合。合。3.3.取取取取 lowcosti=min lowcosti,Edgevi lowcosti=min lowcosti,Edgevi，即用即用即用即用生成树顶点集合外各顶点生成树顶点集合外各顶点生成树顶点集合外各顶点生成树顶点集合外各顶点 i i 到刚加入该集合的新顶点到刚加入该集合的新顶点到刚加入该集合的新顶点到刚加入该集合的新顶点 v v 的的的的距离距离距离距离 Edgevi Edgevi 与原来它们到生成树顶点集合中顶点的最与原来它们到生成树顶点集合中顶点的最与原来它们到生成树顶点集合中顶点的最与原来它们到生成树顶点集合中顶点的最短距离短距离短距离短距离lowcosti lowcosti 做比较做比较做比较做比较,取距离近的作为这些集合外取距离近的作为这些集合外取距离近的作为这些集合外取距离近的作为这些集合外顶点到生成树顶点集合内顶点的最短距离。顶点到生成树顶点集合内顶点的最短距离。顶点到生成树顶点集合内顶点的最短距离。顶点到生成树顶点集合内顶点的最短距离。4.4.如果生成树顶点集合外顶点如果生成树顶点集合外顶点如果生成树顶点集合外顶点如果生成树顶点集合外顶点 i i 到刚加入该集合的新顶到刚加入该集合的新顶到刚加入该集合的新顶到刚加入该集合的新顶点点点点 v v 的距离比原来它到生成树顶点集合中顶点的最短距离的距离比原来它到生成树顶点集合中顶点的最短距离的距离比原来它到生成树顶点集合中顶点的最短距离的距离比原来它到生成树顶点集合中顶点的最短距离还要近，则修改还要近，则修改还要近，则修改还要近，则修改nearvexi:nearvexi=vnearvexi:nearvexi=v。表示生成树表示生成树表示生成树表示生成树外顶点外顶点外顶点外顶点i i到生成树内顶点到生成树内顶点到生成树内顶点到生成树内顶点v v当前距离最近。当前距离最近。当前距离最近。当前距离最近。0 28 10 -1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6选选 v=5选边选边(0,5)顶点顶点v=5加入生成树顶点集合：加入生成树顶点集合：0 28 25 10 -1 0 0 0 5 -1 0 lowcostnearvex0 1 2 3 4 5 6选选 v=4选边选边(5,4)50461322810251424221618原图 边(0,5,10)加入生成树12046132102550 1 2 3 4 5 6顶点顶点v=4加入生成树顶点集合：加入生成树顶点集合：0 28 22 25 10 24-1 0 0 4 -1 -1 4 lowcostnearvex选选 v=3选边选边(4,3)50461322810251424221618原图 边(5,4,25)加入生成树125046132102522顶点顶点v=3加入生成树顶点集合：加入生成树顶点集合：0 28 12 22 25 10 18-1 0 3 -1 -1 -1 3 lowcostnearvex0 1 2 3 4 5 6选选 v=2选边选边(3,2)50461322810251424221618原图 边(4,3,22)加入生成树12504613210252212lowcostnearvex0 1 2 3 4 5 6顶点顶点v=2加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 18-1 2 -1 -1 -1 -1 3 选选 v=1选边选边(2,1)50461322810251424221618原图 边(3,2,12)加入生成树125041321025221612顶点顶点v=1加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14-1-1 -1 -1 -1 -1 1 lowcostnearvex0 1 2 3 4 5 6选选 v=6选边选边(1,6)50461322810251424221618原图 边(2,1,16)加入生成树125046132102514221612lowcostnearvex0 1 2 3 4 5 6顶点顶点v=6加入生成树顶点集合：加入生成树顶点集合：0 16 12 22 25 10 14-1-1 -1 -1 -1 -1 -1 50461322810251424221618原图 边(1,6,14)加入生成树125046132102514221612最后生成树中边集合里存入得各条边为最后生成树中边集合里存入得各条边为：(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14)普里姆算法建立最小生成树普里姆算法建立最小生成树void Graph:Prim(MinSpanTree&T)int NumVertices=VerticesList.last;/顶点数 float*lowcost=new floatNumVertices;int*nearvex=new intNumVertices;for(int i=1;i NumVertices;i+)lowcosti=Edge0i;/顶点0到各边代价 nearvexi=0;/及最短带权路径 nearvex0=-1;/加到生成树顶点集合 MSTEdgeNode e;/最小生成树结点单元 for(i=1;i NumVertices;i+)/循环n-1次,加入n-1条边 float min=MAXNUM;int v=0;for(int j=0;j NumVertices;j+)if(nearvexj!=-1&lowcostj min)v=j;min=lowcostj;/1 /求生成树外顶点到生成树内顶点具有最 /小权值的边,v是当前具最小权值的边 if(v)/v=0表示再也找不到要求顶点 e.tail=nearvexv;e.head=v;e.cost=lowcostv;T.Insert(e);/选出的边加入生成树 2 nearvexv=-1;/该边加入生成树标记 for(j=1;j NumVertices;j+)if(nearvexj!=-1&Edgevj lowcostj)lowcostj=Edgevj;/需要修改 3 nearvexj=v;/4 /end for循环n-1次,加入n-1条边最短路径最短路径(Shortest Path)n n最短路径问题：最短路径问题：如果从图中某一顶点如果从图中某一顶点(称为称为源点源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能的路径可能不止一条，如何找到一条路径使得沿此路不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。径上各边上的权值总和达到最小。n n问题解法问题解法uu 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 Dijkstra算法算法 uu所有顶点之间的最短路径所有顶点之间的最短路径 Floyd算法算法边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题n n问题的提法：问题的提法：给定一个带权有向图给定一个带权有向图D与源点与源点 v，求从求从 v 到到D中其它顶点的最短路径。限定各中其它顶点的最短路径。限定各边上的权值大于或等于边上的权值大于或等于0。n n为求得这些最短路径为求得这些最短路径,Dijkstra提出按路径长提出按路径长度的递增次序度的递增次序,逐步产生最短路径的算法。逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直求出长度次短的一条最短路径，依次类推，直到从顶点到从顶点v到其它各顶点的最短路径全部求出到其它各顶点的最短路径全部求出为止。为止。边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题Dijkstra逐步求解的过程逐步求解的过程10432101003050206010源点源点 终点终点 最短路径最短路径 路径长度路径长度v0 v1 (v0,v1)10 v2 (v0,v1,v2)(v0,v3,v2),60,50 v3 (v0,v3)30 v4 (v0,v4)(v0,v3,v4)(v0,v3,v2,v4)100,90,60 n n引入辅助数组引入辅助数组dist。它的每一个分量它的每一个分量disti表表示当前找到的从源点示当前找到的从源点 v0到终点到终点 vi 的最短路径的最短路径的长度。初始状态：的长度。初始状态：n n 若从源点若从源点v0到顶点到顶点 vi 有边有边,则则disti为该边为该边上的权值；上的权值；n n 若从源点若从源点v0到顶点到顶点 vi 无边无边,则则disti为为 。n n假设假设 S 是已求得的最短路径的终点的集合，是已求得的最短路径的终点的集合，则可证明：下一条最短路径必然是从则可证明：下一条最短路径必然是从v0 出发，出发，中间只经过中间只经过 S 中的顶点便可到达的那些顶点中的顶点便可到达的那些顶点vx(vx V-S)的路径中的一条。的