第八章-图-数据结构(用面向对象的方法与C-语言描述)(第2版)课件.ppt

1、1 1第八章 图清华大学计算机系清华大学计算机系殷人昆殷人昆 王王 宏宏146-146-2 2n图的基本概念图的基本概念n图的存储表示图的存储表示n图的遍历与连通性图的遍历与连通性 n最小生成树最小生成树n最短路径最短路径 n活动网络活动网络第八章第八章 图图146-146-3 3图的基本概念图的基本概念n图定义图定义 图是由顶点集合图是由顶点集合(vertex)及顶点间的及顶点间的关系集合组成的一种数据结构：关系集合组成的一种数据结构：Graph(V,E)其中其中 V=x|x 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合；E=(x,y)|x,y V 或或 E=|x,y

2、 V&Path(x,y)是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)集合。集合。Path(x,y)表示从表示从 x 到到 y 的一条单向通的一条单向通路路,它是有方向的。它是有方向的。146-146-4 4 n有向图与无向图有向图与无向图 在有向图中，顶点对在有向图中，顶点对 是有序的。在无向图中，顶点对是有序的。在无向图中，顶点对(x,y)是无序是无序的。的。n完全图完全图 若有若有 n 个顶点的无向图有个顶点的无向图有 n(n-1)/2 条条边边,则此图为完全无向图。有则此图为完全无向图。有 n 个顶点的有向个顶点的有向图有图有n(n-1)条边条边,则此

3、图为完全有向图。则此图为完全有向图。00001111222265433146-146-5 5 n邻接顶点邻接顶点 如果如果(u,v)是是 E(G)中的一条边，中的一条边，则称则称 u 与与 v 互为邻接顶点互为邻接顶点。n子图子图 设有两个图设有两个图G(V,E)和和G(V,E)。若若V V 且且E E,则称图则称图G是图是图G的子图。的子图。n权权 某些图的边具有与它相关的数某些图的边具有与它相关的数,称之为权。称之为权。这种带权图叫做网络。这种带权图叫做网络。子图子图01230130123023146-146-6 6n顶点的度顶点的度 一个顶点一个顶点v的度是与它相关联的边的度是与它相关联

4、的边的条数。记作的条数。记作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 到顶

5、点到顶点 vj 的路径。它经过的边的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应是属于应是属于E的边。的边。146-146-7 7n路径长度路径长度 非带权图的路径长度是指此路径上非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的条数。带权图的路径长度是指路径上各边的权之和。边的权之和。n简单路径简单路径 若路径上各顶点若路径上各顶点 v1,v2,.,vm 均不均不 互相重复互相重复,则称这样的路径为简单路径。则称这样的路径为简单路径。n回路回路 若路径上第一个顶点若路径上第一个顶点 v1 与最后一个顶与最后一个顶点点vm 重合重合,则称这

6、样的路径为回路或环。则称这样的路径为回路或环。012301230123146-146-8 8n连通图与连通分量连通图与连通分量 在无向图中在无向图中,若从顶点若从顶点v1到顶点到顶点v2有路径有路径,则称顶点则称顶点v1与与v2是连通的。是连通的。如果图中任意一对顶点都是连通的如果图中任意一对顶点都是连通的,则称此图则称此图是连通图。非连通图的极大连通子图叫做连是连通图。非连通图的极大连通子图叫做连通分量。通分量。n强连通图与强连通分量强连通图与强连通分量 在有向图中在有向图中,若对于若对于每一对顶点每一对顶点vi和和vj,都存在一条从都存在一条从vi到到vj和从和从vj到到vi的路径的路径,

7、则称此图是强连通图。非强连通图则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。的极大强连通子图叫做强连通分量。n生成树生成树 一个连通图的生成树是其极小连通一个连通图的生成树是其极小连通子图，在子图，在 n 个顶点的情形下，有个顶点的情形下，有 n-1 条边。条边。146-146-9 9图的抽象数据类型图的抽象数据类型class Graph/对象:由一个顶点的非空集合和一个边集合构成/每条边由一个顶点对来表示。public:Graph();/建立一个空的图 void insertVertex(const T&vertex);/插入一个顶点vertex,该顶点暂时没有入边 void

