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

淩亂°似流年 2023-09-28 13:49 8阅读 0赞

> **问题描述：**  
> 设计并实现一个算法，应用递归的程序设计方法，对一个已存在的图进行广度优先遍历（BFS)，并输出遍历的顶点线性序列。遍历的起点通过输入指定。  
> 注意：遍历时，仅从该点出发遍历整个图，如果图不连通，则只遍历一个子图。图的存储结构采用邻接表。将其加入到ADT中。  
> 参考函数原型：  
> //BFS遍历  
> template<class TypeOfVer, class TypeOfEdge>  
> void adjlist\_graph<TypeOfVer, TypeOfEdge>::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<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    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<<"("<<p->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<<verList[u].ver;
                visited[u]=true;
                q.push(u);
                int m;
                edgeNode<TypeOfEdge> *p=verList[u].head;
                while(!q.empty()){
                    m=q.front();
                    q.pop();
                    p=verList[m].head;
                    while(p){
                        if(!visited[p->data]){
                            cout<<"->"<<verList[p->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.GetGraphKind()<<endl;
        tu.PrintVer();//输出顶点集
        int* x;//个数是int型
        x=tu.GetVerNum();
        //cout<<*x<<endl;//输出顶点个数
        //tu.PrintVer();//输出顶点集
        TypeOfEdge* we;
        we=tu.GetEdgeNum();
        //cout<<*we<<endl;//输出边数
        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<m;++i)
            cin>>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.GetNextAdjVex(no,to)<<endl;
        //tu.DFS(no);
        tu.BFS(no);
        //shuchu(tu,n);
        return 0;
    }

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

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