图的搜索与应用实验报告(附源码)

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图的搜索与应用实验题目：图的深度和广度搜索与拓扑排序设计成绩报告成绩指导老师实验目的1.掌握图的邻接表的存储形式。2.熟练掌握图的搜索策略，包括深度优先搜索与广度优先搜索算法。3.掌握有向图的拓扑排序的方法。二、实验要求及实验环境实验要求：以邻接表的形式存储图。给出图的深度优先搜索算法与广度优先搜索算法。应用搜索算法求出有向图的拓扑排序。实验环境：寝室+机房+编程软件（NetBeansIDE6.9.1）。设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）数据类型定义：template<classT>classNode{//定义边public:intadjvex;//定义顶点所对应的序号Node*next;//指向下一顶点的指针intweight;//边的权重};template<classT>classVnode{public:Tvertex;Node<T>*firstedge;};template<classT>classAlgraph{public:Vnode<T>adjlist[Max];intn;inte;intmark[Max];intIndegree[Max];};template<classT>classFunction{public://创建有向图邻接表voidCreatNalgraph(Algraph<T>*G);//创建无向图邻接表voidCreatAlgraph(Algraph<T>*G);//深度优先递归搜索voidDFSM(Algraph<T>*G,inti);voidDFS(Algraph<T>*G);//广度优先搜索voidBFS(Algraph<T>*G);voidBFSM(Algraph<T>*G,inti);//有向图的拓扑排序voidTopsort(Algraph<T>*G);/得到某个顶点内容所对应的数组序号intJudge(Algraph<T>*G,Tname);};主程序流程图：程序开始程序开始选择图的类型选择图的类型无向图有向图无向图有向图深度优先搜深度优先搜索拓扑排序广度优先搜索广度优先搜索深度优先搜索程序结束程序结束调用关系：主函数调用五个函数CreatNalgraph(G)//创建有向图DFS(G)//深度优先搜索BFS(G)//广度优先搜索Topsort(G)//有向图拓扑排序CreatAlgraph(G)//创建无向图其中CreatNalgraph(G)调用Judge(Algraph<T>*G,Tname)函数；DFS(G)调用DFSM(Algraph<T>*G,inti)函数；BFS(G)调用BFSM(Algraph<T>*G,intk)函数；CreatAlgraph(G)调用Judge(Algraph<T>*G,Tname)函数。测试结果系统不足与经验体会1.对错误输入没有处理2.友好性不是很好附录：源代码（带注释）/**File:ADJACENTYLIST.h*Author:Administrator**Createdon2011年12月1日,上午11:26*/#ifndefADJACENTYLIST_H#define ADJACENTYLIST_H#include<iostream>#include<queue>#defineMax100usingnamespacestd;template<classT>classNode{//边结点public:intadjvex;Node*next;intweight;};template<classT>classVnode{//顶点结点public:Tvertex;Node<T>*firstedge;};template<classT>classAlgraph{public:Vnode<T>adjlist[Max];intn;inte;intmark[Max];intIndegree[Max];//顶点入度};template<classT>classFunction{public:voidCreatNalgraph(Algraph<T>*G);//创建有向图voidCreatAlgraph(Algraph<T>*G);//创建无向图voidDFSM(Algraph<T>*G,inti);voidDFS(Algraph<T>*G);//深度优先搜索voidBFS(Algraph<T>*G);//广度优先搜索voidBFSM(Algraph<T>*G,inti);voidTopsort(Algraph<T>*G);//有向图的拓扑排序intJudge(Algraph<T>*G,Tname);//得到顶点序号};template<classT>voidFunction<T>::CreatNalgraph(Algraph<T>*G){//创建有向图inti,j,k;Ta;Tname1,name2;Node<T>*s;cout<<"请输入顶点数和边数："<<endl;cin>>i;cin>>j;G->n=i;G->e=j;for(inti=0;i<G->n;i++){G->Indegree[i]=0;}cout<<"请输入顶点内容："<<endl;for(i=0;i<G->n;i++){cin>>a;G->adjlist[i].vertex=a;G->adjlist[i].firstedge=NULL;}cout<<"请输入两个顶点构成的边，示例：12："<<endl;for(k=0;k<G->e;k++){cin>>name1;i=Judge(G,name1);cin>>name2;j=Judge(G,name2);s=(Node<T>*)malloc(sizeof(Node<T>));G->Indegree[j]++;s->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;}}template<classT>intFunction<T>::Judge(Algraph<T>*G,Tname){//得到顶点序号for(inti=0;i<G->n;i++){if(G->adjlist[i].vertex==name){returni;break;}}}template<classT>voidFunction<T>::CreatAlgraph(Algraph<T>*G){//创建无向图inti,j,k;Ta;Tname1,name2;Node<T>*s;cout<<"请输入顶点数和边数："<<endl;cin>>i;cin>>j;G->n=i;G->e=j;cout<<"请输入顶点内容："<<endl;for(i=0;i<G->n;i++){cin>>a;G->adjlist[i].vertex=a;G->adjlist[i].firstedge=NULL;}cout<<"请输入两个顶点构成的边，示例：12："<<endl;for(k=0;k<G->e;k++){cin>>name1;i=Judge(G,name1);cin>>name2;j=Judge(G,name2);s=(Node<T>*)malloc(sizeof(Node<T>));s->adjvex=j;s->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s;s=(Node<T>*)malloc(sizeof(Node<T>));s->adjvex=i;s->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;}}template<classT>voidFunction<T>::DFSM(Algraph<T>*G,inti){Node<T>*p;cout<<G->adjlist[i].vertex<<"";G->mark[i]=1;p=G->adjlist[i].firstedge;while(p){if(G->mark[p->adjvex]==0)DFSM(G,p->adjvex);p=p->next;}}template<classT>voidFunction<T>::DFS(Algraph<T>*G){//深度优先搜索for(inti=0;i<G->n;i++){G->mark[i]=0;}for(inti=0;i<G->n;i++){if(G->mark[i]==0)DFSM(G,i);}cout<<endl;}template<classT>voidFunction<T>::BFS(Algraph<T>*G){//广度优先搜索for(inti=0;i<G->n;i++){G->mark[i]=0;}for(inti=0;i<G->n;i++){if(G->mark[i]==0)BFSM(G,i);}cout<<endl;}template<classT>voidFunction<T>::BFSM(Algraph<T>*G,intk){intr=0;intj=0;Node<T>*p;intarray[Max];for(inti=0;i<Max;i++){array[i]=-1;}cout<<G->adjlist[k].vertex<<"";G->mark[k]=1;array[r]=k;G->mark[r]=1;while(array[r]!=-1){intu=array[r++];p=G->adjlist[u].firstedge;while(p){if(G->mark[p->adjvex]==0){cout<<G->adjlist[p->adjvex].vertex<<"";G->mark[p->adjvex]=1;array[++j]=p->adjvex;}p=p->next;}}}template<classT>voidFunction<T>::Topsort(Algraph<T>*G){//有向图的拓扑排序for(inti=0;i<G->n;i++)//初始化mark数组G->mark[i]=0;usingstd::queue;//使用STL中的队列queue<int>Q;for(inti=0;i<G->n;i++)//入度为0的顶点入队if(G->Indegree[i]==0)Q.push(i);while(!Q.empty()){//如果队列非空intv=Q.front();//获得队列顶部元素Q.pop();//队列顶部元素出队cout<<G->adjlist[v].vertex<<"";//问顶点vG->mark[v]=1;//将标记位设置为1Node<T>*e=G->adjlist[v].firstedge;while(e){G->Indegree[e->adjvex]--;//与该顶点相邻的顶点入度减1if(G->Indegree[e->adjvex]==0)//如果顶点入度减为0则入队Q.push(e->adjvex);e=e->next;}}for(inti=0;i<G->n;i++)//利用标记位可以判断图中是否有环if(G->mark[i]==0){cout<<"此图有环！";break;}}#endif /*ADJACENTYLIST_H*//**File:main.cpp*Author:Administrator**Creat