第八章-图-清华大学-数据结构--课件.ppt

《第八章-图-清华大学-数据结构--课件.ppt》由会员分享，可在线阅读，更多相关《第八章-图-清华大学-数据结构--课件.ppt（132页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、n n图的基本概念图的基本概念n n图的存储表示图的存储表示n n图的遍历与连通性图的遍历与连通性 n n最小生成树最小生成树n n最短路径最短路径 n n活动网络活动网络 图的基本概念图的基本概念n n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的及顶点间的关系集合组成的一种数据结构关系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集

2、合。集合。Path(x,y)表示从表示从 x 到到 y 的一条单向通路的一条单向通路,它是有方向的。它是有方向的。n n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对是是有序的。在无向图中，顶点对有序的。在无向图中，顶点对(x,y)是无序的。是无序的。n n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点的有向图有个顶点的有向图有n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。n n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，则中的一条边，则称称

3、 u 与与 v 互为邻接顶点互为邻接顶点。n n权权 某某些些图图的的边边具具有有与与它它相相关关的的数数,称称之之为为权权。这种带权图叫做网络。这种带权图叫做网络。n n子子图图 设设有有两两个个图图 G(V,E)和和 G(V,E)。若若 V V 且且 E E,则称则称 图图G 是是 图图G 的子图。的子图。n n顶顶点点的的度度 一一个个顶顶点点v的的度度是是与与它它相相关关联联的的边边的的条条数数。记记作作TD(v)。在在有有向向图图中中,顶顶点点的的度度等等于于该顶点的入度与出度之和。该顶点的入度与出度之和。n n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均

4、不互均不互相重复相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶点与最后一个顶点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。n n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到到顶点顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。如果是连通的。如果图中任意一对顶点都是连通的图中任意一对顶点都是连通的,则称此图是连通则称此图是连通图。非连通图的极大连通子图叫做连通分量。图。非连通图的极大连通子图叫做连通分量。n n强连通图与强连通分量强连通图与强

5、连通分量 在有向图中在有向图中,若对于每若对于每一对顶点一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的的路径路径,则称此图是强连通图。非强连通图的极则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。大强连通子图叫做强连通分量。n n生成树生成树 一个连通图的生成树是它的极小连通子一个连通图的生成树是它的极小连通子图，在图，在n个顶点的情形下，有个顶点的情形下，有n-1条边。但有向条边。但有向图则可能得到它的由若干有向树组成的生成森图则可能得到它的由若干有向树组成的生成森林。林。n n本章不予本章不予 讨论的图讨论的图图的抽象数据类型图的抽象数据类型

6、class Graph public:Graph();void InsertVertex(const Type&vertex);void InsertEdge (const int v1,const int v2,int weight);void RemoveVertex(const int v);void RemoveEdge(const int v1,const int v2);int IsEmpty();Type GetWeight(const int v1,const int v2);int GetFirstNeighbor(const int v);int GetNextNeighb

7、or(const int v1,const int v2);n n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度，统计第出度，统计第 j 行行 1 的个数可得顶点的个数可得顶点 j 的入度。的入度。n n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个数可得顶的个数可得顶点点i 的度。的度。网络的邻接矩阵网络的邻接矩阵 int GetVertexPos(Const NameType&vertex)return FindVertex(VerticesList,vertex);public:Graph(const int sz=MaxNum

8、Edges);int GraphEmpty()const return VerticesList.IsEmpty();int GraphFull()const return VerticesList.IsFull()|CurrentEdges=MaxEdges;int NumberOfVertices()return VerticesList.last;int NumberOfEdges()return CurrentEdges;邻接矩阵实现的部分图操作邻接矩阵实现的部分图操作template Graph:Graph(const int sz)/构造函数构造函数 for(int i=0;i s

9、z;i+)for(int j=0;j sz;j+)Edgeij=0;CurrentEdges=0;template DistType Graph:GetWeight(const int v1,const int v2)/给出以顶点给出以顶点 v1 和和 v2 为两端点的边上的权值为两端点的边上的权值 if(v1!=-1&v2!=-1)return Edgev1v2;else return 0;template int Graph:GetFirstNeighbor(const int v)/给出顶点位置为给出顶点位置为 v 的第一个邻接顶点的位置的第一个邻接顶点的位置 if(v!=-1)for(

10、int col=0;col 0)return col;return-1;邻接表邻接表(Adjacency List)n n无向图的邻接表无向图的邻接表 把同一个顶点发出的边链接在同一个边链表中，把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点结点中保存有与该边相关联的另一顶点的顶点下标下标 dest 和指向同一链表中下一个边结点的指和指向同一链表中下一个边结点的指针针 link。n n有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表n n在有向图的邻接表中，第在有向图的邻接表中，第

