数据结构4清华大学课件

《数据结构4清华大学课件》由会员分享，可在线阅读，更多相关《数据结构4清华大学课件（286页珍藏版）》请在装配图网上搜索。

1、数据结构（用面向对象方法与C+语言描述）第二版4清华大学计算机系清华大学计算机系殷人昆殷人昆1数据结构4（清华大学）第八章 图清华大学计算机系清华大学计算机系殷人昆殷人昆 王王 宏宏2数据结构4（清华大学）n图的基本概念图的基本概念n图的存储表示图的存储表示n图的遍历与连通性图的遍历与连通性 n最小生成树最小生成树n最短路径最短路径 n活动网络活动网络第八章第八章 图图3 3数据结构4（清华大学）图的基本概念图的基本概念n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间及顶点间的关系集合组成的一种数据结构：的关系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x

2、 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path(x,y)表示从表示从 x 到到 y 的一的一条单向通路条单向通路,它是有方向的。它是有方向的。4 4数据结构4（清华大学）n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序是无序的。的。n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/

3、2 条条边边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点的有向个顶点的有向图有图有n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。000011112222654335 5数据结构4（清华大学）n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。n子图子图 设有两个图设有两个图G(V,E)和和G(V,E)。若若V V 且且E E,则称图则称图G是图是图G的子图。的子图。n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。称之为权。这种带权图叫做网络。这种带权图叫做网络。子图子

4、图012301301230236 6数据结构4（清华大学）n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的边的的度是与它相关联的边的条数。记作条数。记作TD(v)。在有向图中。在有向图中,顶点的度等顶点的度等于该顶点的入度与出度之和。于该顶点的入度与出度之和。n顶点顶点 v 的入度的入度是以是以 v 为终点的有向边的条数为终点的有向边的条数,记作记作 ID(v);顶点顶点 v 的出度的出度是以是以 v 为始点的有向为始点的有向边的条数边的条数,记作记作 OD(v)。n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿一些边经过一些顶点沿一些边经过一些顶点 vp1

5、,vp2,vpm，到达，到达顶点顶点vj。则称顶点序列。则称顶点序列(vi vp1 vp2.vpm vj)为为从顶点从顶点vi 到顶点到顶点 vj 的路径。它经过的边的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的的边。边。7 7数据结构4（清华大学）n路径长度路径长度 非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边边的条数。带权图的路径长度是指路径上各边的权之和。的权之和。n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均均不不 互相重复互相重复,则称这样的路径为简单

6、路径。则称这样的路径为简单路径。n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重合重合,则称这样的路径为回路或环。则称这样的路径为回路或环。0123012301238 8数据结构4（清华大学）n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。是连通的。如果图中任意一对顶点都是连通的如果图中任意一对顶点都是连通的,则称此图则称此图是连通图。非连通图的极大连通子图叫做连是连通图。非连通图的极大连通子图叫做连通分量。通分量。n强连通图与强连通分量强连通图与强连通

7、分量 在有向图中在有向图中,若对于若对于每一对顶点每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,则称此图是强连通图。非强连通则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。图的极大强连通子图叫做强连通分量。n生成树生成树 一个连通图的生成树是其极小连通子一个连通图的生成树是其极小连通子图，在图，在 n 个顶点的情形下，有个顶点的情形下，有 n-1 条边。条边。9 9数据结构4（清华大学）图的抽象数据类型图的抽象数据类型class Graph/对象:由一个顶点的非空集合和一个边集合构成/每条边由一个顶点对来表示。public:Grap

8、h();/建立一个空的图 void insertVertex(const T&vertex);/插入一个顶点vertex,该顶点暂时没有入边 void insertEdge(int v1,int v2,int weight);/在图中插入一条边(v1,v2,w)void removeVertex(int v);/在图中删除顶点v和所有关联到它的边 1010数据结构4（清华大学）void removeEdge(int v1,int v2);/在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点,则返回true,否则返回false T getWeight(int v1,int

9、v2);/函数返回边(v1,v2)的权值 int getFirstNeighbor(int v);/给出顶点 v 第一个邻接顶点的位置 int getNextNeighbor(int v,int w);/给出顶点 v 的某邻接顶点 w 的下一个邻接顶点;11 11数据结构4（清华大学）图的存储表示图的存储表示n图的模板基类图的模板基类 在模板类定义中的数据类型在模板类定义中的数据类型参数表参数表 中，中，T是顶点数据的是顶点数据的类型，类型，E是边上所附数据的类型。是边上所附数据的类型。n这个模板基类是按照最复杂的情况（即带权这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用