8、 insertEdge(int v1,int v2,int weight);/在图中插入一条边(v1,v2,w)void removeVertex(int v);/在图中删除顶点v和所有关联到它的边 146-146-1010 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 getNe

9、xtNeighbor(int v,int w);/给出顶点 v 的某邻接顶点 w 的下一个邻接顶点;146-146-11 11图的存储表示图的存储表示n图的模板基类图的模板基类 在模板类定义中的数据类型在模板类定义中的数据类型参数表参数表 中，中，T是顶点数据的是顶点数据的类型，类型，E是边上所附数据的类型。是边上所附数据的类型。n这个模板基类是按照最复杂的情况（即带权这个模板基类是按照最复杂的情况（即带权无向图）来定义的，如果需要使用非带权图，无向图）来定义的，如果需要使用非带权图，可将数据类型参数表可将数据类型参数表 改为改为。n如果使用的是有向图，也可以对程序做相应如果使用的是有向图，也

10、可以对程序做相应的改动。的改动。146-146-1212图的模板基类图的模板基类 const int maxWeight=;/无穷大的值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph /图的类定义protected:int maxVertices;/图中最大顶点数 int numEdges;/当前边数 int numVertices;/当前顶点数 int getVertexPos(T vertex);/给出顶点vertex在图中位置public:146-146-1313 Graph(int sz=DefaultVer

11、tices);/构造函数 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 的第一个邻接顶点146-14

12、6-1414virtual 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);146-146-151

13、5邻接矩阵邻接矩阵 (Adjacency Matrix)(Adjacency Matrix)n在图的邻接矩阵表示中，有一个记录各个顶在图的邻接矩阵表示中，有一个记录各个顶点信息的点信息的顶点表顶点表，还有一个表示各个顶点之，还有一个表示各个顶点之间关系的间关系的邻接矩阵邻接矩阵。n设图设图 A=(V,E)是一个有是一个有 n 个顶点的图个顶点的图,图的图的邻接矩阵是一个二维数组邻接矩阵是一个二维数组 A.edgenn，定义：，定义：,),(,.否否则则或或者者如如果果01EdgeAEjiEjiji146-146-1616n无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的;n有向图的邻接矩阵可能

14、是不对称的。有向图的邻接矩阵可能是不对称的。0101101001011010A.edge0123012000101010A.edge146-146-1717n在有向图中在有向图中,统计第统计第 i 行行 1 的个数可得顶点的个数可得顶点 i 的的出度出度，统计第，统计第 j 列列 1 的个数可得顶点的个数可得顶点 j 的的入入度度。n在无向图中在无向图中,统计第统计第 i 行行(列列)1 的个数可得顶的个数可得顶点点i 的的度度。网络的邻接矩阵网络的邻接矩阵jiji,ji,jiji,ji,jijiji若若或或且且若若或或且且若若,)(,)(),(0EEEEWA.edge146-146-1818

15、068053290410A.edge863129542031用邻接矩阵表示的图的类定义用邻接矩阵表示的图的类定义template class Graphmtx:public Graph friend istream&operator (istream&in,Graphmtx&G);/输入146-146-1919friend ostream&operator (ostream&out,Graphmtx&G);/输出private:T*VerticesList;/顶点表 E*Edge;/邻接矩阵int getVertexPos(T vertex)/给出顶点vertex在图中的位置 for(int

16、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 的第一个邻接顶点146-146-2121 int getNextNeighbor(int v,int w);/取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex(const T vertex);/插入顶点vertex bool insertEdge(int v1,int v2,E

17、 cost);/插入边(v1,v2),权值为cost bool removeVertex(int v);/删去顶点 v 和所有与它相关联的边 bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);146-146-2222template 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 maxVe

18、rtices;i+)Edgei=new intmaxVertices;/邻接矩阵 for(i=0;i maxVertices;i+)/矩阵初始化 for(j=0;j maxVertices;j+)Edgeij=(i=j)？0:maxWeight;146-146-2323template int Graphmtx:getFirstNeighbor(int v)/给出顶点位置为v的第一个邻接顶点的位置,/如果找不到,则函数返回-1 if(v!=-1)for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return co

