邻接矩阵：构造只有结点没有边的图

冷不防 2023-09-29 15:37 24阅读 0赞

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

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

（2）使用构造函数，构造一个只有结点没有边的无权图。

注意：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:

adjmatrix\_graph( const string &kd, int vSize, const TypeOfVer d\[\], const TypeOfEdge noEdgeFlag); //构造函数构造一个只有结点没有边的图。4个参数的含义：图的类型、结点数、结点值和邻接矩阵中表示结点间没有边的标记（无权图：0，有权图：输入参数定）

adjmatrix\_graph( const string &kd, int vSize, int eSize, const TypeOfVer d\[\], int \*\*e); //构造函数构造一个无权图。5个参数的含义：图的类型、结点数、边数、结点集和边集

adjmatrix\_graph( const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d\[\], int \*\*e, const TypeOfEdge w\[\]); //构造函数构造一个有权图。7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集

bool GraphisEmpty() \{ return Vers == 0; \} //判断图空否

string GetGraphKind()\{ return GraphKind; \}

bool GetVer(int u, TypeOfVer &data); //取得G中指定顶点的值

int GetFirstAdjVex(int u, int &v); //返回G中指定顶点u的第一个邻接顶点的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

int GetNextAdjVex(int u, int v, int &w); //返回G中指定顶点u的下一个邻接顶点（相对于v）的位序（顶点集）。若顶点在G中没有邻接顶点，则返回-1

bool PutVer(int u, TypeOfVer data); //对G中指定顶点赋值

bool InsertVer(const TypeOfVer &data); //往G中添加一个顶点

int LocateVer(TypeOfVer data); //返回G中指定顶点的位置

bool PrintMatrix(); //输出邻接矩阵

int GetVerNum()\{ return Vers;\} //取得当前顶点数

int GetEdgeNum()\{ return Edges;\} //取得当前边数

bool Insert\_Edge(int u, int v); //无权图插入一条边

bool Insert\_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边

bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点

bool Delete\_Edge(int u, int v); //无权图删除一条边

bool Delete\_Edge(int u, int v, TypeOfEdge w); //有权图删除一条边

void DFS\_Traverse(int u); //DFS遍历（外壳部分）

void BFS\_Traverse(int u); //BFS遍历

~adjmatrix\_graph(); //析构函数

\};

![615cf10a05a24c469114e43c5a4aadfb.png][]

![bfa87dd2a8374699ac8872fc740700a3.png][]

输出范例：

UDN  
1 2 3 4 5 6

\-1 -1 -1 -1 -1 -1  
\-1 -1 -1 -1 -1 -1  
\-1 -1 -1 -1 -1 -1  
\-1 -1 -1 -1 -1 -1  
\-1 -1 -1 -1 -1 -1  
\-1 -1 -1 -1 -1 -1

#include<iostream>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<queue>
    using namespace std;
    int b[10001]={0};
    //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 TypeOfVer[Vers];
                ver=d;//这个要写，然后就不用写下面的赋值了
                noEdge=noEdgeFlag;//这个赋值一开始没写
                //for(int i=0;i<vSize;++i)
                //    ver[i]=d[i];
                edge=new TypeOfVer* [Vers];
                for(int i=0;i<vSize;++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,int eSize,TypeOfVer d[],int **e);
           //构造函数构造一个有权图。
           //7个参数的含义：图的类型、结点数、边数、无边标记、结点集、边集、权集
           adjmatrix_graph(string &kd,int vSize,int eSize,TypeOfEdge noEdgeFlag,TypeOfVer d[],int **e,const TypeOfEdge w[]);
           //判断图空否
           bool GraphisEmpty(){ return Vers==0; }
           //获取图的类型
           string GetGraphKind(){ return GraphKind; }
           //取得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,int &w);
           //对G中指定顶点赋值
           bool PutVer(int u, TypeOfVer data);
           //往G中添加一个顶点
           bool InsertVer(const TypeOfVer &data);
           //返回G中指定顶点的位置
           int LocateVer(int x,TypeOfVer data){
                data=ver[x];
                return data;
           }
           //输出邻接矩阵
           void PrintMatrix(){
                int i,j;
                for(i=0;i<Vers;++i){
                    for(j=0;j<Vers;++j)
                        cout<<edge[i][j]<<" ";
                    if(i!=Vers-1)
                        cout<<endl;
                }
           }
           int GetVerNum(){ return Vers;}//取得当前顶点数
           int GetEdgeNum(){ return Edges;} //取得当前边数
           bool Insert_Edge(int u, int v); //无权图插入一条边
           bool Insert_Edge(int u, int v, TypeOfEdge w); //有权图插入一条边
           bool DeleteVer(const TypeOfVer &data); //往G中删除一个顶点
           bool Delete_Edge(int u, int v); //无权图删除一条边
           bool Delete_Edge(int u, int v, TypeOfEdge w); //有权图删除一条边
           void DFS_Traverse(int u); //DFS遍历（外壳部分）
           void BFS_Traverse(int u); //BFS遍历
           ~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;
        for(int i=0;i<n;++i){
            x=tu.LocateVer(i,x);  //这个输出是一定要用ver数组才行，不能在主函数里写输出b数组
            if(i==0)
                cout<<x;
            else
                cout<<" "<<x;
        }
        cout<<endl<<endl;
        tu.PrintMatrix();
    }
    
    
    int main(){
        int n,m,bian;
        string str;
        getline(cin,str);
        cin>>n;
        for(int i=0;i<n;++i)
            cin>>b[i];
        cin>>m;
        adjmatrix_graph<int,int> tu(str,n,b,m);
        shuchu(tu,n);
        return 0;
    }

这里面有好多需要注意的点

1.输出顶点集的时候（我用的b数组来存储顶点集）应该写在整体的输出里面，而不是单独输出b数组。它这个输出都是按照类里面的数组里面看的，不是输入的数组，如果直接输出输入的数组，结果是不对的。系统判断的时候是按照类里面的顶点集来判断的。

2.构造这个函数主要是用到第一个构造函数，只传4个参数就够了。

3.邻接矩阵中无穷的表示用noEdge表示，首先是在主函数中输入，通过传参数传到构造函数里面，将这个参数的值赋给noEdge，再用noEdge给邻接矩阵里面的值赋值，这样才是正确的赋值，否则还是有错误的。

其他的暂时应该没有什么要注意的，做这个题我提交了好多次，啊，期间参考了一下别人的，是我的错。编程之路漫漫，慢慢来，只要有进步就好。

[615cf10a05a24c469114e43c5a4aadfb.png]: https://img-blog.csdnimg.cn/615cf10a05a24c469114e43c5a4aadfb.png
[bfa87dd2a8374699ac8872fc740700a3.png]: https://img-blog.csdnimg.cn/bfa87dd2a8374699ac8872fc740700a3.png