10、非带权图，无向图）来定义的，如果需要使用非带权图，可将数据类型参数表可将数据类型参数表 改为改为。n如果使用的是有向图，也可以对程序做相应如果使用的是有向图，也可以对程序做相应的改动。的改动。1212数据结构4（清华大学）图的模板基类图的模板基类 const int maxWeight=;/无穷大的值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph /图的类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点数 int

11、 getVertexPos(T vertex);/给出顶点vertex在图中位置public:1313数据结构4（清华大学）Graph(int sz=DefaultVertices);/构造函数 Graph();/析构函数 bool GraphEmpty()const/判图空否 return numEdges=0;int NumberOfVertices()return numVertices;/返回当前顶点数 int NumberOfEdges()return numEdges;/返回当前边数virtual T getValue(int i);/取顶点 i 的值 virtual E getW

12、eight(int v1,int v2);/取边上权值 virtual int getFirstNeighbor(int v);/取顶点 v 的第一个邻接顶点1414数据结构4（清华大学）virtual int getNextNeighbor(int v,int w);/取邻接顶点 w 的下一邻接顶点 virtual bool insertVertex(const T vertex);/插入一个顶点vertex virtual bool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权为cost virtual bool removeVertex(i

13、nt v);/删去顶点 v 和所有与相关联边 virtual bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);1515数据结构4（清华大学）邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶在图的邻接矩阵表示中，有一个记录各个顶点信息的点信息的顶点表顶点表，还有一个表示各个顶点之，还有一个表示各个顶点之间关系的间关系的邻接矩阵邻接矩阵。n设图设图 A=(V,E)是一个有是一个有 n 个顶点的图个顶点的图,图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn

14、，定义：，定义：1616数据结构4（清华大学）n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能是不对称的。有向图的邻接矩阵可能是不对称的。01230121717数据结构4（清华大学）n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度出度，统计第，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入入度度。n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个数可得顶的个数可得顶点点i 的的度度。网络的邻接矩阵网络的邻接矩阵1818数据结构4（清华大学）863129542031用邻接矩阵表示的图的类定义用邻接

15、矩阵表示的图的类定义template class Graphmtx:public Graph friend istream&operator (istream&in,Graphmtx&G);/输入1919数据结构4（清华大学）friend ostream&operator (ostream&out,Graphmtx&G);/输出private:T*VerticesList;/顶点表 E*Edge;/邻接矩阵int getVertexPos(T vertex)/给出顶点vertex在图中的位置 for(int i=0;i=0&i=numVertices?VerticesListi:NULL;E

16、getWeight(int v1,int v2)/取边(v1,v2)上权值 return v1!=-1&v2!=-1?Edgev1v2:0;int getFirstNeighbor(int v);/取顶点 v 的第一个邻接顶点2121数据结构4（清华大学）int getNextNeighbor(int v,int w);/取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex(const T vertex);/插入顶点vertex bool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权值为cost bool removeVer

17、tex(int v);/删去顶点 v 和所有与它相关联的边 bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);2222数据结构4（清华大学）template Graphmtx:Graphmtx(int sz)/构造函数 maxVertices=sz;numVertices=0;numEdges=0;int i,j;VerticesList=new TmaxVertices;/创建顶点表 Edge=(int*)new int*maxVertices;for(i=0;i maxVertices;i+)Edgei=new intmaxVertices;/邻接

18、矩阵 for(i=0;i maxVertices;i+)/矩阵初始化 for(j=0;j maxVertices;j+)Edgeij=(i=j)？0:maxWeight;2323数据结构4（清华大学）template int Graphmtx:getFirstNeighbor(int v)/给出顶点位置为v的第一个邻接顶点的位置,/如果找不到,则函数返回-1 if(v!=-1)for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;2424数据结构4（清华大学）template

