邻接矩阵：有向图顶点的入度

Love The Way You Lie 2023-09-28 08:54 13阅读 0赞

目的：使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型（ADT）。

内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接矩阵ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）

（2）设计并实现一个算法，在已存在的有向图中求指定顶点的入度。如顶点不存在，返回-1；否则返回其对应的入度。图的存储结构采用邻接矩阵。将其加入到ADT中。

参考函数原型：

//求有向图指定顶点的入度

template<class TypeOfVer, class TypeOfEdge>

int adjmatrix\_graph<TypeOfVer, TypeOfEdge>::Get\_InDegree(int u);

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

> 输出说明：
> 
> 第一行：顶点集
> 
> 空行
> 
> 第二行：邻接矩阵
> 
> 第三行：指定顶点的序号
> 
> 空行
> 
> 第四行：顶点的入度（顶点不存在/非有向图：-1）

> 输入范例：
> 
> DG  
> 6  
> A B C D E F  
> 6  
> 0 1  
> 0 2  
> 1 3  
> 2 3  
> 3 4  
> 3 5  
> 3

> 输出范例：
> 
> A B C D E F
> 
> 0 1 1 0 0 0  
> 0 0 0 1 0 0  
> 0 0 0 1 0 0  
> 0 0 0 0 1 1  
> 0 0 0 0 0 0  
> 0 0 0 0 0 0
> 
> 2

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    #include<stack>
    #include<cmath>
    using namespace std;
    string b[10001];//放顶点集
    //DG（有向图） DN（有向网） UDG（无向图） UDN（无向网）
    
    template<class TypeOfVer,class TypeOfEdge>//顶点类型与边的类型
    class adjmatrix_graph{                    //顶点用字符串，边用整型
        private:
           int Vers;        //顶点数
           int Edges;       //边数
           TypeOfEdge **edge;//邻接矩阵
           //(TypeOfEdge表示顶点关系类型。对于无权图，用1或0，表示相邻否；对于带权图，则为权值类型)
           TypeOfVer *ver;    //存放结点值
           TypeOfEdge noEdge;  //邻接矩阵中的∞的表示值
           string GraphKind;   //图的种类标志
           bool DFS(int u,int &num,int visited[]); //DFS遍历（递归部分）
        public:
            //构造函数构造一个只有结点没有边的图。4个参数的含义：
            //图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记
            //（无权图：0，有权图：输入参数定）
           adjmatrix_graph(string kd,int vSize,TypeOfVer d[],TypeOfEdge noEdgeFlag){
                GraphKind=kd;
                Vers=vSize;
                ver=new TypeOfEdge[Vers];
                ver=d;//这个要写，然后就不用写下面的赋值了
                noEdge=noEdgeFlag;//这个赋值一开始没写
                //for(int i=0;i<vSize;++i)
                //    ver[i]=d[i];
                Edges=0;
                edge=new TypeOfVer* [Vers];//构建邻接矩阵是按顶点数来分有多少行和列的
                for(int i=0;i<Vers;++i)
                    edge[i]=new TypeOfVer [Vers];
                for(int i=0;i<Vers;++i){
                    for(int j=0;j<Vers;++j){
                        edge[i][j]=noEdge;
                    }
                }
           }
           //构造函数构造一个无权图。
           //5个参数的含义：图的类型、结点数、结点集 、边数、和边集
           adjmatrix_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e){
                GraphKind=kd;
                Vers=vSize;
                Edges=eSize;
                ver=new TypeOfVer [Vers];
                ver=d;
                noEdge=0;//这个不确定的值在每个构造函数里面都要写上才行，可能就是得根据这个进行函数初始化吧
                edge=new TypeOfEdge* [Vers];
                for(int i=0;i<Vers;++i)
                    edge[i]=new TypeOfEdge [Vers];
                for(int i=0;i<Vers;++i){
                    for(int j=0;j<Vers;++j)
                        edge[i][j]=noEdge;
                }
                if(GraphKind[0]!='U'){//当是有向的情况的时候
                    for(int i=0;i<Edges;++i)//这个看图中有哪些边存在是要看输入的边数
                        edge[e[i][0]][e[i][1]]=1;//不是直接用顶点数判断的
                }
                else{
                    for(int i=0;i<Edges;++i)
                        edge[e[i][0]][e[i][1]]=edge[e[i][1]][e[i][0]]=1;
                }
           }
           //构造函数构造一个有权图。
           //7个参数的含义：图的类型、顶点数、顶点集、边数、边集、   无边标记、权集
           adjmatrix_graph(string kd,int vSize,TypeOfVer d[],int eSize,int **e,
                             TypeOfEdge noEdgeFlag,TypeOfEdge w[]){
                GraphKind=kd;
                Vers=vSize;
                Edges=eSize;
                TypeOfEdge *quan;
                quan=new TypeOfEdge [1001];
                quan=w;//权集
                ver=new TypeOfVer [Vers];
                ver=d;
                noEdge=noEdgeFlag;//函数传进来noEdgeFlag，就把这个值赋给noEdge,否则就赋值为0
                edge=new TypeOfEdge* [Vers];
                for(int i=0;i<Vers;++i)
                    edge[i]=new TypeOfEdge [Vers];
                for(int i=0;i<Vers;++i){
                    for(int j=0;j<Vers;++j)
                        edge[i][j]=noEdge;
                }
                if(GraphKind=="DN"||GraphKind=="DG"){//当是有向的情况的时候
                    for(int i=0;i<Edges;++i)//给每个边赋权值就要用边的个数作为临界条件
                        edge[e[i][0]][e[i][1]]=quan[i];
                }
                else{
                    for(int i=0;i<Edges;++i)
                        edge[e[i][0]][e[i][1]]=edge[e[i][1]][e[i][0]]=quan[i];
                }
                //for(int i=0;i<Edges;++i)
                 //   edge[e[i][0]][e[i][1]]=quan[i];
           }
           //判断图空否
           bool GraphisEmpty(){ return Vers==0; }
           //获取图的类型
           string GetGraphKind(){ return GraphKind; }
           int GetVerNum(){ return Vers;}//取得当前顶点数
           int GetEdgeNum(){ return Edges;} //取得当前边数
           //取得G中指定顶点的值
           bool GetVer(int u,TypeOfVer &data);
           //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1
           int GetFirstAdjVex(int u,int &v);
           //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。
           //若顶点在G中没有邻接顶点，则返回-1
           int GetNextAdjVex(int u,int v){
                if(u<0||u>=Vers)
                    return -1;
                if(v<0||v>=Vers)
                    return -1;
                for(int i=v+1;i<Vers;++i){//i从v+1之后再循环
                    if(edge[u][i]!=noEdge)
                        return i;
                }
                return -1;
           }
           //对G中指定顶点赋值
           bool PutVer(int u, TypeOfVer data);
           //往G中添加一个顶点
           bool InsertVer(const TypeOfVer &data);
           //返回顶点集中下标为x的值  根据下标返回一个顶点，所以类型是string
           string LocateVer1(int x){//想精确的找某个值用这个函数
                if(x<0||x>=Vers)
                    return "no";
                return ver[x];
            }
           //返回G中指定顶点的位置,这个返回的是下标
           int LocateVer2(TypeOfVer data){//遍历用这个函数
                for(int i=0;i<Vers;++i){
                    if(data==ver[i])
                        return i;
                }
                return -1;
           }
           //输出邻接矩阵
           void PrintMatrix(){
                for(int i=0;i<Vers;++i){
                    for(int j=0;j<Vers;++j)
                        cout<<edge[i][j]<<" ";
                    cout<<endl;
                }
           }
           bool Insert_Edge(int u, int v); //无权图插入一条边
           bool YouInsert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
           bool DeleteVer(TypeOfVer data){//在G中删除一个顶点
                int x=LocateVer2(data);//x是要删除的顶点的位置
                if(x==-1)//如果没有找到要删除的顶点返回-1
                    return false;
                for(int i=x;i<Vers-1;++i)//把后面的顶点都往前移一位,把原来顶点
                    ver[i]=ver[i+1];     //覆盖，就相当于删除了
                for(int i=x;i<Vers-1;++i){
                    for(int j=0;j<Vers;++j)
                        edge[i][j]=edge[i+1][j];
                }
                for(int i=0;i<Vers;++i){//列
                    for(int j=x;j<Vers-1;++j)
                        edge[i][j]=edge[i][j+1];
                }
                --Vers;
                return true;
           }
           //有向网或无向网删除一条边
           bool Delete_Edge(int u,int v){
                if(GraphKind[0]!='U'){//有向的情况
                    if(edge[u][v]!=noEdge){
                        edge[u][v]=noEdge;
                        --Edges;
                        return true;
                    }
                    else
                        return false;
                }
                else{
                    if(edge[u][v]!=noEdge&&edge[v][u]!=noEdge){
                        edge[u][v]=noEdge;
                        edge[v][u]=noEdge;
                        --Edges;
                        return true;
                    }
                    else
                        return false;
                }
                return 1;
           }
           void DFS_Traverse(int u); //DFS遍历（外壳部分）
           void BFS_Traverse(int u); //BFS遍历
           //求下标为u的顶点的入度的个数    （行入列出）
           //template<class TypeOfVer,class TypeOfEdge>
           int Get_InDegree(int u);
           ~adjmatrix_graph() {//析构函数
               for(int i=0;i<Vers;++i)
                   delete [] edge[i];
               delete []edge;
           }
    };
    
    template<class TypeOfVer,class TypeOfEdge>
    void shuchu(adjmatrix_graph<TypeOfVer,TypeOfEdge> &tu,int n){
        //cout<<tu.GetGraphKind()<<endl;
        TypeOfVer x;
        //TypeOfEdge we;
        //we=tu.GetEdgeNum();//返回第一个边数
        for(int i=0;i<n;++i){//输出顶点集
            x=tu.LocateVer1(i);//这个输出是一定要用ver数组才行，不能在主函数里写输出b数组
            if(i==0)
                cout<<x;
            else
                cout<<" "<<x;
        }
        //cout<<endl<<we<<endl;
        cout<<endl<<endl;
        tu.PrintMatrix();//输出邻接矩阵
        cout<<endl;
    }
    
    //求有向图指定顶点的入度
    template<class TypeOfVer,class TypeOfEdge>
    int adjmatrix_graph<TypeOfVer,TypeOfEdge>::Get_InDegree(int u){
        if(GetGraphKind()[0]=='U')//无向图直接返回-1
            return -1;
        int n=0,m;
        string kkk;
        kkk=LocateVer1(u);//没有找到这个顶点返回-1
        if(kkk=="no")
            return -1;
        //cout<<kkk<<endl<<endl;
        for(int j=0;j<Vers;++j){
            if(edge[u][j]!=noEdge)
                ++n;
        }
        return n;
    }
    
    int main(){
        int n,m;
        string str;//图的类型
        getline(cin,str);
        cin>>n;//顶点数
        for(int i=0;i<n;++i)
            cin>>b[i];//顶点集合
        //int no;
        //cin>>no;//无边标记
        cin>>m;//边数
        int **a;
        a=new int* [m];
        for(int i=0;i<m;++i)
            a[i]=new int [2];
        for(int i=0;i<m;++i)
            cin>>a[i][0]>>a[i][1];//输入边集
        //string ans;
        //cin>>ans;//输入的顶点
        int k;
        cin>>k;
        /*int *c;
        c=new int [m];
        for(int i=0;i<m;++i)
            cin>>c[i];//输入权集*/
        //int u,v;
        //cin>>u>>v;//输入要删除边的弧头和弧尾
        adjmatrix_graph<string,int> tu(str,n,b,m,a);
        //cout<<tu.GetGraphKind()<<endl;
        shuchu(tu,n);
        cout<<tu.Get_InDegree(k)<<endl;
        return 0;
    }

说实话，一开始我读这个题的时候，我真的没有理解它的意思，我觉得题中有的东西说的都是矛盾的（上面的用例的颜色是我自己加上去的，没有对原本的题目做改动）。

它要求指定顶点的入度，输入用例的6个顶点是A，B，C，D，E，F，它要求的入度的顶点是3？？？？？？

看到这还可以理解，正常按题意应该是输出-1，因为3不在顶点集里面。

但是最后却输出了2？？？？？ 这2是啥？3不是顶点为什么会输出入度？？

还有一个就是如果找到了这个顶点，但是它还要输出它的序号，但是输出用例中并没有输出序号。这种种迹象让人（我）感觉很疑惑，相当疑惑。

--------------------

然后我就一遍又一遍的读题，读了好久啊真的是，最后还是没有完全理解。

但是我看他给的函数传的参数是整型变量，我猜测它可能是要传的是顶点的下标，也只有这种解释可以理解。或者如果想认为他是想传一个顶点的话，那就把

int Get_InDegree(int u);

这个函数的参数成

int Get_InDegree(TypeOfVer u);

这个样子，应该也是可以做出来的。