图的深度,广度优先遍历

1、#define t true#define f false#include<iostream.h>struct node/定义一个结构作为节点类型 int data; bool sign; /标志位,用来标示是否遍历过 node *next;node* creategraph()/建立邻接表，完成无向图的输入 int l,m,n; bool g; cout<<"请输入节点数: " cin>>n; node *adjacencylist=new noden+1; /动态分配节点数组内存 adjacencylist0.data=n; /0地址

2、存放的为节点数 adjacencylist0.next=NULL; for(int i=1;i<=n;i+) /给各顶点域赋初值 adjacencylisti.data=0; adjacencylisti.next=NULL; adjacencylisti.sign=f;/表示未遍历 cout<<"请依次输入各条边的始点和尾点:（以0表示结束）"<<endl; cin>>l; if(l!=0) /判断输入边是否结束 g=t; while(g=t) cin>>m; if(l>0)&&(l<=n)

3、&&(m>0)&&(m<=n) /判断输入顶点是否正确 node *p,*q,*top; p=(node *)new(node); /分配边的一个顶点内存 p->data=m; p->next=NULL; if(adjacencylistl.next=NULL) /为每个节点创建邻接链表 adjacencylistl.next=p; else top=adjacencylistl.next; while(top->next!=NULL) top=top->next; top->next=p; adjacencylistl

4、.data+; /统计邻接点的个数 q=(node *)new(node); /分配边的另一个顶点内存 q->data=l; q->next=NULL; if(adjacencylistm.next=NULL) /构建邻接表 adjacencylistm.next=q; else top=adjacencylistm.next; while(top->next!=NULL) top=top->next; top->next=q; adjacencylistm.data+; /统计邻接点的个数 else cout<<"边"<&l

5、t;l<<"-"<<m<<"输入错误！"<<endl;/错误输入标识 cin>>l; if(l=0)/边的输入结束 g=f; return adjacencylist; /返回邻接表;void DepthFirstSearch(node *list)/深度优先搜索 int m,n=list0.data,k,*a=new intn;/设置一个数组用于存放节点 node *p; cout<<"采用深度优先搜索："<<endl; cout<<&q

6、uot;请输入搜索起始节点：" cin>>k; for(int i=0;i<n;i+) ai=k; listk.sign=t; if(i=n-1) break; m=0; while(listk.sign=t) p=listk.next; while(p!=NULL) /找出listk链表中的未遍历节点 k=p->data; p=p->next; if(listk.sign=f) break; m+; if(listk.sign!=f) /判断是否是p=NULL跳出while循环的 if(i<m)/无节点可回溯 cout<<"

7、该图为非连通图!"<<endl; break; else k=ai-m; /回溯 for(i=1;i<=n;i+)/恢复原邻接表 listi.sign=f; cout<<"深度优先搜索遍历顺序为:" for(i=0;i<n;i+)/输出遍历结果 cout<<ai<<" " cout<<endl; delete a;/释放动态数组内存;void BreadthFirstSearth(node *list)/广度优先搜索 int m,r,k,n=list0.data,*a=ne

8、w intn+1; /设置数组存放节点 node *p; cout<<"采用广度优先搜索："<<endl; cout<<"请输入搜索起始节点：" cin>>k; a0=n; a1=k; listk.sign=t; /标识遍历的第一个节点 m=0; r=1; while(m!=r) m+; p=listam.next; while(p!=NULL) k=p->data; if(listk.sign=f) r+; ar=k; /遍历到的节点存入数组 listk.sign=t; /标识已经遍历过的节点 p=

9、p->next; for(int i=1;i<=n;i+) /恢复原邻接表 listi.sign=f; cout<<"广度优先搜索遍历顺序为: " for(i=1;i<=n;i+) /输出遍历 cout<<ai<<" " cout<<endl; delete a; /释放动态数组内存;void PathSearth(node *list)/路径搜索 int *a,c,d,m,k,n=list0.data; cout<<"请输入起始点：" cin>>

10、;k; cout<<"请输入尾节点：" cin>>c; cout<<"请输入要找的路径长度：" cin>>d; d=d+1; if(d>n) cout<<"不存在这样的简单路径！"<<endl; else a=new intd; /动态分配数组内存存放路径上的节点 for(int i=0;i<d;i+) ai=0; a0=k; node *p; int x; lista0.sign=t; i=1; while(ad-1!=c) while(i<d

11、) x=1; p=listai-1.next; while(p!=NULL) m=p->data; if(i=d-1&&m=a0&&a0=c) /路径存在且为回路 cout<<"该路径为一条回路！"<<endl; ai=m; i+; break; if(listm.sign=f) if(ai!=0) if(x=0) /是否为已经判断过的错误路径 ai=m; listai.sign=t; /标识走过节点 i+; break; if(ai=m) /设置错误路径标识 x=0; else ai=m; listai.sig

12、n=t; /标识走过节点 i+; break; p=p->next; if(p=NULL) ai=0; i-; /由此节点往下的路径不存在,回溯 listai.sign=f; /还原标识符 if(i=0) /无法回溯,路径不存在,跳出循环 cout<<"不存在这样的简单路径！"<<endl; break; if(i=0) /无法回溯,路径不存在,跳出循环 break; if(ad-1!=c) /路径不是所要找的 i-; /回溯 if(i>=0) listai.sign=f; /还原标识符 if(ad-1=c) /判断路径是否找到并输出 c

13、out<<"从节点"<<k<<"到节点"<<c<<"的一条路径为：" for(i=0;i<d-1;i+) /输出路径 cout<<ai<<"-> " cout<<ad-1<<endl; delete a; for(int i=1;i<=n;i+) /恢复原邻接表 listi.sign=f; ;void AdjacencyListDelete(node *list)/释放邻接表的空间 node

14、 *p,*q; int n=list0.data; for(int i=1;i<=n;i+) p=listi.next; while(p!=NULL) q=p->next; delete p; /释放链表节点空间 p=q; delete list; /释放邻接表空间;void main() node *list; list=creategraph();/以邻接表的形式建立一个无向图 char a,b; cout<<"请选择遍历方法：（d:深度优先搜索;b:广度优先搜索）" for(int i=1;i<2;i+) cin>>a; sw

15、itch(a) case 'd': case 'D': DepthFirstSearch(list); cout<<"是否采用广度优先搜索重新遍历？（y:是;n:否）" cin>>b; if(b='y')|(b='Y') BreadthFirstSearth(list); break; case 'b': case 'B': BreadthFirstSearth(list); cout<<"是否采用深度优先搜索重新遍历？（y:是;n:否）" cin>>b; if(b='y')|(b='Y') DepthFirstSearch(list); break; default: cout<<"输入错误！请重新输入！"<<endl; i-; w