19、int Graphmtx:getNextNeighbor(int v,int w)/给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if(v!=-1&w!=-1)for(int col=w+1;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;2525数据结构4（清华大学）n邻接表是邻接矩阵的改进形式。为此需要把邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。邻接矩阵的各行分别组织为一个单链表。n在邻接表中，同一个顶点发出的边链接在同在邻接表中，同一个顶点发出的边链接在同一

20、个边链表中，每一个链结点代表一条边一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标（边结点），结点中有另一顶点的下标 dest 和指针和指针 link。对于带权图，边结点中还要保。对于带权图，边结点中还要保存该边的权值存该边的权值cost。n顶点表的第顶点表的第 i 个顶点中保存该顶点的数据，以个顶点中保存该顶点的数据，以及它对应边链表的头指针及它对应边链表的头指针adj。邻接表邻接表(Adjacency List)(Adjacency List)2626数据结构4（清华大学）ABCDdata adjABCD0123dest linkdest link 130210无向图

21、的邻接表无向图的邻接表n统计某顶点对应边链表中结点个数，可得该顶统计某顶点对应边链表中结点个数，可得该顶点的度。点的度。n某条边某条边(vi,vj)在邻接表中有两个边结点，分别在邻接表中有两个边结点，分别在第在第 i 个顶点和第个顶点和第 j 个顶点对应的边链表中。个顶点对应的边链表中。2727数据结构4（清华大学）data adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻接表逆邻接表(入边表入边表)102 011有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表ABC2828数据结构4（清华大学）BACD69

22、528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络(带权图带权图)的邻接表的邻接表n统计出边表中结点个数，得到该顶点的出度；统计出边表中结点个数，得到该顶点的出度；n统计入边表中结点个数，得到该顶点的入度。统计入边表中结点个数，得到该顶点的入度。2929数据结构4（清华大学）n在邻接表的边链表中，各个边结点的链入顺序在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。n设图中有设图中有 n 个顶点，个顶点，e 条边，则用邻接表表示条边，则用邻接表表示无向图时，需要

23、无向图时，需要 n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用邻接表表示有向图时，若不考虑逆邻接表，用邻接表表示有向图时，若不考虑逆邻接表，只需只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时，可以节省大量的存储空时，可以节省大量的存储空间。此外，把同一个顶点的所有边链接在一个间。此外，把同一个顶点的所有边链接在一个单链表中，也使得图的操作更为便捷。单链表中，也使得图的操作更为便捷。3030数据结构4（清华大学）用邻接表表示的图的类定义用邻接表表示的图的类定义 template struct Edge /边结点的定义 int dest;

24、/边的另一顶点位置 E cost;/边上的权值 Edge*link;/下一条边链指针 Edge()/构造函数 Edge(int num,E cost)/构造函数 :dest(num),weight(cost),link(NULL)bool operator!=(Edge&R)const return dest!=R.dest;/判边等否;3131数据结构4（清华大学）template struct Vertex /顶点的定义 T data;/顶点的名字Edge*adj;/边链表的头指针;template class Graphlnk:public Graph /图的类定义friend istr

25、eam&operator (istream&in,Graphlnk&G);/输入friend ostream&operator (ostream&out,Graphlnk&G);/输出3232数据结构4（清华大学）private:Vertex*NodeTable;/顶点表(各边链表的头结点)int getVertexPos(const T vertx)/给出顶点vertex在图中的位置 for(int i=0;i=0&i NumVertices)?NodeTablei.data:0;E getWeight(int v1,int v2);/取边(v1,v2)权值bool insertVertex

26、(const T&vertex);bool removeVertex(int v);bool insertEdge(int v1,int v2,E cost);bool removeEdge(int v1,int v2);int getFirstNeighbor(int v);int getNextNeighbor(int v,int w);3434数据结构4（清华大学）template Graphlnk:Graphlnk(int sz)/构造函数：建立一个空的邻接表 maxVertices=sz;numVertices=0;numEdges=0;NodeTable=new Vertexmax

27、Vertices;/创建顶点表数组 if(NodeTable=NULL)cerr 存储分配错！存储分配错！endl;exit(1);for(int i=0;i maxVertices;i+)NodeTablei.adj=NULL;3535数据结构4（清华大学）template Graphlnk:Graphlnk()/析构函数：删除一个邻接表 for(int i=0;i numVertices;i+)Edge*p=NodeTablei.adj;while(p!=NULL)NodeTablei.adj=p-link;delete p;p=NodeTablei.adj;delete NodeTabl

28、e;/删除顶点表数组;3636数据结构4（清华大学）template int Graphlnk:getFirstNeighbor(int v)/给出顶点位置为 v 的第一个邻接顶点的位置,/如果找不到,则函数返回-1 if(v!=-1)/顶点顶点v存在存在 Edge*p=NodeTablev.adj;/对应边链表第一个边结点if(p!=NULL)return p-dest;/存在,返回第一个邻接顶点 return-1;/第一个邻接顶点不存在;3737数据结构4（清华大学）template int Graphlnk:getNextNeighbor(int v,int w)/给出顶点v的邻接顶点w

29、的下一个邻接顶点的位置,/若没有下一个邻接顶点,则函数返回-1 if(v!=-1)/顶点v存在 Edge*p=NodeTablev.adj;while(p!=NULL&p-dest!=w)p=p-link;if(p!=NULL&p-link!=NULL)return p-link-dest;/返回下一个邻接顶点 return-1;/下一邻接顶点不存在;3838数据结构4（清华大学）邻接多重表邻接多重表(Adjacency Multilist)(Adjacency Multilist)n在邻接多重表中在邻接多重表中,每一条边只有一个边结点。每一条边只有一个边结点。为有关边的处理提供了方便。为有关

30、边的处理提供了方便。n无向图的情形无向图的情形u边结点的结构边结点的结构n其中其中,mark 是记录是否处理过的标记是记录是否处理过的标记;vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接指域是链接指针针,指向下一条依附顶点指向下一条依附顶点vertex1的边；的边；path2 是是指向下一条依附顶点指向下一条依附顶点vertex2的边链接指针。的边链接指针。mark vertex1 vertex2 path1 path23939数据结构4（清华大学）n需要时还可设置一个存放与该边相关的权值的需要时还可设置一个存放与该边相关的权值的域域 cost。u顶点结

31、点的结构顶点结点的结构n顶点信息的结点表以顺序表方式组织顶点信息的结点表以顺序表方式组织,每一个顶每一个顶点结点有两个数据成员：其中，点结点有两个数据成员：其中，data 存放与该存放与该顶点相关的信息，顶点相关的信息，Firstout 是指示第一条依附该是指示第一条依附该顶点的边的指针。顶点的边的指针。n在邻接多重表中在邻接多重表中,所有依附同一个顶点的边都所有依附同一个顶点的边都链接在同一个单链表中。链接在同一个单链表中。data Firstout4040数据结构4（清华大学）mark vtx1 vtx2 path1 path2 0 10 21 3e1e2e3data FoutABCD01

32、23e1e2e3ABCDn从顶点从顶点 i 出发出发,可以循链找到所有依附于该顶可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。点的边，也可以找到它的所有邻接顶点。邻接多重表的结构邻接多重表的结构4141数据结构4（清华大学）n有向图的情形有向图的情形n在用邻接表表示有向图时在用邻接表表示有向图时,有时需要同时使用有时需要同时使用邻接表和逆邻接表。用有向图的邻接多重表邻接表和逆邻接表。用有向图的邻接多重表(十字链表十字链表)可把两个表结合起来表示。可把两个表结合起来表示。u边结点的结构边结点的结构n其中，其中，mark是处理标记；是处理标记；vertex1和和vertex2指指明

33、该有向边始顶点和终顶点的位置。明该有向边始顶点和终顶点的位置。path1是是指向指向始顶点与该边相同始顶点与该边相同的下一条边的指针；的下一条边的指针；path2是指向是指向终顶点与该边相同终顶点与该边相同的下一条边的的下一条边的指针。需要时还可有权值域指针。需要时还可有权值域cost。mark vertex1 vertex2 path1 path24242数据结构4（清华大学）u顶点结点的结构顶点结点的结构n每个顶点有一个结点，它相当于出边表和入边每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员表的表头结点：其中，数据成员data存放与该存放与该顶点相关的信息，指针顶点相

34、关的信息，指针Firstin 指示以该顶点为指示以该顶点为始顶点的出边表的第一条边，始顶点的出边表的第一条边，Firstout 指示以指示以该顶点为终顶点的入边表的第一条边。该顶点为终顶点的入边表的第一条边。data Firstin Firstout4343数据结构4（清华大学）mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表的结构邻接多重表的结构4444数据结构4（清华大学）图的遍历与连通性图的遍历与连通性n从已给的连通图中某一顶点出发，

35、沿着一些边从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历一次，就叫做图的遍历(Graph Traversal)。n图中可能存在回路，且图的任一顶点都可能与图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。沿着某些边又回到了曾经访问过的顶点。n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组被访问过的辅助数组 visited 。4545数据结构4（清

36、华大学）n辅助数组辅助数组visited 的初始状态为的初始状态为 0,在图的遍在图的遍历过程中历过程中,一旦某一个顶点一旦某一个顶点 i 被访问被访问,就立即就立即让让visitedi为为 1,防止它被多次访问。防止它被多次访问。n图的遍历的分类图的遍历的分类:u深度优先搜索深度优先搜索 DFS(Depth First Search)u广度优先搜索广度优先搜索 BFS(Breadth First Search)4646数据结构4（清华大学）深度优先搜索深度优先搜索DFSDFS (Depth First Search)(Depth First Search)n深度优先搜索的示例深度优先搜索的示

37、例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树4747数据结构4（清华大学）nDFS 在访问图中某一在访问图中某一起始顶点起始顶点 v 后后,由由 v 出发出发,访问它的任一访问它的任一邻接顶点邻接顶点 w1;再从再从 w1 出发出发,访问访问与与 w1邻邻 接接但还但还没有访问过的顶点没有访问过的顶点 w2;然后再然后再从从 w2 出发出发,进行类似的访问进行类似的访问,如此进行下去如此进行下去,直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。接着接

38、着,退回一步退回一步,退到前一次刚访问过退到前一次刚访问过的顶点的顶点,看是否还有其它没有被访问的邻接顶看是否还有其它没有被访问的邻接顶点。点。如果有如果有,则访问此顶点则访问此顶点,之后再从此顶点之后再从此顶点出发出发,进行与前述类似的访问进行与前述类似的访问;如果没有如果没有,就就再退回一步进行搜索。重复上述过程再退回一步进行搜索。重复上述过程,直到连直到连通图中所有顶点都被访问过为止。通图中所有顶点都被访问过为止。4848数据结构4（清华大学）图的深度优先搜索算法图的深度优先搜索算法template void DFS(Graph&G,const T&v)/从顶点v出发对图G进行深度优先遍

39、历的主过程 int i,loc,n=G.NumberOfVertices();/顶点个数 bool*visited=new booln;/创建辅助数组 for(i=0;i n;i+)visited i=false;/辅助数组visited初始化loc=G.getVertexPos(v);DFS(G,loc,visited);/从顶点0开始深度优先搜索 delete visited;/释放visited;4949数据结构4（清华大学）templatevoid DFS(Graph&G,int v,bool visited)cout G.getValue(v);/访问顶点v visitedv=tru

40、e;/作访问标记 int w=G.getFirstNeighbor(v);/第一个邻接顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)DFS(G,w,visited);/若w未访问过,递归访问顶点w w=G.getNextNeighbor(v,w);/下一个邻接顶点 ;5050数据结构4（清华大学）广广 度度 优优 先先 搜搜 索索 BFSBFS (Breadth(Breadth First First Search)Search)n广度优先搜索的示例广度优先搜索的示例广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树ACDEGBFIHACDEGBFH1