19、l;return-1;146-146-2424template 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;146-146-2525n邻接表是邻接矩阵的改进形式。为此需要把邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的各行分别组织为一个单链表。邻接矩阵的各行分别组织为一个单链表。n在邻接表中，同一个顶

20、点发出的边链接在同在邻接表中，同一个顶点发出的边链接在同一个边链表中，每一个链结点代表一条边一个边链表中，每一个链结点代表一条边（边结点），结点中有另一顶点的下标（边结点），结点中有另一顶点的下标 dest 和指针和指针 link。对于带权图，边结点中还要保。对于带权图，边结点中还要保存该边的权值存该边的权值cost。n顶点表的第顶点表的第 i 个顶点中保存该顶点的数据，个顶点中保存该顶点的数据，以及它对应边链表的头指针以及它对应边链表的头指针adj。邻接表邻接表 (Adjacency List)(Adjacency List)146-146-2626ABCDdata adjABCD0123d

21、est linkdest link 130210无向图的邻接表无向图的邻接表n统计某顶点对应边链表中结点个数，可得该顶统计某顶点对应边链表中结点个数，可得该顶点的度。点的度。n某条边某条边(vi,vj)在邻接表中有两个边结点，分别在邻接表中有两个边结点，分别在第在第 i 个顶点和第个顶点和第 j 个顶点对应的边链表中。个顶点对应的边链表中。146-146-2727data adjABC012dest linkdest link 邻接表邻接表(出边表出边表)data adjABC012dest link逆邻接表逆邻接表(入边表入边表)102 011有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表

22、ABC146-146-2828BACD69528data adjABCD0123dest cost link 1 53 62 83 21 9(出边表出边表)(顶点表顶点表)网络网络 (带权图带权图)的邻接表的邻接表n统计出边表中结点个数，得到该顶点的出度；统计出边表中结点个数，得到该顶点的出度；n统计入边表中结点个数，得到该顶点的入度。统计入边表中结点个数，得到该顶点的入度。146-146-2929n在邻接表的边链表中，各个边结点的链入顺序在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。任意，视边结点输入次序而定。n设图中有设图中有 n 个顶点，个顶点，e 条边，则用邻接表

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

24、边结点的定义 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;/判边等否;146-146-3131template struct Vertex /顶点的定义 T data;/顶点的名字Edge*adj;/边链表的头指针;template class Graphlnk:public Graph /图的类

25、定义friend istream&operator (istream&in,Graphlnk&G);/输入friend ostream&operator (ostream&out,Graphlnk&G);/输出146-146-3232private: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 in

26、sertVertex(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);146-146-3434template Graphlnk:Graphlnk(int sz)/构造函数：建立一个空的邻接表 maxVertices=sz;numVertices=0;numEdges=0;NodeTable=new Ve

27、rtexmaxVertices;/创建顶点表数组 if(NodeTable=NULL)cerr 存储分配错！存储分配错！endl;exit(1);for(int i=0;i maxVertices;i+)NodeTablei.adj=NULL;146-146-3535template 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 Node