11、 i 个边链表链接的边个边链表链接的边都是都是顶点顶点 i 发出的边发出的边。也叫做。也叫做出边表出边表。n n在有向图的逆邻接表中，第在有向图的逆邻接表中，第 i 个边链表链接的个边链表链接的边都是边都是进入顶点进入顶点 i 的边的边。也叫做。也叫做入边表入边表。n n带权图的边结点中保存该边上的权值带权图的边结点中保存该边上的权值 cost。n n顶点顶点 i 的边链表的表头指针的边链表的表头指针 adj 在顶点表的下标在顶点表的下标为为 i 的顶点记录中，该记录还保存了该顶点的的顶点记录中，该记录还保存了该顶点的其它信息。其它信息。n n在邻接表的边链表中，在邻接表的边链表中，各个边结点

12、的链入顺序各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。n n设图中有设图中有 n 个顶点，个顶点，e 条边，则条边，则用邻接表表示用邻接表表示无向图时无向图时，需要，需要 n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用用邻接表表示有向图时邻接表表示有向图时，若不考虑逆邻接表，若不考虑逆邻接表，只需只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。邻接表表示的图的类定义邻接表表示的图的类定义const int DefaultSize=10;template class Graph;template struct Edge int dest;Dis

13、tType cost;Edge*link;Edge()Edge(int D,DistType C):dest(D),cost(C),link(NULL)int operator!=(const Edge&E)const return dest!=E.dest;template struct Vertex NemeType data;Edge*adj;template class Graph friend class vertex;friend class Edge;private:Vertex*NodeTable;int NumVertices;int MaxVertices;int Numb

14、erOfVertices()return NumVertices;int NumberOfEdges()return NumEdges;void InsertVertex(const NameType&vertex);void RemoveVertex(const int v);void InsertEdge(const int v1,const int v2,const DistType weight);void RemoveEdge(const int v1,const int v2);DistType GetWeight(const int v1,const int v2);int Ge

15、tFirstNeighbor(const int v);int GetNextNeighbor(const int v1,const int v2);网络网络(带权图带权图)的邻接表的邻接表邻接表的构造函数和析构函数邻接表的构造函数和析构函数template Graph:Graph(const int sz=DefaultSize):NumVertices(0),MaxVertices(sz),NumEdges(0)int n,e,k,j;NameType name,tail,head;DistType weight;NodeTable=/创建顶点表创建顶点表 new VertexMaxVer