41、23456789123456789I5151数据结构4（清华大学）nBFS在访问了起始顶点在访问了起始顶点 v 之后之后,由由 v 出发出发,依依次访问次访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1,w2,wt,然后再顺序访问然后再顺序访问 w1,w2,wt 的的所有还未被访问过的邻接顶点。再从这些访所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，访问过的邻接顶点，如此做下去，直到图如此做下去，直到图中所有顶点都被访问到为止。中所有顶点都被访问到为止。n广度优先搜索是一种分层的搜索过程广

42、度优先搜索是一种分层的搜索过程,每向前每向前走一步可能访问一批顶点走一步可能访问一批顶点,不像深度优先搜索不像深度优先搜索那样有往回退的情况。因此那样有往回退的情况。因此,广度优先搜索不广度优先搜索不是一个递归的过程。是一个递归的过程。5252数据结构4（清华大学）n为了实现逐层访问为了实现逐层访问,算法中使用了一个队列算法中使用了一个队列,以记忆正在访问的这一层和上一层的顶点以记忆正在访问的这一层和上一层的顶点,以以便于向下一层访问。便于向下一层访问。n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。，给被访问过的顶点加标记。temp

43、late void BFS(Graph&G,const T&v)int i,w,n=G.NumberOfVertices();/图中顶点个数图的广度优先搜索算法图的广度优先搜索算法5353数据结构4（清华大学）bool*visited=new booln;for(i=0;i n;i+)visitedi=false;int loc=G.getVertexPos(v);/取顶点号 cout G.getValue(loc);/访问顶点v visitedloc=true;/做已访问标记 Queue Q;Q.EnQueue(loc);/顶点进队列,实现分层访问 while(!Q.IsEmpty()/循环

44、,访问所有结点 Q.DeQueue(loc);w=G.getFirstNeighbor(loc);/第一个邻接顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)/若未访问过5454数据结构4（清华大学）cout G.getValue(w);/访问 visitedw=true;Q.EnQueue(w);/顶点w进队列 w=G.getNextNeighbor(loc,w);/找顶点loc的下一个邻接顶点 /外层循环，判队列空否 delete visited;5555数据结构4（清华大学）连通分量连通分量(Connected component)(Connected com

45、ponent)n当无向图为非连通图时，从图中某一顶点出当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索发，利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点，只能访算法不可能遍历到图中的所有顶点，只能访问到该顶点所在最大连通子图问到该顶点所在最大连通子图（连通分量）（连通分量）的的所有顶点。所有顶点。n若从无向图每一连通分量中的一个顶点出发若从无向图每一连通分量中的一个顶点出发进行遍历进行遍历,可求得无向图的所有连通分量。可求得无向图的所有连通分量。n例如，对于非连通的无向图，所有连通分量例如，对于非连通的无向图，所有连通分量的生成树组成了非连通图的生

