Adjacency Matrix Constructing Unweighted Graphs

Purpose: Use C++ templates to design and gradually improve the [adjacency matrix] abstract data type (ADT) of graphs.

Contents: (1) Please refer to the prototype of the adjacency matrix template class of the graph to design and gradually improve the adjacency matrix ADT of the graph. (Since the environment currently only supports single-file compilation, all contents are concentrated in one source file. In actual design, it is recommended to put [abstract classes] Please refer to the prototype of the adjacency matrix template class of the graph to design and gradually improve the adjacency matrix ADT of the graph. (Since the environment currently only supports single-file compilation, all contents are concentrated in one source file. In actual design, it is recommended to put [abstract classes] and corresponding derived classes in separate header files.)

(2) Use the [constructor] Use the [constructor] to construct an unweighted graph with nodes and edges.

Note: DG (Directed Graph), DN (Directed Network), UDG (Undirected Graph), UDN (Undirected Network)

The adjacency matrix template class prototype reference of graph is as follows:

template

class adjmatrix_graph{

private:

int Vers; //Number of vertices 

int Edges; // number of edges 

TypeOfEdge **edge; //Store the adjacency matrix (TypeOfEdge represents the vertex relationship type. For an unweighted graph, use 1 or 0 to indicate whether it is adjacent; for a weighted graph, it is the weight type) 

TypeOfVer *ver; //Store the node value 

TypeOfEdge noEdge; //The representation value of ∞ in the adjacency matrix

string GraphKind; //The type flag of the graph 

bool DFS(int u, int &num, int visited[]); //DFS traversal (recursive part)

public:

adjmatrix_graph(const string &kd, int vSize, const TypeOfVer d[], const TypeOfEdge noEdgeFlag); //The constructor constructs a graph with only nodes and no edges. The meaning of the 4 parameters: the type of the graph, the number of nodes, the value of the node, and the mark in the adjacency matrix indicating that there is no edge between the nodes (unweighted graph: 0, weighted graph: input parameter set) 

adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); //The constructor constructs an unweighted graph. The meaning of the 5 parameters: the type of the graph, the number of nodes, the number of edges, the set of nodes and the set of edges 

adjmatrix_graph(const string &kd, int vSize, int eSize, const TypeOfEdge noEdgeFlag, const TypeOfVer d[], int **e, const TypeOfEdge w[]); //The constructor constructs a graph with rights. The meaning of the 7 parameters: the type of the graph, the number of nodes, the number of edges, the edgeless mark, the node set, the edge set, the weight set

bool GraphisEmpty() { return Vers == 0;} //Determine whether the graph is empty

string GetGraphKind(){ return GraphKind;}

bool GetVer(int u, TypeOfVer &data); //Get the value of the specified vertex in G 

int GetFirstAdjVex(int ​​u, int &v); // Returns the bit order (vertex set) of the first adjoining vertex of the specified vertex u in G. Returns -1 if the vertex has no adjacent vertices in G 

int GetNextAdjVex(int ​​u, int v, int &w); // Returns the bit order (vertex set) of the next adjacent vertex (relative to v) of the specified vertex u in G. Returns -1 if the vertex has no adjacent vertices in G

bool PutVer(int u, TypeOfVer data); // Assign value to the specified vertex in G 

bool InsertVer(const TypeOfVer &data); // add a vertex to G 

int LocateVer(TypeOfVer data); // returns the position of the specified vertex in G 

bool PrintMatrix(); // print the adjacency matrix 

int GetVerNum(){ return Vers;} // Get the current number of vertices 

int GetEdgeNum(){ return Edges;} // Get the current number of edges 

bool Insert_Edge(int u, int v); // Insert an edge in an unauthorised graph

bool Insert_Edge(int u, int v, TypeOfEdge w); // insert an edge with a graph

bool DeleteVer(const TypeOfVer &data); // delete a vertex from G

bool Delete_Edge(int u, int v); // unweighted graph deletes an edge 

bool Delete_Edge(int u, int v, TypeOfEdge w); // have the right to delete an edge in the graph 

void DFS_Traverse(int u); //DFS traverse (shell part)

void BFS_Traverse(int u); //BFS traverse

~adjmatrix_graph(); //destructor 

};

Input example:

UDG
6
1 2 3 4 5 6
6
0 1
0 2
0 3
1 4
2 4
3 5

Example output:

UDG
1 2 3 4 5 6

0 1 1 1 0 0 
1 0 0 0 1 0 
1 0 0 0 1 0 
1 0 0 0 0 1 
0 1 1 0 0 0 
0 0 0 1 0 0 

# include <iostream>
 # include <vector>
 # include <string>
 # include <sstream>
 # include <queue>
 using  namespace  std ;
 int b[ 10001 ]={ 0 };
 //DG (directed graph) DN (with Directed Network) UDG (Undirected Graph) UDN (Undirected Network)

