题目:
[实验目的]
验证图的深度优先遍历与广度优先遍历算法。
[实验内容及要求]
1.输入一个有向图的顶点数n和边数e,设图中顶点编号为1到n,
1) 依次输入每个边的起点和终点,创建该图的邻接表;
2) 边链表中边结点编号按照从小到大的顺序存储。
2.实现图的深度优先遍历和广度优先遍历,输入顶点序号V,给出1中有向图
自v开始的深度优先遍历序列和广度优先遍历序列。
3.为了增强程序的可读性,程序中要有适当的注释。
函数部分:
typedef struct graph_link{ int code; graph_link *next; }gl,*pgl; vector<pgl> create_Adjacent(int point){ vector<pgl>adjacent; for(int i=0;i<point;i++) { pgl p=(pgl)malloc(sizeof(gl)); p->code=i+1; p->next=NULL; adjacent.push_back(p); } string start,end; while(1){ cout<<"please input start(if you want to stop,input *):"; cin>>start; if(start[0]=='*') break; cout<<"please input end:"; cin>>end; for(int i=0;i<point;i++) if(adjacent[i]->code==str2int(start)){ pgl node=(pgl)malloc(sizeof(gl)); node->next=NULL; node->code=str2int(end); pgl p=adjacent[i]; while(p->next!=NULL) p=p->next; p->next=node; } } return adjacent; } void output_adjacent(vector<pgl>adjacent){ for(int i=0;i<adjacent.size();i++) { pgl end=adjacent[i]; while(end->next!=NULL){ cout<<end->code<<" -> "; end=end->next; } cout<<end->code<<endl; } } void DFS(vector<pgl>adjacent,int point){ stack<pgl>link; pgl p; int *visit=new int[point]; for(int i=0;i<point;i++) visit[i]=0; int start; cout<<"please input the point DFS start:"; cin>>start; for(int i=0;i<point;i++) if(adjacent[i]->code==start) p=adjacent[i]; link.push(p); while(!link.empty()){ pgl node=link.top(); link.pop(); if(!visit[node->code-1]) { cout<<node->code<<" -> "; visit[node->code-1]=1; for(int i=0;i<point;i++) if(adjacent[i]->code==node->code) node=adjacent[i]; node=node->next; while(node!=NULL){ link.push(node); node=node->next; } } } cout<<"end"<<endl; } void BFS(vector<pgl>adjacent,int point){ queue<pgl>link; pgl p; int *visit=new int[point]; for(int i=0;i<point;i++) visit[i]=0; int start; cout<<"please input the point BFS start:"; cin>>start; for(int i=0;i<point;i++) if(adjacent[i]->code==start) p=adjacent[i]; link.push(p); while(!link.empty()){ pgl node=link.front(); link.pop(); if(!visit[node->code-1]) { cout<<node->code<<" -> "; visit[node->code-1]=1; for(int i=0;i<point;i++) if(adjacent[i]->code==node->code) node=adjacent[i]; node=node->next; while(node!=NULL){ link.push(node); node=node->next; } } } cout<<"end"<<endl; }
调用部分:
int point; cout<<"please input how many points:"; cin>>point; vector<pgl>adjacent=create_Adjacent(point); output_adjacent(adjacent); DFS(adjacent,point); BFS(adjacent,point);
您这个算法好像没法创建1->2 ,1->3,1->4这样的放射状图(或许只是我太菜了不会用
(手动删评 我太菜了