46、成森林。的生成树组成了非连通图的生成森林。5656数据结构4（清华大学）ACDEBFGOIHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图的连通分量5757数据结构4（清华大学）重连通分量重连通分量 (Biconnected Component)(Biconnected Component)n在无向连通图在无向连通图G中中,当且仅当删去当且仅当删去G中的顶点中的顶点v及所有依附于及所有依附于v的所有边后的所有边后,可将图分割成两个可将图分割成两个或两个以上的连通分量，则称顶点或两个以上的连通分量，则称顶点v为为关节点关节点。n没有没有关节点关节点的连通图叫做重连通图。的连通图叫做

47、重连通图。n在重连通图上在重连通图上,任何一对顶点之间至少存在有任何一对顶点之间至少存在有两条路径两条路径,在删去某个顶点及与该顶点相关联在删去某个顶点及与该顶点相关联的边时的边时,也不破坏图的连通性。也不破坏图的连通性。6464数据结构4（清华大学）n一个连通图一个连通图G如果不是重连通图，那么它可以如果不是重连通图，那么它可以包括几个重连通分量。包括几个重连通分量。n在一个无向连通图在一个无向连通图G中中,重连通分量可以利用重连通分量可以利用深度优先生成树找到。深度优先生成树找到。n在图中各顶点旁标明的深度优先数在图中各顶点旁标明的深度优先数,给出进行给出进行深度优先搜索时各顶点访问的次序

