#|邻接矩阵（构造无权图） DHU-----OJ|#|类模板|c++|图

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

注意：DG（有向图）, DN（有向网）, UDG（无向图）, UDN（无向网）

图的邻接矩阵模板类原型参考如下：

template
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(); //析构函数
};
#|邻接矩阵（构造无权图）
文章图片

输入范例：
UDG
6
1 2 3 4 5 6
6
0 1
0 2
0 3
1 4
2 4
3 5
输出范例：
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 #include #include #include #include using namespace std; int b[10001]={0}; //DG（有向图） DN（有向网） UDG（无向图） UDN（无向网）template 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 void shuchu(adjmatrix_graph &tu,int n){ cout<>n; //顶点数 for(int i=0; i>b[i]; //顶点集合 cin>>m; //边数 int **a; a=new int* [m]; for(int i=0; i>a[i][0]>>a[i][1]; adjmatrix_graph tu(str,n,b,m,a); shuchu(tu,n); return 0; }

最需要注意的就是题目是要“构造无权图”，并没有说有向还是无向，我在做的时候都按照无向做的，没有考虑有向的事，所以提交了好多次都是WA。
哦，还有一个需要注意的地方，就是这次构造函数使用含有5个参数的函数，最后传的是一个指针，这个指针是用来存储边集的，输入边数就是代表它有多少行，而列数就是2列，就是2个顶点之间的关系嘛。
【#|邻接矩阵（构造无权图）】无向图就是邻接矩阵的2个边的是1，有向就只有一个边是1.