# Adjacency Matrix Constructing Unweighted Graphs

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

(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

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

};

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 >
private :
int Vers;         //Number of vertices
int Edges;        //Number of edges
//(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) ;
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;
}
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
for ( int i= 0 ;i<Vers;++i)
delete [] edge[i];
delete []edge;
}
};

template<class TypeOfVer,class TypeOfEdge>
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;
}

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];