图深度优先搜索C++.docx

#includeusing namespace std;#define NULL 0#define MaxSize 20struct edgenode/边表结点int adjvex;edgenode *next;struct vexnode/顶点表结点int vertex;edgenode *link;class ALGraph/邻接表类public:void CreatGraph();/创建临界表void D_Search(int i, int j);/深度优先搜索判断void B_Search(int i, int j);/广度优先搜索判断private:vexnode gaMaxSize;/顶点数组int n,e;/顶点数，边数;void ALGraph:CreatGraph()edgenode *s;int i,start,end;cout请输入顶点数和边数:ne;while( e(n-1) )cout错误!该图不是连通图!请重新输入:ne;cout请输入顶点编号:endl;/建立顶点数组for(i=0;igai.vertex;gai.link=NULL;cout请依次输入各边相连的结点endl;/建立边表for(i=0;istartend;while( ( startn ) | ( endn ) )cout输入有误，请重新输入startend;s=new edgenode;s-adjvex=end;s-next=gastart-1.link;gastart-1.link=s;/按深度优先搜索，判断vi和vj之间是否存在路径void ALGraph:D_Search(int start ,int end)cout-endl;cout按深度优先搜索adjvex-1;while(p!=NULL)if(!visitedp-adjvex)visitedp-adjvex=1;top+;nodetop=p-adjvex;stepflag=p-adjvex;flag+;p=gap-adjvex-1.link;else p=p-next;if(p=NULL&top!=0)p=ganode-top-1.link;if(p=NULL) break;if(p-adjvex=end) mm=1;break;if(mm=1)cout点start和点end之间有路径.endl;cout路径为:start;for(i=1;iflag;i+)coutstepi;coutendendlendl;elsecoutstart和end之间没有路径.endl;/按广度优先搜索，判断vi和vj之间是否存在路径void ALGraph:B_Search(int start ,int end)cout-endl;cout按广度优先搜索adjvex-1;while(p!=NULL)if(!visitedp-adjvex)visitedp-adjvex=1;top+;nodetop=p-adjvex;stepflag=p-adjvex;flag+;p=p-next;else p=p-next;if(p=NULL&top!=0)p=ganode-top-1.link;if(p=NULL) break;if(p-adjvex=end) mm=1;break;if(mm=1)cout点start和点end之间有路径.endl;cout路径不会找endl;elsecoutstart和end之间没有路径.endl;int main()ALGraph xj;int start,end,re_build=-1,re_search=-1,temp;while(re_build!=0)re_build=-1;xj.CreatGraph();while(re_search!=2)re_search=-1;cout请输入要查询的起点和终点:startend;/深度优先搜索xj.D_Search(start,end);/广度优先搜索xj.B_Search(start,end);cout-endl;cout请选择操作方式:endl0.退出endl;cout1.重新搜索endl2.重新建立邻接表