问题描述：
设计并实现一个算法，应用递归的程序设计方法，对一个已存在的图进行广度优先遍历（BFS)，并输出遍历的顶点线性序列。遍历的起点通过输入指定。
注意：遍历时，仅从该点出发遍历整个图，如果图不连通，则只遍历一个子图。图的存储结构采用邻接表。将其加入到ADT中。
参考函数原型：
//BFS遍历
template
void adjlist_graph::BFS_Traverse(int u);

【DHU-----OJ|图的邻接表（广度优先遍历&&深度优先遍历）】输入说明 :
建图的输入数据格式参见建图的算法说明。（以无权图为例）
第一行：图的类型
第二行：结点数
第三行：结点集
第四行：边数
第五行：边集
第六行：起始顶点的位序

输出说明 :
第一行：顶点集
第二行：邻接表
空行
第三行：BFS遍历序列（结点之间用->分隔）

输入范例 :
UDG
8
V1 V2 V3 V4 V5 V6 V7 V8
8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5

输出范例 :
V1 V2 V3 V4 V5 V6 V7 V8
V1->2->1->nullptr
V2->4->3->0->nullptr
V3->6->5->0->nullptr
V4->7->1->nullptr
V5->7->1->nullptr
V6->2->nullptr
V7->2->nullptr
V8->4->3->nullptr
(空行)
V6->V3->V7->V1->V2->V5->V4->V8

