北京师范大学数据结构教学资料图市公开课金奖市赛课一等奖课件.pptx

146-146-1 1n图基本概念图基本概念n图存储表示图存储表示n图遍历与连通性图遍历与连通性 n最小生成树最小生成树n最短路径最短路径 n活动网络活动网络第八章第八章 图图第1页第1页146-146-2 2图基本概念图基本概念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 一条单向通路一条单向通路,它是有方向。它是有方向。第2页第2页146-146-3 3 n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序。在无向图中，顶点对是有序。在无向图中，顶点对(x,y)是无序。是无序。n完全图完全图 若有若有 n 个顶点无向图有个顶点无向图有 n(n-1)/2 条边条边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点有向图有个顶点有向图有n(n-1)条边条边,则此图为完全有向图。则此图为完全有向图。00001111222265433第3页第3页146-146-4 4 n邻接顶点邻接顶点 假如假如(u,v)是是 E(G)中一条边，则中一条边，则称称 u 与与 v 互为邻接顶点互为邻接顶点。n子图子图 设有两个图设有两个图G(V,E)和和G(V,E)。若若V V 且且E E,则称图则称图G是图是图G子图。子图。n权权 一些图边含有与它相关数一些图边含有与它相关数,称之为权。这称之为权。这种带权图叫做网络。种带权图叫做网络。子图子图01230130123023第4页第4页146-146-5 5n顶点度顶点度 一个顶点一个顶点v度是与它相关联边条数。记度是与它相关联边条数。记作作TD(v)。在有向图中。在有向图中,顶点度等于该顶点入顶点度等于该顶点入度与出度之和。度与出度之和。n顶点顶点 v 入度入度是以是以 v 为终点有向边条数为终点有向边条数,记作记作 ID(v);顶点顶点 v 出度出度是以是以 v 为始点有向边条数为始点有向边条数,记作记作 OD(v)。n路径路径 在图在图 G(V,E)中中,若从顶点若从顶点 vi 出发出发,沿沿一些边通过一些顶点一些边通过一些顶点 vp1,vp2,vpm，到达顶，到达顶点点vj。则称顶点序列。则称顶点序列(vi vp1 vp2.vpm vj)为从顶为从顶点点vi 到顶点到顶点 vj 路径。它通过边路径。它通过边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E边。边。第5页第5页146-146-6 6n路径长度路径长度 非带权图路径长度是指此路径上边非带权图路径长度是指此路径上边条数。带权图路径长度是指路径上各边权之和。条数。带权图路径长度是指路径上各边权之和。n简朴路径简朴路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互相重复互相重复,则称这样路径为简朴路径。则称这样路径为简朴路径。n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重叠重叠,则称这样路径为回路或环。则称这样路径为回路或环。012301230123第6页第6页146-146-7 7n连通图与连通分量连通图与连通分量 在在无向图无向图中中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通。假如是连通。假如图中任意一对顶点都是连通图中任意一对顶点都是连通,则称此图是连通则称此图是连通图。非连通图极大连通子图叫做连通分量。图。非连通图极大连通子图叫做连通分量。n强连通图与强连通分量强连通图与强连通分量 在在有向图有向图中中,若对于若对于每一对顶点每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi路径路径,则称此图是强连通图。非强连通图极则称此图是强连通图。非强连通图极大强连通子图叫做强连通分量。大强连通子图叫做强连通分量。n生成树生成树 一个连通图生成树是其极小连通子图，一个连通图生成树是其极小连通子图，在在 n 个顶点情形下，有个顶点情形下，有 n-1 条边。条边。第7页第7页146-146-8 8图抽象数据类型图抽象数据类型nclass Graph n/对象:由一个顶点非空集合和一个边集合构成n/每条边由一个顶点对来表示。npublic:n Graph();/建立一个空图n void insertVertex(const T&vertex);n /插入一个顶点vertex,该顶点暂时没有入边n void insertEdge(int v1,int v2,int weight);n /在图中插入一条边(v1,v2,w)n void removeVertex(int v);n /在图中删除顶点v和所有关联到它边 第8页第8页146-146-9 9 void removeEdge(int v1,int v2);/在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点,则返回true,不然返回false T getWeight(int v1,int v2);/函数返回边(v1,v2)权值 int getFirstNeighbor(int v);/给出顶点 v 第一个邻接顶点位置 int getNextNeighbor(int v,int w);/给出顶点 v 某邻接顶点 w 下一个邻接顶点;第9页第9页146-146-1010图存储表示图存储表示n图模板基类图模板基类 在模板类定义中数据类型参数在模板类定义中数据类型参数表表 中，中，T是顶点数据类型，是顶点数据类型，E是边上所附数据类型。是边上所附数据类型。n这个模板基类是按照最复杂情况（即带权无这个模板基类是按照最复杂情况（即带权无向图）来定义，假如需要使用非带权图，可向图）来定义，假如需要使用非带权图，可将数据类型参数表将数据类型参数表 改为改为。n假如使用是有向图，也能够对程序做相应改假如使用是有向图，也能够对程序做相应改动。动。第10页第10页146-146-11 11图模板基类图模板基类 const int maxWeight=;/无穷大值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph /图类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点数 int getVertexPos(T vertex);/给出顶点vertex在图中位置public:第11页第11页146-146-1212 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 getWeight(int v1,int v2);/取边上权值 virtual int getFirstNeighbor(int v);/取顶点 v 第一个邻接顶点第12页第12页146-146-1313virtual 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(int v);/删去顶点 v 和所有与相关联边 virtual bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);第13页第13页146-146-1414邻接矩阵邻接矩阵 (Adjacency Matrix)(Adjacency Matrix)n在图邻接矩阵表示中，有一个统计各个顶点在图邻接矩阵表示中，有一个统计各个顶点信息信息顶点表顶点表，尚有一个表示各个顶点之间关，尚有一个表示各个顶点之间关系系邻接矩阵邻接矩阵。n设图设图 A=(V,E)是一个有是一个有 n 个顶点图个顶点图,图邻接图邻接矩阵是一个二维数组矩阵是一个二维数组 A.edgenn，定义：，定义：第14页第14页146-146-1515n无向图邻接矩阵是对称无向图邻接矩阵是对称;n有向图邻接矩阵也许是不对称。有向图邻接矩阵也许是不对称。0123012第15页第15页146-146-1616n在有向图中在有向图中,统计第统计第 i 行行 1 个数可得顶点个数可得顶点 i 出出度度，统计第，统计第 j 列列 1 个数可得顶点个数可得顶点 j 入度入度。n在无向图中在无向图中,统计第统计第 i 行行(列列)1 个数可得顶点个数可得顶点i 度度。网络邻接矩阵网络邻接矩阵第16页第16页146-146-1717863129542031用邻接矩阵表示图类定义用邻接矩阵表示图类定义template class Graphmtx:public Graph friend istream&operator (istream&in,Graphmtx&G);/输入第17页第17页146-146-1818friend 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 getWeight(int v1,int v2)/取边(v1,v2)上权值 return v1!=-1&v2!=-1?Edgev1v2:0;int getFirstNeighbor(int v);/取顶点 v 第一个邻接顶点第19页第19页146-146-2020 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 removeVertex(int v);/删去顶点 v 和所有与它相关联边 bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);第20页第20页146-146-2121template 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;/邻接矩阵 for(i=0;i maxVertices;i+)/矩阵初始化 for(j=0;j maxVertices;j+)Edgeij=(i=j)？0:maxWeight;第21页第21页146-146-2222template 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;第22页第22页146-146-2323template 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;第23页第23页146-146-2424n邻接表是邻接矩阵改进形式。为此需要把邻邻接表是邻接矩阵改进形式。为此需要把邻接矩阵各行分别组织为一个单链表。接矩阵各行分别组织为一个单链表。n在邻接表中，同一个顶点发出边链接在同一在邻接表中，同一个顶点发出边链接在同一个边链表中，每一个链结点代表一条边（边个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点下标结点），结点中有另一顶点下标 dest 和指针和指针 link。对于带权图，边结点中还要保留该边权。对于带权图，边结点中还要保留该边权值值cost。n顶点表第顶点表第 i 个顶点中保留该顶点数据，以及它个顶点中保留该顶点数据，以及它相应边链表头指针相应边链表头指针adj。邻接表邻接表 (Adjacency List)(Adjacency List)第24页第24页146-146-2525ABCDdata adjABCD0123dest linkdest link 130210无向图邻接表无向图邻接表n统计某顶点相应边链表中结点个数，可得该顶统计某顶点相应边链表中结点个数，可得该顶点度。点度。n某条边某条边(vi,vj)在邻接表中有两个边结点，分别在邻接表中有两个边结点，分别在第在第 i 个顶点和第个顶点和第 j 个顶点相应边链表中。个顶点相应边链表中。第25页第25页146-146-2626data adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻接表逆邻接表(入边表入边表)102 011有向图邻接表和逆邻接表有向图邻接表和逆邻接表ABC第26页第26页146-146-2727BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 (带权图带权图)邻接表邻接表n统计出边表中结点个数，得到该顶点出度；统计出边表中结点个数，得到该顶点出度；n统计入边表中结点个数，得到该顶点入度。统计入边表中结点个数，得到该顶点入度。第27页第27页146-146-2828n在邻接表边链表中，各个边结点链入顺序任意，在邻接表边链表中，各个边结点链入顺序任意，视边结点输入顺序而定。视边结点输入顺序而定。n设图中有设图中有 n 个顶点，个顶点，e 条边，则用邻接表表示条边，则用邻接表表示无向图时，需要无向图时，需要 n 个顶点结点，个顶点结点，2e 个边结点；个边结点；用邻接表表示有向图时，若不考虑逆邻接表，用邻接表表示有向图时，若不考虑逆邻接表，只需只需 n 个顶点结点，个顶点结点，e 个边结点。个边结点。n当当 e 远远小于远远小于 n2 时，能够节约大量存储空间。时，能够节约大量存储空间。另外，把同一个顶点所有边链接在一个单链表另外，把同一个顶点所有边链接在一个单链表中，也使得图操作更为便捷。中，也使得图操作更为便捷。第28页第28页146-146-2929用邻接表表示图类定义用邻接表表示图类定义 template struct Edge /边结点定义 int dest;/边另一顶点位置 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;/判边等否;第29页第29页146-146-3030template struct Vertex /顶点定义 T data;/顶点名字Edge*adj;/边链表头指针;template class Graphlnk:public Graph /图类定义friend istream&operator (istream&in,Graphlnk&G);/输入friend ostream&operator (ostream&out,Graphlnk&G);/输出第30页第30页146-146-3131private: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(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);第32页第32页146-146-3333template Graphlnk:Graphlnk(int sz)/结构函数：建立一个空邻接表 maxVertices=sz;numVertices=0;numEdges=0;NodeTable=new VertexmaxVertices;/创建顶点表数组 if(NodeTable=NULL)cerr 存储分派错！存储分派错！endl;exit(1);for(int i=0;i maxVertices;i+)NodeTablei.adj=NULL;第33页第33页146-146-3434template 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 NodeTable;/删除顶点表数组第34页第34页146-146-3535template int Graphlnk:getFirstNeighbor(int v)/给出顶点位置为 v 第一个邻接顶点位置,/假如找不到,则函数返回-1 if(v!=-1)/顶点顶点v存在存在 Edge*p=NodeTablev.adj;/相应边链表第一个边结点if(p!=NULL)return p-dest;/存在,返回第一个邻接顶点 return-1;/第一个邻接顶点不存在第35页第35页146-146-3636template int Graphlnk:getNextNeighbor(int v,int w)/给出顶点v邻接顶点w下一个邻接顶点位置,/若没有下一个邻接顶点,则函数返回-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;/下一邻接顶点不存在第36页第36页146-146-3737邻接多重表邻接多重表 (Adjacency Multilist)(Adjacency Multilist)n在邻接多重表中在邻接多重表中,每一条边只有一个边结点。为每一条边只有一个边结点。为相关边处理提供了以便。相关边处理提供了以便。n无向图情形无向图情形边结点结构边结点结构n其中其中,mark 是统计是否处理过标识是统计是否处理过标识;vertex1和和vertex2是该边两顶点位置。是该边两顶点位置。path1域是链接指针域是链接指针,指向下一条依附顶点指向下一条依附顶点vertex1边；边；path2 是指向是指向下一条依附顶点下一条依附顶点vertex2边链接指针。边链接指针。mark vertex1 vertex2 path1 path2第37页第37页146-146-3838n需要时还可设置一个存储与该边相关权值域需要时还可设置一个存储与该边相关权值域 cost。顶点结点结构顶点结点结构n顶点信息结点表以顺序表方式组织顶点信息结点表以顺序表方式组织,每一个顶点每一个顶点结点有两个数据组员：其中，结点有两个数据组员：其中，data 存储与该顶存储与该顶点相关信息，点相关信息，Firstout 是批示第一条依附该顶点是批示第一条依附该顶点边指针。边指针。n在邻接多重表中在邻接多重表中,所有依附同一个顶点边都链所有依附同一个顶点边都链接在同一个单链表中。接在同一个单链表中。data Firstout第38页第38页146-146-3939mark vtx1 vtx2 path1 path2 0 10 21 3e1e2e3data FoutABCD0123e1e2e3ABCDn从顶点从顶点 i 出发出发,能够循链找到所有依附于该顶能够循链找到所有依附于该顶点边，也能够找到它所有邻接顶点。点边，也能够找到它所有邻接顶点。邻接多重表结构邻接多重表结构第39页第39页146-146-4040n有向图情形有向图情形n在用邻接表表示有向图时在用邻接表表示有向图时,有时需要同时使用有时需要同时使用邻接表和逆邻接表。用有向图邻接多重表邻接表和逆邻接表。用有向图邻接多重表(十十字链表字链表)可把两个表结合起来表示。可把两个表结合起来表示。边结点结构边结点结构n其中，其中，mark是处理标识；是处理标识；vertex1和和vertex2指指明该有向边始顶点和终顶点位置。明该有向边始顶点和终顶点位置。path1是指是指向向始顶点与该边相同始顶点与该边相同下一条边指针；下一条边指针；path2是是指向指向终顶点与该边相同终顶点与该边相同下一条边指针。需要时下一条边指针。需要时还可有权值域还可有权值域cost。mark vertex1 vertex2 path1 path2第40页第40页146-146-4141u顶点结点结构顶点结点结构n每个顶点有一个结点，它相称于出边表和入边每个顶点有一个结点，它相称于出边表和入边表表头结点：其中，数据组员表表头结点：其中，数据组员data存储与该顶存储与该顶点相关信息，指针点相关信息，指针Firstout 批示以该顶点为始批示以该顶点为始顶点出边表第一条边，顶点出边表第一条边，Firstin 批示以该顶点为批示以该顶点为终顶点入边表第一条边。终顶点入边表第一条边。data Firstin Firstout第41页第41页146-146-4242mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表结构邻接多重表结构第42页第42页146-146-4343画画出出在在下下图图所所表表示示有有向向图图中中删删除除顶顶点点V3V3后十字链表存储结构图后十字链表存储结构图。第43页第43页146-146-4444图遍历与连通性图遍历与连通性n从已给连通图中某一顶点出发，沿着一些边访从已给连通图中某一顶点出发，沿着一些边访遍图中所有顶点，且使每个顶点仅被访问一次，遍图中所有顶点，且使每个顶点仅被访问一次，就叫做图遍历就叫做图遍历(Graph Traversal)。n图中也许存在回路，且图任一顶点都也许与其图中也许存在回路，且图任一顶点都也许与其它顶点相通，在访问完某个顶点之后也许会沿它顶点相通，在访问完某个顶点之后也许会沿着一些边又回到了曾经访问过顶点。着一些边又回到了曾经访问过顶点。n为了避免重复访问，可设置一个标志顶点是否为了避免重复访问，可设置一个标志顶点是否被访问过辅助数组被访问过辅助数组 visited 。第44页第44页146-146-4545n辅助数组辅助数组visited 初始状态为初始状态为 0,在图遍历过在图遍历过程中程中,一旦某一个顶点一旦某一个顶点 i 被访问被访问,就马上让就马上让visitedi为为 1,预防它被多次访问。预防它被多次访问。n图遍历分类图遍历分类:u深度优先搜索深度优先搜索 DFS(Depth First Search)u广度优先搜索广度优先搜索 BFS(Breadth First Search)第45页第45页146-146-4646深度优先搜索深度优先搜索DFSDFS (Depth First Search)(Depth First Search)n深度优先搜索示例深度优先搜索示例ACDEGBFIHACDEGBFIH123456789123456789迈进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树第46页第46页146-146-4747nDFS 在访问图中某一在访问图中某一起始顶点起始顶点 v 后后,由由 v 出发出发,访问它任一访问它任一邻接顶点邻接顶点 w1;再从再从 w1 出发出发,访问访问与与 w1邻邻 接接但还但还没有访问过顶点没有访问过顶点 w2;然后再从然后再从 w2 出发出发,进行类似访问进行类似访问,如此进行下去如此进行下去,直至到直至到达所有邻接顶点都被访问过顶点达所有邻接顶点都被访问过顶点 u 为止。为止。接着接着,退回一步退回一步,退到前一次刚访问过顶点退到前一次刚访问过顶点,看是否看是否尚有其它没有被访问邻接顶点。尚有其它没有被访问邻接顶点。假如有假如有,则访则访问此顶点问此顶点,之后再从此顶点出发之后再从此顶点出发,进行与前述类进行与前述类似访问似访问;假如没有假如没有,就再退回一步进行搜索。重就再退回一步进行搜索。重复上述过程复上述过程,直到连通图中所有顶点都被访问直到连通图中所有顶点都被访问过为止。过为止。第47页第47页146-146-4848图深度优先搜索算法图深度优先搜索算法template void DFS(Graph&G,const T&v)/从顶点v出发对图G进行深度优先遍历主过程 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第48页第48页146-146-4949templatevoid DFS(Graph&G,int v,bool visited)cout G.getValue(v);/访问顶点v visitedv=true;/作访问标识 int w=G.getFirstNeighbor(v);/第一个邻接顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)DFS(G,w,visited);/若w未访问过,递归访问顶点w w=G.getNextNeighbor(v,w);/下一个邻接顶点 第49页第49页146-146-5050广广 度度 优优 先先 搜搜 索索 BFSBFS (Breadth(Breadth First First Search)Search)n广度优先搜索示例广度优先搜索示例广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树ACDEGBFIHACDEGBFH123456789123456789I第50页第50页146-146-5151nBFS在访问了起始顶点在访问了起始顶点 v 之后之后,由由 v 出发出发,依次依次访问访问 v 各个未被访问过邻接顶点各个未被访问过邻接顶点 w1,w2,wt,然后再顺序访问然后再顺序访问 w1,w2,wt 所有尚未被访问所有尚未被访问过邻接顶点。再从这些访问过顶点出发，再过邻接顶点。再从这些访问过顶点出发，再访问它们所有尚未被访问过邻接顶点，访问它们所有尚未被访问过邻接顶点，如如此做下去，直到图中所有顶点都被访问到为此做下去，直到图中所有顶点都被访问到为止。止。n广度优先搜索是一个分层搜索过程广度优先搜索是一个分层搜索过程,每向前走每向前走一步也许访问一批顶点一步也许访问一批顶点,不像深度优先搜索那不像深度优先搜索那样有往回退情况。因此样有往回退情况。因此,广度优先搜索不是一广度优先搜索不是一个递归过程。个递归过程。第51页第51页146-146-5252n为了实现逐层访问为了实现逐层访问,算法中使用了一个队列算法中使用了一个队列,以以记忆正在访问这一层和上一层顶点记忆正在访问这一层和上一层顶点,以便于向以便于向下一层访问。下一层访问。n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过顶点加标识。，给被访问过顶点加标识。template void BFS(Graph&G,const T&v)int i,w,n=G.NumberOfVertices();/图中顶点个数图广度优先搜索算法图广度优先搜索算法第52页第52页146-146-5353 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()/循环,访问所有结点 Q.DeQueue(loc);w=G.getFirstNeighbor(loc);/第一个邻接顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)/若未访问过第53页第53页146-146-5454 cout G.getValue(w);/访问 visitedw=true;Q.EnQueue(w);/顶点w进队列 w=G.getNextNeighbor(loc,w);/找顶点loc下一个邻接顶点 /外层循环，判队列空否 delete visited;第54页第54页146-146-5555连通分量连通分量 (Connected component)(Connected component)n当无向图为非连通图时，从图中某一顶点出当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或广度优先搜索发，利用深度优先搜索算法或广度优先搜索算法不也许遍历到图中所有顶点，只能访问算法不也许遍历到图中所有顶点，只能访问到该顶点所在最大连通子图到该顶点所在最大连通子图（连通分量）（连通分量）所所有顶点。有顶点。n若从无向图每一连通分量中一个顶点出发进若从无向图每一连通分量中一个顶点出发进行遍历行遍历,可求得无向图所有连通分量。可求得无向图所有连通分量。n比如，对于非连通无向图，所有连通分量生比如，对于非连通无向图，所有连通分量生成树构成了非连通图生成森林。成树构成了非连通图生成森林。第55页第55页146-146-5656ACDEBFGOIHJNMLK非连通无向图AHKCDEIBFOGJNML非连通图连通分量第56页第56页146-146-6363重连通分量重连通分量 (Biconnected Component)(Biconnected Component)n在无向连通图G中,当且仅当删去G中顶点v及所有依附于v所有边后,可将图分割成两个或两个以上连通分量，则称顶点v为关节点。n没相关节点连通图叫做重连通图。n在重连通图上,任何一对顶点之间至少存在有两条路径,在删去某个顶点及与该顶点相关联边时,也不破坏图连通性。第63页第63页146-146-6464n一个连通图一个连通图G假如不是重连通图，那么它能够假如不是重连通图，那么它能够包括几种重连通分量。包括几种重连通分量。n在一个无向连通图在一个无向连通图G中中,重连通分量能够利用重连通分量能够利用深度优先生成树找到。深度优先生成树找到。n在图中各在图中各顶点旁标明深度优先数顶点旁标明深度优先数,给出进行深给出进行深度优先搜索时各顶点访问顺序。度优先搜索时各顶点访问顺序。n深度优先生成树深度优先生成树根是根是关节点关节点充要条件是它至少充要条件是它至少有两个子女有两个子女。n其它顶点其它顶点 u 是是关节点关节点充要条件是它至少有一个充要条件是它至少有一个子女子女 w,从从 w 出发出发,不能通过不能通过 w、w 子孙及一条子孙及一条回边所构成路径到达回边所构成路径到达 u 祖先祖先。第64页第64页146-146-6565ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有两根有两 个子女个子女关关关关节节节节点点点点关关关关节节节节点点点点关节点关节点关节点关节点第65页第65页146-146-6666最小生成树最小生成树 (minimum cost spanning tree)(minimum cost spanning tree)n使用不同遍历图方法，能够得到不同生成树；从不同顶点出发，也可能得到不同生成树。n按照生成树定义，n 个顶点连通网络生成树有 n 个顶点、n-1条边。n结构最小生成树 假设有一个网络，用以表示 n 个城市之间架设通信线路，边上权值代表架设通信线路成本。怎样架设才干使线路架设成本达到最小？第66页第66页146-146-6767n结构最小生成树准则结构最小生成树准则v必须使用且仅使用该网络中必须使用且仅使用该网络中 n-1 条边来联条边来联结网络中结网络中 n 个顶点；个顶点；v不能使用产生回路边；不能使用产生回路边；v各边上权值总和达到最小。各边上权值总和达到最小。北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉34764158312419253822221931394450第67页第67页146-146-6868北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉76241922221931北京北京 天津天津南京南京上海上海广州广州西安西安成都成都昆明昆明武汉武汉34764158312419253822221931394450第68页第68页146-146-6969克鲁斯卡尔克鲁斯卡尔 (Kruskal)(Kruskal)算法算法n克鲁斯卡尔算法基本思想：n设有一个有 n 个顶点连通网络 N=V,E,最初先结构一个只有 n 个顶点,没有边非连通图 T=V,图中每个顶点自成一个连通分量。当在 E 中选到一条含有最小权值边时,若该边两个顶点落在不同连通分量上，则将此边加入到 T 中;不然将此边舍去，重新选择一条权值最小边。如此重复下去,直到全部顶点在同一个连通分量上为止。第69页第69页146-146-7070KruskalKruskal算法伪代码描述算法伪代码描述 T=;/T是最小生成树边集合是最小