48、。深度优先搜索时各顶点访问的次序。n深度优先生成树的深度优先生成树的根是根是关节点关节点的充要条件是它的充要条件是它至少有两个子女至少有两个子女。n其它顶点其它顶点 u 是是关节点关节点的充要条件是它至少有一的充要条件是它至少有一个子女个子女 w,从从 w 出发出发,不能通过不能通过 w、w 的子孙及的子孙及一条回边所组成的路径到达一条回边所组成的路径到达 u 的祖先的祖先。6565数据结构4（清华大学）ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有两根有两 个子女个子女关关关关节节节节点点点点关关关关节节节节点点点点关节点关节点关节点关节点6666数据

49、结构4（清华大学）最小生成树最小生成树 (minimum cost spanning tree)(minimum cost spanning tree)n使用不同的遍历图的方法，可以得到不同的生使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的成树；从不同的顶点出发，也可能得到不同的生成树。生成树。n按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生个顶点的连通网络的生成树有成树有 n 个顶点、个顶点、n-1条边。条边。n构造最小生成树构造最小生成树 假设有一个网络，用以表示假设有一个网络，用以表示 n 个城市之间架设通信线路，边上的权值代表个城市之间架

50、设通信线路，边上的权值代表架设通信线路的成本。如何架设才能使线路架架设通信线路的成本。如何架设才能使线路架设的成本达到最小？设的成本达到最小？6767数据结构4（清华大学）n构造最小生成树的准则构造最小生成树的准则v必须使用且仅使用该网络中的必须使用且仅使用该网络中的 n-1 条边来条边来联结网络中的联结网络中的 n 个顶点；个顶点；v不能使用产生回路的边；不能使用产生回路的边；v各边上的权值的总和达到最小。各边上的权值的总和达到最小。北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉347641583124192538222219313944506868数据结构4（清

51、华大学）北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉76241922221931北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉347641583124192538222219313944506969数据结构4（清华大学）克鲁斯卡尔克鲁斯卡尔(Kruskal)(Kruskal)算法算法n克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：设有一个有设有一个有 n 个顶点的连通网络个顶点的连通网络 N=V,E,最初先构造一个只有最初先构造一个只有 n 个顶点个顶点,没有边的非连没有边的非连通图通图 T=V,图中每个顶点自成一个连通图中每个顶