16、tices;cin n;/输入顶点个数输入顶点个数 for(int i=0;i name;InserVertex(name);cin e;/输入边条数输入边条数 for(i=0;i tail head weight;k=GetVertexPos(tail);j=GetVertexPos(head);InsertEdge(k,j,weight);template int Graph:GetVertexPos(Const NameType&vertex)/根据顶点名根据顶点名vertex查找该顶点在邻接表中的位置查找该顶点在邻接表中的位置 for(int i=0;i NumVertices;i+)

17、if(NodeTablei.data=vertex)return i;return-1;template int Graph:GetFirstNeighbor(const int v)/查找顶点查找顶点 v 的第一个邻接顶点在邻接表中的位置的第一个邻接顶点在邻接表中的位置 if(v!=-1)/若顶点存若顶点存在在 Edge*p=NodeTablev.adj;if(p!=NULL)return pdest;return-1;/若顶点不存在若顶点不存在template int Graph:GetNextNeighbor(const int v1,const int v2)/查找顶点查找顶点 v1

18、在邻接顶点在邻接顶点 v2 后下一个邻接顶点后下一个邻接顶点 if(v1!=-1)Edge*p=NodeTablev1.adj;template DistType Graph:GetWeight(const int v1,const int v2)/取两端点为取两端点为 v1 和和 v2 的边上的权值的边上的权值 if(v1!=-1&v2!=-1)Edge*p=NodeTablev1.adj;while(p!=NULL)if(pdest=v2)return pcost;else p=plink;return 0;邻接多重表邻接多重表(Adjacency Multilist)n n在邻接多重表中

19、，每一条边只有一个边结点。在邻接多重表中，每一条边只有一个边结点。为有关边的处理提供了方便。为有关边的处理提供了方便。n n无向图的情形无向图的情形uu边结点的结构边结点的结构 mark vertex1 vertex2 path1 path2其中，其中，mark 是记录是否处理过的标记；是记录是否处理过的标记；vertex1和和vertex2是依附于该边的两顶点位置。是依附于该边的两顶点位置。path1域是链接指针，指向下一条依附于域是链接指针，指向下一条依附于顶点顶点vertex1的边；的边；path2也是链接指针，指向下一也是链接指针，指向下一条依附于条依附于顶点顶点vertex2的边。需

20、要时还可设置的边。需要时还可设置一个存放与该边相关的权值的域一个存放与该边相关的权值的域 cost。uu顶点结点的结构顶点结点的结构 存储顶点信息的结点表存储顶点信息的结点表以顺序表方式组织以顺序表方式组织，每一，每一个顶点结点有两个数据成员：其中，个顶点结点有两个数据成员：其中，data 存放与存放与该顶点相关的信息，该顶点相关的信息，Firstout 是指示第一条依附是指示第一条依附于该顶点的边的指针。于该顶点的边的指针。在邻接多重表中在邻接多重表中,所有依附于同一个顶点的边所有依附于同一个顶点的边都链接在同一个单链表中。都链接在同一个单链表中。从从顶点顶点 i 出发出发,可以循链找到所有

21、依附于该顶点可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。的边，也可以找到它的所有邻接顶点。uu邻接多重表的结构邻接多重表的结构 data Firstoutn n有向图的情形有向图的情形 在用邻接表表示有向图时，有时需要同时使在用邻接表表示有向图时，有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表用邻接表和逆邻接表。用有向图的邻接多重表(十字链表十字链表)可把这两个表结合起来表示。可把这两个表结合起来表示。uu边结点的结构边结点的结构 mark vertex1 vertex2 path1 path2 其中，其中，mark是处理标记；是处理标记；vertex1和和verte

22、x2指指明该有向边始顶点和终顶点的位置。明该有向边始顶点和终顶点的位置。path1是是指向始顶点与该边相同的下一条边的指针；指向始顶点与该边相同的下一条边的指针；path2是指向终顶点与该边相同的下一条边的是指向终顶点与该边相同的下一条边的指针。需要时还可有权值域指针。需要时还可有权值域cost。uu顶点结点的结构顶点结点的结构 每个顶点有一个结点，它相当于出边表和入每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员边表的表头结点：其中，数据成员data存放与存放与该顶点相关的信息，指针该顶点相关的信息，指针Firstin指示以该顶点指示以该顶点为始顶点的出边表的第一条边，为

23、始顶点的出边表的第一条边，Firstout指示指示以该顶点为终顶点的入边表的第一条边。以该顶点为终顶点的入边表的第一条边。data Firstin Firstoutuu邻接多重表的结构邻接多重表的结构图的遍历与连通性图的遍历与连通性n n从已给的连通图中某一顶点出发，沿着一些边从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历一次，就叫做图的遍历(Graph Traversal)。n n图中可能存在回路，且图的任一顶点都可能与图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会

24、其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。沿着某些边又回到了曾经访问过的顶点。n n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组被访问过的辅助数组 visited ，它的初始状态，它的初始状态为为 0，在图的遍历过程中，一旦某一个顶点，在图的遍历过程中，一旦某一个顶点 i 被被访问，就立即让访问，就立即让 visited i 为为 1，防止它被多次，防止它被多次访问。访问。深度优先搜索深度优先搜索DFS(Depth First Search)n n深度优先搜索的示例深度优先搜索的示例n nDFS 在访问图中

25、某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，出发，访问它的任一邻接顶点访问它的任一邻接顶点 w1；再从；再从 w1 出发，访出发，访问与问与 w1邻邻 接但还没有访问过的顶点接但还没有访问过的顶点 w2；然后；然后再从再从 w2 出发，进行类似的访问，出发，进行类似的访问，如此进行如此进行下去，直至到达所有的邻接顶点都被访问过的下去，直至到达所有的邻接顶点都被访问过的顶点顶点 u 为止。接着，退回一步，退到前一次刚为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从邻接顶点

26、。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。直到连通图中所有顶点都被访问过为止。图的深度优先搜索算法图的深度优先搜索算法viod Graph:DFS(const int v,int visited )cout GetValue(v);/访问顶点访问顶点 v visitedv=1;/顶点顶点 v 作访作访问标记问标记 int w=GetFirstNeighbor(v);/取取 v 的第一个邻接顶点的第一个邻接顶点

27、w while(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)DFS(w,visited);/若顶点若顶点 w 未访问过未访问过,递归访问顶点递归访问顶点 w w=GetNextNeighbor(v,w);/取顶点取顶点 v 的排在的排在 w 后面的下一个邻接顶点后面的下一个邻接顶点 void Graph:DFS()visited=new Boolean n;/创建数组创建数组 visited for(int i=0;i n;i+)visited i=0;/访问标记数组访问标记数组 visited 初始化初始化 DFS(0);delete visited;/释放释

28、放 visited 算法分析算法分析n n图中有图中有 n 个顶点，个顶点，e 条边。条边。n n如果用邻接表表示图，沿如果用邻接表表示图，沿 Firstout link 链可链可以找到某个顶点以找到某个顶点 v 的所有邻接顶点的所有邻接顶点 w。由于总。由于总共有共有 2e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问而且对所有顶点递归访问1次，所以遍历图的次，所以遍历图的时间复杂性为时间复杂性为O(n+e)。n n如果用邻接矩阵表示图，则查找每一个顶点的如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为所有的边，所需时间为O(n)，则遍

29、历图中所有，则遍历图中所有的顶点所需的时间为的顶点所需的时间为O(n2)。广度优先搜索广度优先搜索BFS(Breadth First Search)n n广度优先搜索的示例广度优先搜索的示例 广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树n n使用广度优先搜索在访问了起始顶点使用广度优先搜索在访问了起始顶点 v 之后，之后，由由 v 出发，依次访问出发，依次访问 v 的各个未曾被访问过的的各个未曾被访问过的邻接顶点邻接顶点 w1,w2,wt，然后再顺序访问，然后再顺序访问 w1,w2,wt 的所有还未被访问过的邻接顶点。的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再

30、访问它们的所再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，有还未被访问过的邻接顶点，如此做下去，如此做下去，直到图中所有顶点都被访问到为止。直到图中所有顶点都被访问到为止。n n广度优先搜索是一种分层的搜索过程，每向前广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。是一个递归的过程，其算法也不是递归的。n n为了实现逐层访问，算法中使用了一个队列，为了实现逐层访问，算法中使用了一个队列，

31、以记忆正在访问的这一层和上一层的顶点，以以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。便于向下一层访问。n n与深度优先搜索过程一样，为避免重复访问，与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶，给被访问过的顶点加标记。点加标记。图的广度优先搜索算法图的广度优先搜索算法void Graph:BFS(const int v)visited=new intNumCertices;/创建创建 visited for(int i=0;i NumVertices;i+)visitedi=0;/visited 初始化初始化 cout

32、 GetValue(v);visitedv=1;Queue q;q.EnQueue(v);/访问访问 v,进队进队列列 while(!q.IsEmpty()/队空搜索队空搜索结束结束 v=q.DeQueue();/不空不空,出队列出队列 int w=GetFirstNeighbor(v);/取顶点取顶点 v 的第一个邻接顶点的第一个邻接顶点 w while(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)/若该邻接顶点未访若该邻接顶点未访问过问过 cout GetValue(w);/访问访问 visitedw=1;q.EnQueue(w);/进队进队 w=GetNe

33、xtNeighbor(v,w);/取顶点取顶点 v 的排在的排在 w 后面的下一邻接顶点后面的下一邻接顶点 /重复检测重复检测 v 的所有邻接顶点的所有邻接顶点 delete visited;算法分析算法分析n n如果使用邻接表表示图，则循环的总时间代如果使用邻接表表示图，则循环的总时间代价为价为 d0+d1+dn-1=O(e)，其中的，其中的 di 是顶是顶点点 i 的度。的度。n n如果使用邻接矩阵，则对于每一个被访问过如果使用邻接矩阵，则对于每一个被访问过的顶点，循环要检测矩阵中的的顶点，循环要检测矩阵中的 n 个元素，总个元素，总的时间代价为的时间代价为O(n2)。连通分量连通分量(C

34、onnected component)n n当无向图为非连通图时，从图中某一顶点出发，当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索算法不利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访问到该顶可能遍历到图中的所有顶点，只能访问到该顶点所在的最大连通子图点所在的最大连通子图(连通分量连通分量)的所有顶点。的所有顶点。n n若从无向图的每一个连通分量中的一个顶点出若从无向图的每一个连通分量中的一个顶点出发进行遍历，可求得无向图的所有连通分量。发进行遍历，可求得无向图的所有连通分量。n n在算法中，需要对图的每一个顶点进行检测：在算法中，需要对

35、图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。出发遍历图，可求得图的另一个连通分量。n n对于非连通的无向图，所有连通分量的生成树对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。组成了非连通图的生成森林。确定连通分量的算法确定连通分量的算法 void Graph:Components()visited=new intNumCertices;/创建创建visited for(int i=0;i NumVe

36、rtices;i+)visitedi=0;/visited 初始初始化化 for(i=0;i NumVertices;i+)if(!visitedi)/检测所有顶点是否检测所有顶点是否访问过访问过 DFS(i,visited);/从未访问的顶点出发访从未访问的顶点出发访问问 OutputNewComponent();/输出一个连通分量输出一个连通分量 delete visited;/释放释放visited重连通分量重连通分量(Biconnected Component)n n在无向连通图在无向连通图G中，当且仅当删去中，当且仅当删去G中的顶点中的顶点 v及及所有依附于所有依附于v的所有边的所有

37、边后，可将图分割成两个后，可将图分割成两个或两个以上的连通分量，则称顶点或两个以上的连通分量，则称顶点v为为关节点关节点。n n没有没有关节点关节点的连通图叫做重连通图。的连通图叫做重连通图。n n在重连通图上在重连通图上,任何一对顶点之间至少存在有两任何一对顶点之间至少存在有两条路径条路径,在删去某个顶点及与该顶点相关联的边在删去某个顶点及与该顶点相关联的边时时,也不破坏图的连通性。也不破坏图的连通性。n n一个连通图一个连通图G如果不是重连通图，那么它可以包如果不是重连通图，那么它可以包括几个重连通分量。括几个重连通分量。n n在一个无向连通图在一个无向连通图G中中,重连通分量可以利用深重

38、连通分量可以利用深度优先生成树找到。度优先生成树找到。n ndfn 顶顶点点的的深深度度优优先先数数，标标明明进进行行深深度度优优先先搜索时各顶点访问的次序。搜索时各顶点访问的次序。n n如如果果在在深深度度优优先先生生成成树树中中，顶顶点点 u 是是顶顶点点 v 的的祖先祖先,则有则有dfnu dfnv。n n深深度度优优先先生生成成树树的的根根是是关关节节点点的的充充要要条条件件是是它至少有两个子女它至少有两个子女。n n其其它它顶顶点点 u 是是关关节节点点的的充充要要条条件件是是它它至至少少有有一一个个子子女女 w,从从 w 出出发发,不不能能通通过过 w、w 的的子子孙孙及一条回边所

39、组成的路径到达及一条回边所组成的路径到达 u 的祖先的祖先。n n在在图图G的的每每一一个个顶顶点点上上定定义义一一个个 low 值值，lowu 是是从从 u 或或 u 的的子子孙孙出出发发通通过过回回边边可可以以到到达的达的最低深度优先数最低深度优先数。n nu 是关节点的充要条件是：是关节点的充要条件是：uu u 是具有两个以上子女的生成树的根是具有两个以上子女的生成树的根uu u 不是根，但它有一个子女不是根，但它有一个子女 w，使得，使得 loww dfnun n这时这时 w 及其子孙不存在指向顶点及其子孙不存在指向顶点u的祖先的回边。的祖先的回边。lowu=min dfnu,min

40、loww|w 是是 u 的一个子女的一个子女,min dfnx|(u,x)是一条回边是一条回边 计算计算dfn与与low的算法的算法(1)void Graph:DfnLow(const int x)/公有函数：从顶点公有函数：从顶点x开始深度优先搜索开始深度优先搜索 int num=1;/num是访问计数器是访问计数器 dfn=new intNumVertices;low=new intNumVertices;/dfn是深度优先数是深度优先数,low是最小祖先访问顺序是最小祖先访问顺序号号 for(int i=0;i 1 时输出重连通分量（时输出重连通分量（1）void Graph:Bicon

41、nected()/公有函数：从顶点公有函数：从顶点0开始深度优先搜索开始深度优先搜索 int num=1;/访问计数器访问计数器num dfn=new intNumVertices;/dfn是深度优先是深度优先数数 low=new intNumVertices;/low是最小祖先是最小祖先号号 for(int i=0;i 1 时输出重连通分量（时输出重连通分量（2）void Graph:Biconnected(const int u,const int v)/私有函数：计算私有函数：计算dfn与与low,根据其重连通分量输根据其重连通分量输/出出Graph的边。在产生的生成树中的边。在产生的生

42、成树中,v 是是 u 的双的双亲亲/结点结点,S 是一个初始为空的栈，应声明为图的数是一个初始为空的栈，应声明为图的数/据成员。据成员。int x,y,w;dfnu=lowu=num+;w=GetFirstNeighbor(u);/找顶点找顶点u的第一个邻接顶点的第一个邻接顶点w while(w!=-1)if(v!=w&dfnw=dfnu)/无回边无回边,原来的重连通分量结束原来的重连通分量结束 cout “新重连通分量新重连通分量:”end1;do (x,y)=S.Pop();cout x ,y endl;while(x,y)与与(u,w)不是同一条边不是同一条边);/输出该重连通分量的各边

43、输出该重连通分量的各边 else if(w!=v)/有回边有回边,计算计算 lowu=min2(lowu,dfnw);/根据回边另一顶点根据回边另一顶点w调整调整lowu w=GetNextNeighbor(u,w);/找顶点找顶点u的邻接顶点的邻接顶点w的下一个邻接顶点的下一个邻接顶点 算法算法 Biconnected 的时间代价是的时间代价是 O(n+e)。其中。其中 n 是该连通图的顶点数，是该连通图的顶点数，e 是该连通图的边数。是该连通图的边数。此算法的前提条件是连通图中至少有两个顶点此算法的前提条件是连通图中至少有两个顶点,因为正好有一个顶点的图连一条边也没有。因为正好有一个顶点的

44、图连一条边也没有。最小生成树最小生成树(minimum cost spanning tree)n n使用不同的遍历图的方法，可以得到不同的生使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的生成树。生成树。n n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1 条边。条边。n n构造最小生成树的准则构造最小生成树的准则uu必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；uu必须使用且仅使用必须使用且仅使用 n-1 条边来联

45、结网络中的条边来联结网络中的 n 个顶点；个顶点；uu不能使用产生回路的边。不能使用产生回路的边。克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法n n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点，没有边的非连个顶点，没有边的非连通图通图 T=V,图中每个顶点自成一个连通图中每个顶点自成一个连通分量。当在分量。当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则若该边的两个顶点落在不同的连通分量上，则将此边加入到将

46、此边加入到 T 中；否则将此边舍去，重新选中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。有顶点在同一个连通分量上为止。n n算法的框架算法的框架我们利用最小堆我们利用最小堆(MinHeap)和并查和并查集集(DisjointSets)来实现克鲁斯卡尔算法。来实现克鲁斯卡尔算法。n n首先，利用最小堆来存放首先，利用最小堆来存放E中的所有的边中的所有的边,堆堆中每个结点的格式为中每个结点的格式为n n在构造最小生成树的过程中，最小堆中存放剩在构造最小生成树的过程中，最小堆中存放剩余的边，并且利用并查集的运算

47、检查依附于一余的边，并且利用并查集的运算检查依附于一条边的两个顶点条边的两个顶点 tail、haed 是否在同一个连通是否在同一个连通分量分量(即并查集的同一个子集合即并查集的同一个子集合)上上,是则舍去是则舍去这条边；否则将此边加入这条边；否则将此边加入 T，同时将这两个顶，同时将这两个顶点放在同一个连通分量上。随着各边逐步加入点放在同一个连通分量上。随着各边逐步加入到最小生成树的边集合中，各连通分量也在逐到最小生成树的边集合中，各连通分量也在逐步合并，直到形成一个连通分量为止。步合并，直到形成一个连通分量为止。tail head cost 边的两个顶点位置边的两个顶点位置 边的权值边的权值

48、应用克鲁斯卡尔算法构造最小生成树的过程应用克鲁斯卡尔算法构造最小生成树的过程最小生成树类定义最小生成树类定义const int MAXINT=机器可表示的机器可表示的,问题中不可能出现的大数问题中不可能出现的大数class MinSpanTree;class MSTEdgeNode/生成树边结点类生成树边结点类定义定义friend class MinSpanTree;private:int tail,head;/生成树各边的两顶点生成树各边的两顶点 int cost;/生成树各边的代生成树各边的代价价;class MinSpanTree /生成树的类定义生成树的类定义public:MinSpa

49、nTree(int sz=MaxEdges-1):MaxSize(sz),n(0)edgevalue=new MSTEdgeNodeMaxSize;int Insert(MSTEdgeNode&item);/将将item加到最小生成树中加到最小生成树中protected:MSTEdgeNode*edgevalue;/边值数组边值数组 int MaxSize,n;/最大边数最大边数,当前边当前边数数;利用克鲁斯卡尔算法建立最小生成树利用克鲁斯卡尔算法建立最小生成树void Graph:Kruskal(MinSpanTree&T)MSTEdgeNode e;/边结点辅助单元边结点辅助单元 MinH

50、eap H(CurrentEdges);int NumVertices=VerticesList.last;/顶点个数顶点个数 UFSets F(NumVertices);/并查集并查集F 并初始并初始化化 for(int u=0;u NumVertices;u+)/邻接矩邻接矩阵阵 for(int v=i+1;v NumVertices;v+)if(Edgeuv!=MAXINT)/检出所检出所有边有边 e.tail=u;e.head=v;e.cost=w;H.Insert(e);/插入最小插入最小堆堆 int count=1;/最小生成树加入边数的计最小生成树加入边数的计数数 while(c