28、Table;/删除顶点表数组;146-146-3636template int Graphlnk:getFirstNeighbor(int v)/给出顶点位置为 v 的第一个邻接顶点的位置,/如果找不到,则函数返回-1 if(v!=-1)/顶点顶点v存在存在 Edge*p=NodeTablev.adj;/对应边链表第一个边结点if(p!=NULL)return p-dest;/存在,返回第一个邻接顶点 return-1;/第一个邻接顶点不存在;146-146-3737template 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;/下一邻接顶点不存在;146-146-3838邻接多重表邻接多重表 (Adjacency Multilist(Adjacency Multilist)n在邻接多重表中在邻接多重表中,每一条边只有一个边结点。每一条边只有一个边结点。为有关边的处理提供了方便。为有关边的处理提

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

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

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

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

34、以该顶点为指示以该顶点为始顶点的出边表的第一条边，始顶点的出边表的第一条边，Firstout 指示以指示以该顶点为终顶点的入边表的第一条边。该顶点为终顶点的入边表的第一条边。data Firstin Firstout146-146-4343mark vtx1 vtx2 path1 path2 0 10 31 22 33 44 0e1e2e3e4e5e6data Fin FoutABCDE01234e1e2e3e4e5e6ABCDE邻接多重表的结构邻接多重表的结构146-146-4444图的遍历与连通性图的遍历与连通性n从已给的连通图中某一顶点出发，沿着一些边从已给的连通图中某一顶点出发，沿着一

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

36、为的初始状态为 0,在图的遍在图的遍历过程中历过程中,一旦某一个顶点一旦某一个顶点 i 被访问被访问,就立即就立即让让visitedi为为 1,防止它被多次访问。防止它被多次访问。n图的遍历的分类图的遍历的分类:u深度优先搜索深度优先搜索 DFS(Depth First Search)u广度优先搜索广度优先搜索 BFS(Breadth First Search)146-146-4646深度优先搜索深度优先搜索DFSDFS (Depth First Search)(Depth First Search)n深度优先搜索的示例深度优先搜索的示例ACDEGBFIHACDEGBFIH1234567891

37、23456789前进回退深度优先搜索过程深度优先搜索过程 深度优先生成树深度优先生成树146-146-4747nDFS 在访问图中某一在访问图中某一起始顶点起始顶点 v 后后,由由 v 出发出发,访问它的任一访问它的任一邻接顶点邻接顶点 w1;再从再从 w1 出发出发,访问访问与与 w1邻邻 接接但还但还没有访问过的顶点没有访问过的顶点 w2;然后再然后再从从 w2 出发出发,进行类似的访问进行类似的访问,如此进行下去如此进行下去,直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。接着接着,退回一步退回一步,退到前一次刚访问过退到前一次刚访问过的顶点

38、的顶点,看是否还有其它没有被访问的邻接顶看是否还有其它没有被访问的邻接顶点。点。如果有如果有,则访问此顶点则访问此顶点,之后再从此顶点出之后再从此顶点出发发,进行与前述类似的访问进行与前述类似的访问;如果没有如果没有,就再退就再退回一步进行搜索。重复上述过程回一步进行搜索。重复上述过程,直到连通图直到连通图中所有顶点都被访问过为止。中所有顶点都被访问过为止。146-146-4848图的深度优先搜索算法图的深度优先搜索算法template void DFS(Graph&G,const T&v)/从顶点v出发对图G进行深度优先遍历的主过程 int i,loc,n=G.NumberOfVertice

39、s();/顶点个数 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;146-146-4949templatevoid DFS(Graph&G,int v,bool visited)cout G.getValue(v);/访问顶点v visitedv=true;/作访问标记 int w=G.getFirstNeighbor(v);/

40、第一个邻接顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)DFS(G,w,visited);/若w未访问过,递归访问顶点w w=G.getNextNeighbor(v,w);/下一个邻接顶点 ;146-146-5050广度优先搜索广度优先搜索BFSBFS (Breadth First Search)(Breadth First Search)n广度优先搜索的示例广度优先搜索的示例广度优先搜索过程广度优先搜索过程 广度优先生成树广度优先生成树ACDEGBFIHACDEGBFH123456789123456789I146-146-5151nBFS在访问了起始顶点在访问了

41、起始顶点 v 之后之后,由由 v 出发出发,依次依次访问访问 v 的各个未被访问过的邻接顶点的各个未被访问过的邻接顶点 w1,w2,wt,然后再顺序访问然后再顺序访问 w1,w2,wt 的所的所有还未被访问过的邻接顶点。再从这些访问有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，问过的邻接顶点，如此做下去，直到图中如此做下去，直到图中所有顶点都被访问到为止。所有顶点都被访问到为止。n广度优先搜索是一种分层的搜索过程广度优先搜索是一种分层的搜索过程,每向前每向前走一步可能访问一批顶点走一步可能访问一批顶点,不像深度