52、点自成一个连通分量。当在分量。当在 E 中选到一条具有最小权值的边时中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则若该边的两个顶点落在不同的连通分量上，则将此边加入到将此边加入到 T 中中;否则将此边舍去，重新选否则将此边舍去，重新选择一条权值最小的边。如此重复下去择一条权值最小的边。如此重复下去,直到所直到所有顶点在同一个连通分量上为止。有顶点在同一个连通分量上为止。7070数据结构4（清华大学）KruskalKruskal算法的伪代码描述算法的伪代码描述 T=;/T是最小生成树的边集合是最小生成树的边集合/E是带权无向图的边集合是带权无向图的边集合while(T 包

53、含的边少于包含的边少于n-1&E不空不空)从从 E 中选一条具有最小代价的边中选一条具有最小代价的边(v,w);从从 E 中删去中删去(v,w);如果如果(v,w)加到加到 T 中后不会产生回路中后不会产生回路,则将则将 (v,w)加入加入T;否则放弃否则放弃(v,w);if(T 中包含的边少于中包含的边少于n-1条条)cout 不是最小生成树不是最小生成树 endl;7171数据结构4（清华大学）n算法的框架算法的框架 利用利用最小堆最小堆(MinHeap)和和并查集并查集(DisjointSets)来实现来实现克鲁斯卡尔算法克鲁斯卡尔算法。n首先首先,利用利用最小堆最小堆来存放来存放E中的

54、所有的边中的所有的边,堆堆中每个结点的格式为中每个结点的格式为n在构造最小生成树过程中在构造最小生成树过程中,利用利用并查集并查集的运的运算检查依附一条边的两顶点算检查依附一条边的两顶点tail、head 是否在是否在同一连通分量同一连通分量(即即并查集的同一个子集合并查集的同一个子集合)上上,是则舍去这条边；否则将此边加入是则舍去这条边；否则将此边加入T,同时将同时将这两个顶点放在同一个连通分量上。这两个顶点放在同一个连通分量上。边的两个顶点位置 边的权值 tail head cost 7272数据结构4（清华大学）n随着各边逐步加入到最小生成树的边集合中随着各边逐步加入到最小生成树的边集合

55、中,各连通分量也在逐步合并各连通分量也在逐步合并,直到形成一个连通直到形成一个连通分量为止。分量为止。10504613228102514242216181250461325046132原图 (a)(b)构造最小生成树的过程构造最小生成树的过程7373数据结构4（清华大学）1012504613228102514242216181250461325046132101412原图 (c)(d)504613210141612(e)(f)(g)5046132101422161250461210251422161237474数据结构4（清华大学）最小生成树类定义最小生成树类定义const float max

56、Value=FLOAT_MAX /机器可表示的、问题中不可能出现的大数template struct MSTEdgeNode/树边结点的类定义 int tail,head;/两顶点位置 E cost;/边上的权值MSTEdgeNode():tail(-1),head(-1),cost(0)/构造函数;template 7575数据结构4（清华大学）class MinSpanTree/树的类定义protected:MSTEdgeNode*edgevalue;/边值数组 int maxSize,n;/最大元素个数和当前个数public:MinSpanTree(int sz=DefaultSize-

57、1):MaxSize(sz),n(0)edgevalue=new MSTEdgeNodesz;int Insert(MSTEdgeNode&item);7676数据结构4（清华大学）n在求解最小生成树时，可以用邻接矩阵存储图，在求解最小生成树时，可以用邻接矩阵存储图，也可以用邻接表存储图。算法中使用图的抽象也可以用邻接表存储图。算法中使用图的抽象基类的操作，无需考虑图及其操作的具体实现。基类的操作，无需考虑图及其操作的具体实现。#include heap.h#include UFSets.htemplate void Kruskal(Graph&G,MinSpanTree&MST)Kruska

58、lKruskal算法的实现算法的实现 7777数据结构4（清华大学）MSTEdgeNode ed;/边结点辅助单元 int u,v,count;int n=G.NumberOfVertices();/顶点数 int m=G.NumberOfEdges();/边数 MinHeap MSTEdgeNode H(m);/最小堆 UFSets F(n);/并查集 for(u=0;u n;u+)for(v=u+1;v n;v+)if(G.getWeight(u,v)!=maxValue)ed.tail=u;ed.head=v;/插入堆 ed.cost=G.getWeight(u,v);H.Insert(

59、ed);7878数据结构4（清华大学）count=1;/最小生成树边数计数 while(count n)/反复执行,取n-1条边 H.Remove(ed);/退出具最小权值的边 u=F.Find(ed.tail);v=F.Find(ed.head);/取两顶点所在集合的根u与v if(u!=v)/不是同一集合,不连通 F.Union(u,v);/合并,连通它们 MST.Insert(ed);/该边存入MST count+;；7979数据结构4（清华大学）出堆顺序出堆顺序 (0,5,10)选中选中 (2,3,12)选中选中(1,6,14)选中选中 (1,2,16)选中选中 (3,6,18)舍弃舍

