图的邻接表：广度优先遍历&&深度优先遍历

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

输入说明 :
建图的输入数据格式参见建图的算法说明。（以无权图为例）
第一行：图的类型
第二行：结点数
第三行：结点集
第四行：边数
第五行：边集
第六行：起始顶点的位序

输出说明 :
第一行：顶点集
第二行：邻接表
空行
第三行：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<int> q;//这个队列用于广度优先搜索存放顶点
bool visited[1001]={false};//一开始设为都没有被访问过
vector<int> po(10001);
//DG（有向图）  DN（有向网）  UDG（无向图） UDN（无向网）

//图的邻接表模板类原型参考如下：
//边表的顶点定义
template<class TypeOfEdge>//这个就是在边上的顶点定义
struct edgeNode{
    int data;
    TypeOfEdge weight;
    edgeNode<TypeOfEdge> *next;
    //构造函数，用于构造其他顶点（无权图）
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    edgeNode(int d,edgeNode<TypeOfEdge> *ptr=NULL){ data=d;next=ptr; }
    //构造函数，用于构造其他顶点（带权图）
    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    edgeNode(int d,TypeOfEdge w,edgeNode<TypeOfEdge> *ptr=NULL){
        data=d; weight=w; next=ptr;
    }
    int getData(){ return data; }//取得顶点的序号（顶点集）
    TypeOfEdge getWeight(){ return weight; }//取得边集中对应边的权值
    void SetLink(edgeNode<TypeOfEdge> *link ){ next=link; }//修改顶点的next域
    void SetData(int value){ data=value; }//修改顶点的序号（顶点集）
    void SetWeight(TypeOfEdge value){ weight=value; }//修改边集中对应边的权值
};

//图的邻接表类   这个结构体是存储顶点的结构体，里面包括顶点和它的下一个指针
template<class TypeOfVer,class TypeOfEdge>
struct verNode{
    TypeOfVer ver;//存放顶点名称
    edgeNode<TypeOfEdge> *head;//顶点的指针
    verNode(edgeNode<TypeOfEdge> *h=NULL){ head=h; }
    TypeOfVer getVer(){ return ver; }//取得顶点值（顶点集）
    edgeNode<TypeOfEdge> *getHead(){ return head; }//取得对应的边表的头指针
    void setVer(TypeOfVer value){ ver=value; }//设置顶点值（顶点集）
    void setHead(edgeNode<TypeOfEdge> *value){ head=value; }//设置对应的边表的头指针
};