template < class  TypeOfVer , class  TypeOfEdge >
 class  adjmatrix_graph { 
    private :
        int Vers;         //Number of vertices 
       int Edges;        //Number of edges 
       TypeOfEdge **edge; //Adjacency matrix 
       //(TypeOfEdge represents the vertex relationship type. For unweighted graphs, Use 1 or 0 to indicate whether it is adjacent or not; for a weighted graph, it is the weight type) 
       TypeOfVer *ver;     //Store the node value 
       TypeOfEdge noEdge;   //The representation value of ∞ in the adjacency matrix 
       string GraphKind;    //Graph kind flag 
       bool  DFS ( int u, int &num, int visited[]) ;//DFS traversal (recursive part) 
    public :
         //Constructor constructs a graph with only nodes and no edges. The meaning of the 4 parameters: 
        //The type of the graph, the number of nodes, the value of the node, and the mark in the adjacency matrix indicating that there is no edge between the nodes 
        // (unweighted graph: 0, weighted graph: input parameter set) 
       adjmatrix_graph( string kd, int vSize,TypeOfVer d[],TypeOfEdge noEdgeFlag){
            GraphKind=kd;
            Vers=vSize;
            ver=new TypeOfVer[Vers];
            ver=d; //This is to be written, and then there is no need to write the following assignment 
            noEdge=noEdgeFlag; //This assignment is not written at the beginning 
            //for(int i=0;i<vSize;++i) 
            //ver [i]=d[i]; 
            Edges= 0 ;
            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;
                }
            }
       }
       //The constructor constructs an unweighted graph. 
       //The meaning of the 5 parameters: the type of the graph, the number of nodes, the set of nodes, the number of edges, and the set of edges 
       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 ; //This indeterminate value must be written in each constructor. It may be necessary to initialize the function according to this 
            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;
                    //edge[i][j]=0;//It is not possible to directly assign a value like this
            }
            if(GraphKind=="DG"){
                for(int i=0;i<eSize;++i)
                    edge[e[i][0]][e[i][1]]=1;
            }
            else{
                for(int i=0;i<eSize;++i)
                    edge[e[i][0]][e[i][1]]=edge[e[i][1]][e[i][0]]=1;
            }
       }
       //Constructor constructs a graph with rights. 
       //The meaning of the 7 parameters: type of graph, number of nodes, number of edges, edgeless label, node set, edge set, weight set 
       adjmatrix_graph( string &kd, int vSize, int eSize,TypeOfEdge noEdgeFlag,TypeOfVer d[], int **e, const TypeOfEdge w[]);
        //Determine whether the graph is empty 
       bool  GraphisEmpty () { return Vers== 0 ; }
        //Get the type 
       string of the  graph GetGraphKind () { return GraphKind; }
        //Get the specified in G vertex value 
       bool  GetVer ( int u,TypeOfVer &data) ;
       //Return the bit order (vertex set) of the first adjacent vertex of the specified vertex u in G. If the vertex has no adjacent vertex in G, return -1 
       int  GetFirstAdjVex ( int u, int &v) ;
        //Return the position order (vertex set) of the next adjacent vertex (relative to v) of the specified vertex u in G. If the vertex has no adjacent vertex in G, return -1 
       int  GetNextAdjVex ( int u, int v, int &w) ;
        //Assign the specified vertex in G 
       bool  PutVer ( int u, TypeOfVer data) ;
        //Add to G A vertex 
       bool  InsertVer ( const TypeOfVer &data) ;
        //Returns the position of the specified vertex in G 
       int  LocateVer ( int x,TypeOfVer data){
            data=ver[x];
            return data;
       }
       //Output the adjacency matrix 
       void  PrintMatrix () {
             for ( int i= 0 ;i<Vers;++i){
                 for ( int j= 0 ;j<Vers;++j)
                     cout <<edge[i][j ]<< " " ;
                 cout << endl ;
            }
       }
       int  GetVerNum () { return Vers;} //Get the current number of vertices 
       int  GetEdgeNum () { return Edges;} //Get the current number of edges 
       bool  Insert_Edge ( int u, int v) ; //Insert an edge without the right graph 
       bool  Insert_Edge ( int u, int v, TypeOfEdge w) ; //Insert an edge to the graph 
       bool  DeleteVer ( const TypeOfVer &data) ; //Delete a vertex from G 
       bool  Delete_Edge ( int u, int v); //Unauthorized graph to delete an edge 
       bool  Delete_Edge ( int u, int v, TypeOfEdge w) ; //authorized graph to delete an edge 
       void  DFS_Traverse ( int u) ; //DFS traversal (shell part) 
       void  BFS_Traverse ( int u ) ; //BFS traversal 
       ~adjmatrix_graph() { //destructor 
           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){ //Output vertex set 
        x=tu.LocateVer(i,x); //This output must use the ver array, not in the main function write output b array 
        if (i== 0 )
             cout <<x;
         else 
            cout << " " <<x;
    }
    cout<<endl<<endl;
    tu.PrintMatrix(); //Output the adjacency matrix
}


int  main () {
     int n,m;
     string str; //type of graph 
    getline( cin ,str);
     cin >>n; //number of vertices 
    for ( int i= 0 ;i<n;++i)
         cin >>b[i]; //Vertex set 
    cin >>m; //Number of edges 
    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];

    adjmatrix_graph<int,int> tu(str,n,b,m,a);
    shuchu(tu,n);
    return 0;
}

The most important thing to note is that the title is “Constructing an Unauthorized Graph”, and it does not say directed or undirected. When I do it, I do it according to the undirected, without considering the directed thing, so I have submitted it many times. wa.

Oh, there is another point to pay attention to, this time the constructor uses a function with 5 parameters, and the last pass is a pointer, this pointer is used to store the edge set, the number of input edges represents how many rows it has, The number of columns is 2 columns, which is the relationship between the 2 vertices.

An undirected graph is an adjacency matrix where 2 edges are 1, and a directed graph is where only one edge is 1.

Leave a Comment

Your email address will not be published. Required fields are marked *