60、弃(3,4,22)选中选中 (4,6,24)舍弃舍弃 (4,5,25)选中选中并查集原图-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-711211F5046132281025142422161812(0,5,10)(2,3,12)(1,6,14)(1,2,16)(3,4,22)(4,5,25)8080数据结构4（清华大学）普里姆普里姆(Prim)(Prim)算法算法n普里姆算法的基本思想：普里姆算法的基本思想：从连通网络从连通网络 N=V,E中的某一顶点中的某一顶点 u0

61、出发出发,选择与它关联的具有最小权值的边选择与它关联的具有最小权值的边(u0,v),将将其顶点加入到其顶点加入到生成树顶点集合生成树顶点集合U中。中。以后每一步从一个顶点在集合以后每一步从一个顶点在集合U中中,而另一个而另一个顶点不在集合顶点不在集合U中的各条边中选择权值最小的中的各条边中选择权值最小的边边(u,v),把它的顶点加入到把它的顶点加入到集合集合U中。如此继中。如此继续下去续下去,直到网络中的所有顶点都加入到生成直到网络中的所有顶点都加入到生成树顶点集合树顶点集合U中为止。中为止。8181数据结构4（清华大学）普里姆普里姆(Prim)(Prim)的伪代码描述的伪代码描述选定构造最小

62、生成树的出发顶点选定构造最小生成树的出发顶点u0;Vmst=u0，Emst=;while(Vmst包含的顶点少于包含的顶点少于n&E不空不空)从从E中选一条边中选一条边(u,v),u Vmstv V-Vmst,且具有最小代价且具有最小代价(cost);令令Vmst=Vmstv,Emst=Emst(u,v);将新选出的边从将新选出的边从E中剔除：中剔除：E=E-(u,v);if(Vmst包含的顶点少于包含的顶点少于n)cout 不是最小生成树不是最小生成树 endl;8282数据结构4（清华大学）252510504613228102514242216185046132504613210原图 (a

63、)(b)504613210(c)(d)(e)(f)504613210221250461210251422161232522128383数据结构4（清华大学）PrimPrim算法的实现算法的实现#include heap.htemplate void Prim(Graph&G,const T u0,MinSpanTree&MST)MSTEdgeNode ed;/边结点辅助单元 int i,u,v,count;int n=G.NumberOfVertices();/顶点数 int m=G.NumberOfEdges();/边数int u=G.getVertexPos(u0);/起始顶点号MinHe

64、ap MSTEdgeNode H(m);/最小堆8484数据结构4（清华大学）bool Vmst=new booln;/最小生成树顶点集合 for(i=0;i n;i+)Vmsti=false;Vmstu=true;/u 加入生成树 count=1;do /迭代 v=G.getFirstNeighbor(u);while(v!=-1)/检测u所有邻接顶点 if(!Vmstv)/v不在mst中 ed.tail=u;ed.head=v;ed.cost=G.getWeight(u,v);H.Insert(ed);/(u,v)加入堆 /堆中存所有u在mst中,v不在mst中的边 v=G.getNext

65、Neighbor(u,v);8585数据结构4（清华大学）while(!H.IsEmpty()&count n)H.Remove(ed);/选堆中具最小权的边 if(!Vmsted.head)MST.Insert(ed);/加入最小生成树 u=ed.head;Vmstu=true;/u加入生成树顶点集合 count+;break;while(count n);8686数据结构4（清华大学）n例子例子50461322810251424221618125046132281025142422161812H=(0,5,10),(0,1,28)ed=(0,5,10)Vmst=t,f,f,f,f,f,fV

66、mst=t,f,f,f,f,t,f8787数据结构4（清华大学）5046132281025142422161812H=(5,4,25),(0,1,28)ed=(5,4,25)Vmst=t,f,f,f,f,t,fVmst=t,f,f,f,t,t,f5046132281025142422161812H=(4,3,22),(4,6,24),(0,1,28)ed=(4,3,22)Vmst=t,f,f,f,t,t,fVmst=t,f,f,t,t,t,f8888数据结构4（清华大学）5046132281025142422161812H=(3,2,12),(3,6,18),(4,6,24),(0,1,28)ed=(3,2,12)Vmst=t,f,f,t,t,t,fVmst=t,f,t,t,t,t,f5046132281025142422161812H=(2,1,16),(3,6,18),(4,6,24),(0,1,28)ed=(2,1,16)Vmst=t,f,t,t,t,t,fVmst=t,t,t,t,t,t,f8989数据结构4（清华大学）5046132281025142422161812H=(1