#include #include #include #include #include #include #include using namespace std; string b[10001]; //用来存放顶点集 queue q; //这个队列用于广度优先搜索存放顶点 bool visited[1001]={false}; //一开始设为都没有被访问过 vector po(10001); //DG（有向图）DN（有向网）UDG（无向图） UDN（无向网）//图的邻接表模板类原型参考如下： //边表的顶点定义 template//这个就是在边上的顶点定义 struct edgeNode{ int data; TypeOfEdge weight; edgeNode *next; //构造函数，用于构造其他顶点（无权图） //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面 edgeNode(int d,edgeNode *ptr=NULL){ data=https://www.it610.com/article/d; next=ptr; } //构造函数，用于构造其他顶点（带权图） //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面 edgeNode(int d,TypeOfEdge w,edgeNode *ptr=NULL){ data=https://www.it610.com/article/d; weight=w; next=ptr; } int getData(){ return data; }//取得顶点的序号（顶点集） TypeOfEdge getWeight(){ return weight; }//取得边集中对应边的权值 void SetLink(edgeNode *link ){ next=link; }//修改顶点的next域 void SetData(int value){ data=https://www.it610.com/article/value; }//修改顶点的序号（顶点集） void SetWeight(TypeOfEdge value){ weight=value; }//修改边集中对应边的权值 }; //图的邻接表类这个结构体是存储顶点的结构体，里面包括顶点和它的下一个指针 template struct verNode{ TypeOfVer ver; //存放顶点名称 edgeNode *head; //顶点的指针 verNode(edgeNode *h=NULL){ head=h; } TypeOfVer getVer(){ return ver; }//取得顶点值（顶点集） edgeNode *getHead(){ return head; }//取得对应的边表的头指针 void setVer(TypeOfVer value){ ver=value; }//设置顶点值（顶点集） void setHead(edgeNode *value){ head=value; }//设置对应的边表的头指针 }; template//顶点类型边的类型 class adjlist_graph{ private: int Vers; //顶点数 int Edges; //边数 string GraphKind; //图的种类标志 verNode *verList; //按顺序存储结构存储顶点集 bool Delete_Edge(int u,int v); bool DFS(int u,int num,int visited[]); //DFS遍历（递归部分） public: //构造函数构造一个只有顶点没有边的图 //3个参数的含义：图的类型、顶点数、顶点值 adjlist_graph(string kd,int vSize,TypeOfVer d[]){ GraphKind=kd; Vers=vSize; verList=new verNode [Vers]; //建立顶点值 for(int i=0; i [Vers]; //建立顶点值 for(int i=0; i [Vers]; //建立顶点值 for(int i=0; i=Vers) return false; int v; if(verList[u].head!=NULL){ v=verList[u].head->data; return v; } v=-1; return -1; } //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集） //若顶点在G中没有邻接顶点，则返回false int GetNextAdjVex(int u,int v){//就是说第u行的第v+1个顶点 if(u<0||u>=Vers||v<0||v>=Vers) return false; edgeNode *p=verList[u].head; while(p){ if(p->data=https://www.it610.com/article/=v) break; p=p->next; } if(p->next){ return p->next->data; } return -1; } bool PutVer(int u,TypeOfVer data); //对G中指定顶点赋值 bool InsertVer(const TypeOfVer data); //往G中添加一个顶点 int LocateVer(TypeOfVer data); //返回G中指定顶点的位置 //对于有权图，取两端点为v1和v2的边上的权值。 //获取成功，返回true；否则，返回false bool GetWeight(int u,int v,int &w){//有权图也分为有向和无向 if(u<0||u>=Vers||v<0||v>=Vers) return false; if(GraphKind[0]!='U'){//如果是无向图，哪个顶点作为开头都可以 edgeNode *p=verList[u].head; while(p){ if(p->data=https://www.it610.com/article/=v){ w=p->weight; return true; } p=p->next; } } else{ edgeNode *p=verList[u].head; while(p){ if(p->data=https://www.it610.com/article/=v){ w=p->weight; return true; } p=p->next; } p=verList[v].head; //如果以u开始的起点没找到，再以v开头为起点找 while(p){ if(p->data=https://www.it610.com/article/=u){ w=p->weight; return true; } p=p->next; } } w=-1; return false; } //求指定顶点的（出）度（无向图/网：度； 有向图/网：出度 ） int Get_Degree(int u){ if(u<0||u>=Vers) return -1; int k=0; edgeNode *p=verList[u].head; while(p){ ++k; p=p->next; } return k; } //求有向图指定顶点的入度 int Get_InDegree(int u){ if(u<0||u>=Vers||GraphKind[0]=='U')//顶点不存在/非有向图返回-1 return -1; bool flag=false; int k=0; for(int i=0; i *p=verList[i].head; while(p){ if(p->data=https://www.it610.com/article/=u){ ++k; flag=true; } p=p->next; } } return flag ? k : -1; //如果入度不为0，返回k，否则返回-1 } //检查指定2个顶点是否是邻接顶点 bool ExistEdge(int u,int v){ if(GraphKind[0]=='U'){//如果是无向图的情况 edgeNode *p=verList[u].head; while(p){//只需要遍历一个就行 if(p->data=https://www.it610.com/article/=v) return true; p=p->next; } } else{ edgeNode *px=verList[u].head; while(px){ if(px->data=https://www.it610.com/article/=v) return true; px=px->next; } edgeNode *py=verList[v].head; while(py){ if(py->data=https://www.it610.com/article/=u) return true; py=py->next; } } return false; } //输出顶点集 void PrintVer(){ for(int i=0; i *p=verList[i].head; //从顶点开始遍历 while(p){ cout<<"->"weight!=-1) cout<<"("next; } cout<<"->nullptr"<nullptr"<=Vers||v<0||v>=Vers)//不在范围内时无法插入，返回false return false; if(verList[u].head!=NULL){ edgeNode *p=verList[u].head; //这个是判断如果本来就存在这条边的情况 while(p){ if(p->data=https://www.it610.com/article/=v) return false; p=p->next; } } edgeNode *x=new edgeNode(v); //直接使用构造函数赋值 //x.data=https://www.it610.com/article/v; 不要这么写 x->next=verList[u].head; //head本身就是指向的第一个指针，所以head后面不用加->next verList[u].head=x; ++Edges; //边数加一 return true; } //有权图插入一条边 bool Insert_Edge2(int u,int v,TypeOfEdge w=-1){//先给没赋值的权值赋为-1，如果不等于-1，就输出，否则不输出 if(u<0||u>=Vers||v<0||v>=Vers)//不在范围内时无法插入，返回false return false; if(verList[u].head!=NULL){ edgeNode *p=verList[u].head; //这个是判断如果本来就存在这条边的情况 while(p){ if(p->data=https://www.it610.com/article/=v) return false; p=p->next; } } edgeNode *x=new edgeNode(v); //直接使用构造函数赋值 //x.data=https://www.it610.com/article/v; 不要这么写 x->next=verList[u].head; //head本身就是指向的第一个指针，所以head后面不用加->next verList[u].head=x; x->weight=w; //给权值赋值 ++Edges; //边数加一 return true; } //往G中删除一个顶点 bool DeleteVer(int data){//因为题中传入的参数就是顶点的序号，根本不是顶点本身 if(data<0||data>=Vers)//如果不在范围内返回false return false; edgeNode *pw=verList[data].head; int k=0; //用来记录被删除的顶点有多少边与之相连 if(GraphKind[0]=='U'){ while(pw){//如果是无向图只需要记录要被删除的边表中有多少结点就够了 ++k; edgeNode *po=pw; pw=pw->next; delete po; } } else{//如果是有向图，我们需要遍历整个链表 edgeNode *rp=verList[data].head; while(rp){//这个循环是记录被删除顶点的边表的结点个数 ++k; rp=rp->next; } for(int i=0; i *r=verList[i].head; while(r){ if(r->data=https://www.it610.com/article/=data) ++k; r=r->next; } } } Edges-=k; //减掉边只有的边数 for(int i=data; i *px=verList[i].head; edgeNode *py=verList[i].head; while(px==py){//这个是判断如果与顶点结点相连的就是要删除的结点的情况 if(px==py&&px==NULL&&py==NULL) break; else if(px->data=https://www.it610.com/article/=data){ px=px->next; verList[i].head=px; edgeNode *q=py; py=py->next; delete q; } else if(px->data>data){ --(px->data); px=px->next; } } while(px){//当px在前，py在后时 if((px->data)>data){ --(px->data); px=px->next; } else if(px->data=https://www.it610.com/article/=data){//如果相等的话就删除这个结点 edgeNode *q=px; py->next=px->next; px=px->next; delete q; continue; } else if((px->data)next; py=py->next; } } return true; } bool DeleteEdge(int u,int v); //删除边 (外壳：有向（删除1条边）， 无向（删除2条边）） void DFS_Traverse(int u); //DFS遍历 //深度优先遍历 void DFS(int u){ cout<=0; w=GetNextAdjVex(u,w)){ if(!visited[w]){ cout<<"->"; DFS(w); } } } void BFS_Traverse(int u); //BFS遍历 //广度优先遍历 void BFS(int u){ cout<=0; w=GetNextAdjVex(u,w)){ if(!visited[w]){ cout<<"->"< *p=verList[u].head; while(!q.empty()){ m=q.front(); q.pop(); p=verList[m].head; while(p){ if(!visited[p->data]){ cout<<"->"<data].ver; visited[p->data]=true; q.push(p->data); } p=p->next; } }*/ } //~adjlist_graph(); //析构函数 }; template void shuchu(adjlist_graph &tu,int n){ //cout<>n; //输入顶点个数 for(int i=0; i>b[i]; //输入顶点集合 cin>>m; //输入边数 int **e; e=new int* [m]; for(int i=0; i>e[i][0]>>e[i][1]; //输入边集 /*int c[m]; for(int i=0; i>c[i]; //输入权集*/ adjlist_graph,int> tu(str,n,b,m,e); //使用构造函数构造图的类 int no,to; //指定的要删除的顶点 cin>>no; /*int jk; cin>>jk; //输入要插入边的权值*/ shuchu(tu,n); cout<