42、优先搜索不像深度优先搜索那样有往回退的情况。因此那样有往回退的情况。因此,广度优先搜索不广度优先搜索不是一个递归的过程。是一个递归的过程。146-146-5252n为了实现逐层访问为了实现逐层访问,算法中使用了一个队列算法中使用了一个队列,以以记忆正在访问的这一层和上一层的顶点记忆正在访问的这一层和上一层的顶点,以便以便于向下一层访问。于向下一层访问。n为避免重复访问为避免重复访问,需要一个辅助数组需要一个辅助数组 visited ，给被访问过的顶点加标记。给被访问过的顶点加标记。template void BFS(Graph&G,const T&v)int i,w,n=G.NumberOfV

43、ertices();/图中顶点个数图的广度优先搜索算法图的广度优先搜索算法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);/第一个邻接

44、顶点 while(w!=-1)/若邻接顶点w存在 if(!visitedw)/若未访问过146-146-5454 cout G.getValue(w);/访问 visitedw=true;Q.EnQueue(w);/顶点w进队列 w=G.getNextNeighbor(loc,w);/找顶点loc的下一个邻接顶点 /外层循环，判队列空否 delete visited;146-146-5555连通分量连通分量 (Connected component)(Connected component)n当无向图为非连通图时，从图中某一顶点出当无向图为非连通图时，从图中某一顶点出发，利用深度优先搜索算法或

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

46、EIBFOGJNML非连通图的连通分量146-146-5757确定连通分量的算法确定连通分量的算法template void Components(Graph&G)/通过DFS，找出无向图的所有连通分量 int i,n=G.NumberOfVertices();/图中顶点个数 bool*visited=new booln;/访问标记数组 for(i=0;i n;i+)visitedi=false;for(i=0;i n;i+)/扫描所有顶点 if(!visitedi)/若没有访问过 DFS(G,i,visited);/访问 OutputNewComponent();/输出连通分量 146-14

47、6-5858 delete visited;n例：以深度优先搜索方法从顶点例：以深度优先搜索方法从顶点 出发遍历出发遍历图图,建立深度优先生成森林。建立深度优先生成森林。AABCDEFGABDECFG146-146-5959template void DFS_Forest(Graph&G,Tree&F)TreeNode *rt,*subT;int n=G.NumberOfVertices();static int*visited=new intn;/访问数组 for(int i=0;i n;i+)visited i=0;for(i=0;i n;i+)/遍历所有顶点 if(!visitedi)/

48、顶点 i 未访问过 if(F.IsEmpty()/F原为空生成森林,建根 subT=rt=F.BuildRoot(G.GetValue(i);/顶点 i 的值成为根 rt 的值 146-146-6060 else subT=F.InsertRightSibling (subT,G.GetValue(i);/顶点 i 的值成为 subT 右兄弟的值 DFS_Tree(G,F,subT,i,visited);/从顶点 i 出发深度优先遍历,建子树 template void DFS_Tree(Graph&G,Tree&F,TreeNode*rt,int v,int visited)TreeNode

49、*p;146-146-6161 visitedv=1;/顶点 作访问过标志 int w=G.GetFirstNeighbor(v);/取顶点v的第一个邻接顶点 int FirstChild=1;/第一个未访问子女应是 的左子女 while(w!=-1)/邻接顶点 存在 if(!visited w)/未访问过,将成为 的子女 if(FirstChild)p=F.InsertLeftChild(rt,G.GetValue(w);/插入为 的左子女146-146-6262 FirstChild=0;/建右兄弟 else p=F.InsertRightSibling (p,G.GetValue(w);

50、/p插入为 p 的左子女 DFS_Tree(G,F,p,w,visited);/递归建立 w 的以 p 为根的子树 /邻接顶点 w 处理完 w=G.GetNextNeighbor(v,w);/取 v 的下一个邻接顶点 w /回到 while 判邻接顶点 w 存在;146-146-6363重连通分量重连通分量 (Biconnected(Biconnected Component)Component)n在无向连通图在无向连通图G中中,当且仅当删去当且仅当删去G中的顶点中的顶点v及所有依附于及所有依附于v的所有边后的所有边后,可将图分割成两个可将图分割成两个或两个以上的连通分量，则称顶点或两个以上的