template<class TypeOfVer,class TypeOfEdge>//顶点类型  边的类型
class adjlist_graph{
    private:
       int Vers;//顶点数
       int Edges;//边数
       string GraphKind;//图的种类标志
       verNode<TypeOfVer,TypeOfEdge> *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<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
            for(int i=0;i<Vers;++i){
                verList[i].ver=d[i];
                verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
            }
       }
       //构造函数构造一个无权图
       //5个参数的含义：图的类型、顶点数、顶点集、  边数和边集
       adjlist_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e){
            GraphKind=kd;
            Vers=vSize;
            Edges=eSize;
            verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
            for(int i=0;i<Vers;++i){
                verList[i].ver=d[i];
                verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
            }
            for(int i=0;i<Edges;++i){//从边开始构造顶点
                for(int j=0;j<Vers;++j){
                    if(e[i][0]==j){
                        if(GraphKind[0]!='U'){//有向图的情况就只有1个方向
                            Insert_Edge1(e[i][0],e[i][1]);
                            Edges-=1;
                            break;
                        }
                        else{//无向图的表结点的个数是边数的2倍
                            Insert_Edge1(e[i][0],e[i][1]);
                            Insert_Edge1(e[i][1],e[i][0]);
                            Edges-=2;
                            break;
                        }
                    }
                }
            }
       }
       //构造函数构造一个有权图
       //6个参数的含义：图的类型、顶点数、顶点集、      边数、边集         权集
       adjlist_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e,TypeOfEdge w[]){
            GraphKind=kd;
            Vers=vSize;
            Edges=eSize;
            verList=new verNode<TypeOfVer,TypeOfEdge> [Vers];//建立顶点值
            for(int i=0;i<Vers;++i){
                verList[i].ver=d[i];
                verList[i].head=NULL;//一开始构造的时候顶点还没有相邻的顶点
            }
            for(int i=0;i<Edges;++i){//从边开始构造顶点
                for(int j=0;j<Vers;++j){
                    if(e[i][0]==j){
                        if(GraphKind[0]!='U'){//有向图的情况就只有1个方向
                            Insert_Edge2(e[i][0],e[i][1],w[i]);
                            Edges-=1;
                            break;
                        }
                        else{//无向图的表结点的个数是边数的2倍
                            Insert_Edge2(e[i][0],e[i][1],w[i]);
                            Insert_Edge2(e[i][1],e[i][0],w[i]);
                            Edges-=2;
                            break;
                        }
                    }
                }
            }
       }
       bool GraphisEmpty(){ return Vers==0; }//判断图空否
       string GetGraphKind(){ return GraphKind; }//返回图的类型
       int* GetVerNum(){ return &Vers; }//取得当前顶点数
       int* GetEdgeNum(){ return &Edges; }  //取得当前边数
       bool GetVer(int u,TypeOfVer &data){//取得G中指定顶点的值
            return true;
       }
       //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）
       //若顶点在G中没有邻接顶点，则返回-1
       int GetFirstAdjVex(int u){
            if(u<0||u>=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<TypeOfEdge> *p=verList[u].head;
            while(p){
                if(p->data==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<TypeOfEdge> *p=verList[u].head;
                while(p){
                    if(p->data==v){
                        w=p->weight;
                        return true;
                    }
                    p=p->next;
                }
            }
            else{
                edgeNode<TypeOfEdge> *p=verList[u].head;
                while(p){
                    if(p->data==v){
                        w=p->weight;
                        return true;
                    }
                    p=p->next;
                }
                p=verList[v].head;//如果以u开始的起点没找到，再以v开头为起点找
                while(p){
                    if(p->data==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<TypeOfEdge> *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<Vers;++i){
                if(i==u)
                    continue;
                edgeNode<TypeOfEdge> *p=verList[i].head;
                while(p){
                    if(p->data==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<TypeOfEdge> *p=verList[u].head;
                while(p){//只需要遍历一个就行
                    if(p->data==v)
                        return true;
                    p=p->next;
                }
            }
            else{
                edgeNode<TypeOfEdge> *px=verList[u].head;
                while(px){
                    if(px->data==v)
                        return true;
                    px=px->next;
                }
                edgeNode<TypeOfEdge> *py=verList[v].head;
                while(py){
                    if(py->data==u)
                        return true;
                    py=py->next;
                }
            }
            return false;
       }
       //输出顶点集
       void PrintVer(){
           for(int i=0;i<Vers;++i){
                if(i==0)
                    cout<<verList[i].ver;
                else
                    cout<<" "<<verList[i].ver;
           }
           cout<<endl;
       }
       //输出邻接表
       void PrintAdjList(){
            for(int i=0;i<Vers;++i){
                cout<<verList[i].ver;
                if(verList[i].head!=NULL){
                    edgeNode<TypeOfEdge> *p=verList[i].head;//从顶点开始遍历
                    while(p){
                        cout<<"->"<<p->data;
                        /*if(p->weight!=-1)
                            cout<<"("<weight<<")";*/
                        p=p->next;
                    }
                    cout<<"->nullptr"<<endl;
                }
                else
                    cout<<"->nullptr"<<endl;
            }
       }
       //无权图插入一条边
       bool Insert_Edge1(int u,int v){//u是起点，v是终点
            if(u<0||u>=Vers||v<0||v>=Vers)//不在范围内时无法插入，返回false
                return false;
            if(verList[u].head!=NULL){
                edgeNode<TypeOfEdge> *p=verList[u].head;//这个是判断如果本来就存在这条边的情况
                while(p){
                    if(p->data==v)
                        return false;
                    p=p->next;
                }
            }
            edgeNode<TypeOfEdge> *x=new edgeNode<TypeOfEdge>(v);//直接使用构造函数赋值
            //x.data=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<TypeOfEdge> *p=verList[u].head;//这个是判断如果本来就存在这条边的情况
                while(p){
                    if(p->data==v)
                        return false;
                    p=p->next;
                }
            }
            edgeNode<TypeOfEdge> *x=new edgeNode<TypeOfEdge>(v);//直接使用构造函数赋值
            //x.data=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<TypeOfEdge> *pw=verList[data].head;
            int k=0;//用来记录被删除的顶点有多少边与之相连
            if(GraphKind[0]=='U'){
                while(pw){//如果是无向图只需要记录要被删除的边表中有多少结点就够了
                    ++k;
                    edgeNode<TypeOfEdge> *po=pw;
                    pw=pw->next;
                    delete po;
                }
            }
            else{//如果是有向图，我们需要遍历整个链表
                edgeNode<TypeOfEdge> *rp=verList[data].head;
                while(rp){//这个循环是记录被删除顶点的边表的结点个数
                    ++k;
                    rp=rp->next;
                }
                for(int i=0;i<Vers;++i){//这个循环就是记录其他链表中有多少是和被删除顶点有关的边
                    edgeNode<TypeOfEdge> *r=verList[i].head;
                    while(r){
                        if(r->data==data)
                            ++k;
                        r=r->next;
                    }
                }
            }
            Edges-=k;//减掉边只有的边数
            for(int i=data;i<Vers-1;++i){//将后面的顶点往前移一位
                verList[i].ver=verList[i+1].ver;
                verList[i].head=verList[i+1].head;//指针也要往前移一位
            }
            --Vers;
            //PrintAdjList();//输出邻接表用来测试顶点和指针的移动是否正确
            for(int i=0;i<Vers;++i){
                edgeNode<TypeOfEdge> *px=verList[i].head;
                edgeNode<TypeOfEdge> *py=verList[i].head;
                while(px==py){//这个是判断如果与顶点结点相连的就是要删除的结点的情况
                    if(px==py&&px==NULL&&py==NULL)
                        break;
                    else if(px->data==data){
                        px=px->next;
                        verList[i].head=px;
                        edgeNode<TypeOfEdge> *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==data){//如果相等的话就删除这个结点
                        edgeNode<TypeOfEdge> *q=px;
                        py->next=px->next;
                        px=px->next;
                        delete q;
                        continue;
                    }
                    else if((px->data)<data)
                        px=px->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<<verList[u].ver;
            visited[u]=true;
            int w;
            for(w=GetFirstAdjVex(u);w>=0;w=GetNextAdjVex(u,w)){
                if(!visited[w]){
                    cout<<"->";
                    DFS(w);
                }
            }
       }
       void BFS_Traverse(int u);       //BFS遍历
       //广度优先遍历
       void BFS(int u){
            cout<<verList[u].ver;
            visited[u]=true;
            q.push(u);
            int w;
            while(!q.empty()){
                u=q.front();
                q.pop();
                for(w=GetFirstAdjVex(u);w>=0;w=GetNextAdjVex(u,w)){
                    if(!visited[w]){
                        cout<<"->"<<verList[w].ver;
                        visited[w]=true;
                        q.push(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<class TypeOfVer,class TypeOfEdge>
void shuchu(adjlist_graph<TypeOfVer,TypeOfEdge> &tu,int n){
    //cout<
    tu.PrintVer();//输出顶点集
    int* x;//个数是int型
    x=tu.GetVerNum();
    //cout<<*x<
    //tu.PrintVer();//输出顶点集
    TypeOfEdge* we;
    we=tu.GetEdgeNum();
    //cout<<*we<
    tu.PrintAdjList();//输出邻接表
}


int main(){
    string str;//图的类型
    int n,m;//顶点数和边数
    getline(cin,str);
    cin>>n;//输入顶点个数
    for(int i=0;i<n;++i)
        cin>>b[i];//输入顶点集合
    cin>>m;//输入边数
    int **e;
    e=new int* [m];
    for(int i=0;i<m;++i)
        e[i]=new int [2];
    for(int i=0;i<m;++i)
        cin>>e[i][0]>>e[i][1];//输入边集
    /*int c[m];
    for(int i=0;i>c[i];//输入权集*/
    adjlist_graph<string,int> tu(str,n,b,m,e);//使用构造函数构造图的类
    int no,to;//指定的要删除的顶点
    cin>>no;
    /*int jk;
    cin>>jk;//输入要插入边的权值*/
    shuchu(tu,n);
    cout<<endl;
    //cout<
    //tu.DFS(no);
    tu.BFS(no);
    //shuchu(tu,n);
    return 0;
}

BFS函数如果只写被注释掉的代码也是可以过的。
没有注释是按书上的思路来的，通过使用队列来记录的方式。

这里面的深度优先遍历的代码也是可以用的，2中遍历方式的输入是一样的，只是调用的函数不同，如果想用深度优先遍历就把496行给注释掉，495行去掉注释就可以啦。