chap08 v3数据结构-图.pdf

第8章 图第8章 图8.1 图的基本概念8.1 图的基本概念8.2 图的存储结构8.2 图的存储结构8.3 图的遍历8.3 图的遍历8.4 最小生成树8.4 最小生成树8.5 一点到其他点最短路径问题8.5 一点到其他点最短路径问题8.6 拓扑排序8.6 拓扑排序8.1图的基本概念8.1图的基本概念?图定义图定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph(Graph(V V,E E)其中其中V V=x x|x x 某个数据对象 某个数据对象是顶点的有穷非空集合；是顶点的有穷非空集合；E E=(=(x x,y y)|)|x x,y y V V 或或E E=y|x x,y y V V&PathPath(x x,y y)?有向图与无向图有向图与无向图 是有序的。边就称为 是有序的。边就称为弧弧，x为，x为弧尾弧尾，y为，y为弧头弧头。(x,y)是无序的。(x,y)是无序的。?完全图完全图0000111122226543300001111222265433?邻接顶点邻接顶点?子图子图 设有两个图 G(V,E)和 G设有两个图 G(V,E)和 G(V(V,E,E)。若V)。若V V 且 E V 且 EE,则称 图GE,则称 图G 是 图G 的子图。是 图G 的子图。01230123子图子图01301301230123023023?权权?带权图带权图也叫做也叫做网络网络。?稠密图和稀疏图稠密图和稀疏图enlognenlogn863129542031863129542031?顶点的度顶点的度?入度入度?出度出度?路径路径?路径长度路径长度?简单路径简单路径 若路径上各顶点若路径上各顶点v v1 1,v v2 2,.,.,v vmm均不互相重复,则称这样的路径为简单路径。均不互相重复,则称这样的路径为简单路径。?回路回路若路径上第一个顶点若路径上第一个顶点v v1 1 与最后一个顶点与最后一个顶点v vmm重合,则称这样的路径为回路或环。重合,则称这样的路径为回路或环。012301230123012301230123?连通图与连通分量连通图与连通分量?强连通图与强连通分量强连通图与强连通分量?生成树生成树 一个连通图的生成树是其极小连通子图.一个连通图的生成树是其极小连通子图.操作的归纳操作的归纳图的抽象数据类型图的抽象数据类型class Graph/对象:由一个顶点的非空集合和一个边集合构成/每条边由一个顶点对来表示。public:Graph();/建立一个空的图void insertVertex(const T&vertex);/插入一个顶点vertex,该顶点暂时没有入边void insertEdge(int v1,int v2,int weight);/在图中插入一条边(v1,v2,w)void removeVertex(int v);/在图中删除顶点v和所有关联到它的边void removeEdge(int v1,int v2);/在图中删去边(v1,v2)bool IsEmpty();/若图中没有顶点,则返回true,否则返回falseT getWeight(int v1,int v2);/函数返回边(v1,v2)的权值int getFirstNeighbor(int v);/给出顶点 v 第一个邻接顶点的位置int getNextNeighbor(int v,int w);/给出顶点 v 的某邻接顶点 w 的下一个邻接顶点;图的模板基类图的模板基类const int maxWeight=;/无穷大的值(=)const int DefaultVertices=30;/最大顶点数(=n)template class Graph/图的类定义protected:int maxVertices;/图中最大顶点数int numEdges;/当前边数int numVertices;/当前顶点数int getVertexPos(T vertex);/给出顶点vertex在图中位置public: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 的第一个邻接顶点virtual int getNextNeighbor(int v,int w);/取邻接顶点 w 的下一邻接顶点virtual bool insertVertex(const T vertex);/插入一个顶点vertexvirtual bool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权为costvirtual bool removeVertex(int v);/删去顶点 v 和所有与相关联边virtual bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);8.2 图的存储表示8.2 图的存储表示一、邻接矩阵（相邻矩阵）一、邻接矩阵（相邻矩阵）?图(图(n n 个顶点)的邻接矩阵是一个个顶点)的邻接矩阵是一个二维数组二维数组edgeedgen n n n，?定义：定义：=,),(,.否则或者如果否则或者如果0=jiji,ji,jiji,ji,jijiji若或且若或且若若或且若或且若,)(,)(),(0EEEEWA.edge863129542031863129542031=068053290410A.edge邻接矩阵存储图的类定义邻接矩阵存储图的类定义template class Graphmtx:public Graph friend istream&operator (istream&in,Graphmtx&G);/输入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 getWeight(int v1,int v2)/取边(v1,v2)上权值return v1!=-1&v2!=-1?Edgev1v2:0;int getFirstNeighbor(int v);/取顶点 v 的第一个邻接顶点int getNextNeighbor(int v,int w);/取 v 的邻接顶点 w 的下一邻接顶点bool insertVertex(const T vertex);/插入顶点vertexbool insertEdge(int v1,int v2,E cost);/插入边(v1,v2),权值为costbool removeVertex(int v);/删去顶点 v 和所有与它相关联的边bool removeEdge(int v1,int v2);/在图中删去边(v1,v2);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;/邻接矩阵for(i=0;i maxVertices;i+)/矩阵初始化for(j=0;j maxVertices;j+)Edgeij=(i=j)？0:maxWeight;template int Graphmtx:getFirstNeighbor(int v)/给出顶点位置为v的第一个邻接顶点的位置,/如果找不到,则函数返回-1if(v!=-1)for(int col=0;col numVertices;col+)if(Edgevcol&Edgevcol maxWeight)return col;return-1;template 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;二、邻接表二、邻接表?1.无向图的邻接表1.无向图的邻接表 将与同一顶点相邻接的顶点链接成一个单链表.同一顶点相邻接的顶点链接成一个单链表.ABCDABCDdata adjdata adjABCDABCDdest linkdest linkdest linkdest link1302101302100 01 12 23 3?2.有向图的邻接表和逆邻接表2.有向图的邻接表和逆邻接表data adjdata adjABCABC012012dest linkdest link 邻接表(出边表)邻接表(出边表)data adjdata adjABCABC012012dest linkdest link102102011011A AB BC C逆邻接表(入边表)逆邻接表(入边表)?3.网络(带权图)的邻接表3.网络(带权图)的邻接表ABCDABCD 1 1 5 53 3 6 62 2 8 83 3 2 21 1 9 9B B B BA A A AC C C CD D D D9 96 6data adjdata adjdest cost linkdest cost link52520 01 12 23 38 8(顶点表顶点表顶点表顶点表)(出边表出边表出边表出边表)?邻接表的特征：邻接表的特征：?在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。?求某个顶点的度（入度或出度）比较方便；求某个顶点的度（入度或出度）比较方便；?设图中有设图中有n n 个顶点，个顶点，e e 条边，则用邻接表表示无向图时，需要条边，则用邻接表表示无向图时，需要n n 个顶点结点，2个顶点结点，2e e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n n 个顶点结点，个顶点结点，e e 个边结点。个边结点。邻接表存储图的类定义邻接表存储图的类定义链表的结点结构类链表的结点结构类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;/判边等否;顺序表结点结构类顺序表结点结构类template 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);/输出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(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);void CreateNodeTable(void);/建立邻接表结构建立邻接表结构;template 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;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 NodeTable;/删除顶点表数组;template int Graphlnk:getFirstNeighbor(int v)/给出顶点位置为 v 的第一个邻接顶点的位置,/如果找不到,则函数返回-1if(v!=-1)/顶点顶点v存在存在Edge*p=NodeTablev.adj;/对应边链表第一个边结点if(p!=NULL)return p-dest;/存在,返回第一个邻接顶点return-1;/第一个邻接顶点不存在;template int Graphlnk:getNextNeighbor(int v,int w)/给出顶点v的邻接顶点w的下一个邻接顶点的位置,/若没有下一个邻接顶点,则函数返回-1if(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;/下一邻接顶点不存在;邻接表建立方法邻接表建立方法邻接表建立算法邻接表建立算法?邻接表结构的分拆邻接表结构的分拆?输入的组织输入的组织ABCDABCDdata adjdata adjABCDABCDdest linkdest linkdest linkdest link1302101302100 01 12 23 3邻接表存储结构的实现算法邻接表存储结构的实现算法在输入数据前,顶点表NodeTable 全部初始化,即将第i个结点的数据存入NodeTablei.data中;在输入数据前,顶点表NodeTable 全部初始化,即将第i个结点的数据存入NodeTablei.data中;接着,把所有第i个结点的邻接点链接成一个单链表,方法是:在输入数据时,每输入一条边接着,把所有第i个结点的邻接点链接成一个单链表,方法是:在输入数据时,每输入一条边,就需要建立一个边结点,并将它链入相应边链表中。就需要建立一个边结点,并将它链入相应边链表中。Edge*p=new Edge;p-dest=k;/建立边结点,dest域赋为 kp-cost=?p-link=NodeTablei.adj;NodeTablei.adj=p;/头插入建链邻接表的建立算法邻接表的建立算法template void Graphlnk:CreateNodeTable(void);/建立邻接表结构建立邻接表结构 i intnt n,i,j,m;n,i,j,m;Edge*p;cinn;/结点个数cinn;/结点个数for(i=1;i=n;i+)for(i=1;iNodeTablei.data;/输入结点值cinNodeTablei.data;/输入结点值cinm;/每个结点的邻接点个数cinm;/每个结点的邻接点个数for(j=0;jm;j+)for(j=0;jm;j+)p=new p=new Edge;cinp-dest;/建立边结点,输入结点值到dest域cinp-dest;/建立边结点,输入结点值到dest域/带权图则多加一个权值的输入/带权图则多加一个权值的输入 cinp-cost;cinp-cost;p-link=NodeTablei.adj;p-link=NodeTablei.adj;NodeTablei.adj=p;/头插入建链NodeTablei.adj=p;/头插入建链 8.3 图的遍历8.3 图的遍历?定义定义?图的遍历方法:图的遍历方法:?深度优先 DFS深度优先 DFS?广度优先 BFS广度优先 BFS二叉树前序遍历算法的回顾二叉树前序遍历算法的回顾存储结构存储结构struct treenodestruct treenode int data;int data;struct treenode*child2;struct treenode*child2;前序遍历算法前序遍历算法void DFS(struct tvoid DFS(struct treenodereenode*root)*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;for(i=0;i2;i+)for(i=0;ichildi);DFS(root-childi);/DFS(root-child0);/DFS(root-child0);/DFS(root-child1);/DFS(root-child1);深度优先遍历算法void DFS(struct node*root)void DFS(struct node*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;i=0;i=0;while(i2)while(ichildi);DFS(root-childi);i+;i+;/DFS(root-child0);/DFS(root-child0);/DFS(root-child1);/DFS(root-child1);在邻接表存储结构下的实现算法:在邻接表存储结构下的实现算法:void DFS(int v)void DFS(int v)coutNodeTablev.data;/访问v结点coutdest);DFS(p-dest);p=p-link;p=p-link;/DFS/DFS层次遍历算法层次遍历算法层次遍历算法层次遍历算法void BFS(struct treenode*root)void BFS(struct treenode*root)queue qu;queue qu;struct treenode*temp;struct treenode*temp;qu.push(root);qu.push(root);while(!qu.empty()while(!qu.empty()temp=qu.front();temp=qu.front();qu.pop();qu.pop();coutdata ;coutdatachiif(temp-child0!=0)ld0!=0)qu.push(temp-child0);qu.push(temp-child0);if(temp-chiif(temp-child1!=0)ld1!=0)qu.push(temp-child1);qu.push(temp-child1);/可以改写为 for 循环/可以改写为 for 循环 层次遍历算法层次遍历算法voivoid d B BFS(struct treenode*root)FS(struct treenode*root)queue qu;queue qu;struct treenode*temp;struct treenode*temp;qu.push(root);qu.push(root);while(!qu.empty()while(!qu.empty()temp=qu.front();temp=qu.front();qu.pop();qu.pop();coutdata ;coutdata ;for(i=0;i2;i+)for(i=0;ichildi!=0)if(temp-childi!=0)qu.push(temp-childiqu.push(temp-childi););广度优先遍历算法void BFS(struct node*root)void BFS(struct node*root)queue qu;queue qu;struct node*temp;struct node*temp;qu.push(root);qu.push(root);while(!qu.empty()while(!qu.empty()temp=qu.front();temp=qu.front();qu.pop();qu.pop();coutdata ;coutdata ;i=0;i=0;while(i2)while(ichildi!=0)if(temp-childi!=0)qu.push(temp-child i );qu.push(temp-child i );i+;i+;在邻接表存储结构下的实现算法:void BFS()int v;queue qu;/定义一个队列quv=0;/在邻接表存储结构下的实现算法:void BFS()int v;queue qu;/定义一个队列quv=0;/根结点的下标为0根结点的下标为0qu.push(v);/v入列while(!qu.empty()v=qu.front();qu.pop();/出列coutdest);p=p-link;/while/if/while/BFSqu.push(v);/v入列while(!qu.empty()v=qu.front();qu.pop();/出列coutdest);p=p-link;/while/if/while/BFS四叉特征树四叉特征树存储结构存储结构struct treenodestruct treenode int data;int data;struct treenode*child4;struct treenode*child4;前序遍历算法前序遍历算法void DFS(struct tvoid DFS(struct treenodereenode*root)*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;for(i=0;i4;i+)for(i=0;ichildi);/DFS(root-childi);/深度优先遍历算法深度优先遍历算法void DFS(struct node*root)void DFS(struct node*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;i=0;i=0;while(i4)while(ichild i );DFS(root-child i );i+;i+;层次遍历算法层次遍历算法void BFS(struct treenode*root)void BFS(struct treenode*root)int i;int i;queue qu;queue qu;struct treenode*temp;struct treenode*temp;qu.push(root);qu.push(root);while(!qu.empty()while(!qu.empty()temp=qu.front();temp=qu.front();qu.pop();qu.pop();coutdata ;coutdata ;for(i=0;i4;i+)for(i=0;ichildi!=0)if(temp-childi!=0)qu.push(temp-childi);qu.push(temp-childi);广度优先遍历算法广度优先遍历算法void BFS(struct node*root)void BFS(struct node*root)queue qu;queue qu;struct node*temp;struct node*temp;qu.push(root);qu.push(root);while(!qu.empty()while(!qu.empty()temp=qu.front();temp=qu.front();qu.pop();qu.pop();coutdata ;coutdata ;i=0;i=0;while(i4)while(ichildi!=0)if(temp-childi!=0)qu.push(temp-child i );qu.push(temp-child i );i+;i+;八叉特征树存储结构八叉特征树存储结构struct treenodeint data;struct treenode*child8;struct treenodeint data;struct treenode*child8;八叉特征树的遍历方法八叉特征树的遍历方法 前序遍历方法前序遍历方法 层次遍历方法层次遍历方法图的遍历图的遍历 深度优先深度优先 广度优先广度优先?深度优先 DFS深度优先 DFS?在访问图中某一在访问图中某一起始顶点起始顶点v v后,由后,由v v出发,访问它的任一出发,访问它的任一邻接顶点邻接顶点ww1 1;再从;再从ww1 1 出发,访问出发,访问与与ww1 1邻 接邻 接但还但还没有访问过的顶点没有访问过的顶点ww2 2;然后再从;然后再从ww2 2 出发,出发,进行类似的访问进行类似的访问,如此进行下去,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点u u 为止为止。?接着,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。?重复上述过程,直到连通图中所有顶点都被访问过为止。重复上述过程,直到连通图中所有顶点都被访问过为止。深度优先遍历的示例深度优先遍历的示例ACDEACDEGBFIGBFIH H深度优先遍历过程深度优先遍历过程?广度优先 BFS广度优先 BFS?在访问了在访问了起始顶点起始顶点v v之后,由之后,由v v 出发,依次访问出发,依次访问v v 的各个未被访问过的的各个未被访问过的邻接顶点邻接顶点ww1 1,ww2 2,wwt t,然后再顺序访问然后再顺序访问ww1 1,ww2 2,wwt t 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，如此做下去，直到图中所有顶点都被访问到为止。如此做下去，直到图中所有顶点都被访问到为止。?广度优先遍历是一种广度优先遍历是一种分层分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先遍历那样有往回退的情况。的搜索过程,每向前走一步可能访问一批顶点,不像深度优先遍历那样有往回退的情况。?因此,广度优先遍历不是一个递归的过程。因此,广度优先遍历不是一个递归的过程。?广度优先遍历的示例广度优先遍历的示例ACDEACDEGBFIGBFIH H广度优先遍历过程广度优先遍历过程图遍历的问题分析0123图的遍历方法的问题发现图的遍历方法的问题发现1.各结点的叉数不统一1.各结点的叉数不统一存储结构的问题存储结构的问题structtreenodestructtreenode int data;int data;struct treenode*child8;struct treenode*child8;/问题所在/问题所在;找孩子找孩子?改变为找邻接点?改变为找邻接点如何找结点i的邻接点如何找结点i的邻接点 存储结构存储结构邻接矩阵存储结构邻接矩阵存储结构0123=0101101001011010A.edge找出结点i的所有邻接点找出结点i的所有邻接点for(int col=0;col numVertices;col+)if(Edgeicol=1）带权图带权图863129542031863129542031=068053290410A.edge找出结点i的所有邻接点找出结点i的所有邻接点for(int col=0;col numVertices;col+)if(Edgeicol）&Edgeicolmaxweihgt)邻接表结构邻接表结构ABCDdata adjABCDdata adjABCDABCD01230123dest linkdest linkdest linkdest link130210130210找出结点i的所有邻接点找出结点i的所有邻接点Edge*p=NodeTablei.adj;while(p!=NULL)p=p-link;图的遍历方法的问题发现图的遍历方法的问题发现012301232.如何解决重复访问?2.如何解决重复访问?图遍历的问题分析图遍历的问题分析?如何解决重复访问?如何解决重复访问?可设置一个标志顶点是否被访问过的辅助数组可设置一个标志顶点是否被访问过的辅助数组 visited visited。?深度优先 DFS深度优先 DFS?在访问图中某一在访问图中某一起始顶点起始顶点v v后,由后,由v v出发,访问它的任一出发,访问它的任一邻接顶点邻接顶点ww1 1;再从;再从ww1 1 出发,访问出发,访问与与ww1 1邻 接邻 接但还但还没有访问过的顶点没有访问过的顶点ww2 2;然后再从;然后再从ww2 2 出发,出发,进行类似的访问进行类似的访问,如此进行下去,如此进行下去,直至到达所有的邻接顶点都被访问过的顶点直至到达所有的邻接顶点都被访问过的顶点u u 为止为止。?接着,接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。?重复上述过程,直到连通图中所有顶点都被访问过为止。重复上述过程,直到连通图中所有顶点都被访问过为止。深度优先遍历的示例深度优先遍历的示例ACDEACDEGBFIGBFIH H深度优先遍历过程深度优先遍历过程二叉树前序遍历算法的回顾二叉树前序遍历算法的回顾二叉树前序遍历算法二叉树前序遍历算法void DFS(struct treenode*root)void DFS(struct treenode*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;for(i=0;i2;i+)/for(i=0;ichildi);DFS(root-childi);/DFS(root-child0);/DFS(root-child0);/DFS(root-child1);/DFS(root-child1);图的深度优先遍历抽象算法:图的深度优先遍历抽象算法:voidvoid DFS(Graph G,intint v)/从顶点v出发，深度优先遍历遍历连通图 G /从顶点v出发，深度优先遍历遍历连通图 Gvisitedv=TRUETRUE;访问v结点;forfor(w=FirstAdjVex(G,v);w!=!=0;w=NextAdjVex(G,v,w)if if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS /DFS图的深度优先遍历算法图的深度优先遍历算法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;templatevoid DFS(Graph&G,int v,bool visited)cout G.getValue(v)numVerticesnumVertices;/加入到加入到Graphlnk构造函数中构造函数中void void Graphlnk:dfs()dfs()int i,v0;for(i=0;iv0;/输入深度优先遍历的出发点dfs(v0);/调用深度优先的递归函数 int i,v0;for(i=0;iv0;/输入深度优先遍历的出发点dfs(v0);/调用深度优先的递归函数在邻接表存储结构下的实现算法:在邻接表存储结构下的实现算法:void void Graphlnk:DFS(int v)/DFS(int v)/私有函数私有函数 /从顶点v出发，深度优先遍历遍历连通图 G /从顶点v出发，深度优先遍历遍历连通图 Gvisitedv=true;visitedv=true;coutNodeTablev.data;/访问v结点coutdest)DFS(p-dest);if(!visitedp-dest)DFS(p-dest);p=p-link;p=p-link;/DFS/DFS四叉树的深度优先遍历算法四叉树的深度优先遍历算法void DFS(struct node*root)void DFS(struct node*root)int i;int i;if(root!=0)if(root!=0)coutdata ;coutdata ;i=0;i=0;while(i4)while(ichild i );DFS(root-child i );i+;i+;程序的组织程序的组织void main()void main()邻接表的建立；邻接表的建立；调用深度优先遍历调用深度优先遍历公有成员公有成员函数函数 邻接矩阵存储的深度优先遍历邻接矩阵存储的深度优先遍历 int gmaxmmaxm;int gmaxmmaxm;邻接矩阵的输入邻接矩阵的输入 调用深度优先算法调用深度优先算法?广度优先 BFS广度优先 BFS?在访问了在访问了起始顶点起始顶点v v之后,由之后,由v v 出发,依次访问出发,依