锐客网

  1. 首页 > 睿知 > it技术 > >

#|邻接矩阵（有向图顶点的入度）

c++#DHU-----OJ图类模板

目的：使用C++模板设计并逐步完善图的邻接矩阵抽象数据类型（ADT）。
内容：（1）请参照图的邻接矩阵模板类原型，设计并逐步完善图的邻接矩阵ADT。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。）
（2）设计并实现一个算法，在已存在的有向图中求指定顶点的入度。如顶点不存在，返回-1；否则返回其对应的入度。图的存储结构采用邻接矩阵。将其加入到ADT中。

参考函数原型：
//求有向图指定顶点的入度
template
int adjmatrix_graph::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 #include #include #include #include #include #include using namespace std; string b[10001]; //放顶点集 //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 TypeOfEdge[Vers]; ver=d; //这个要写，然后就不用写下面的赋值了 noEdge=noEdgeFlag; //这个赋值一开始没写 //for(int i=0; i=Vers) return -1; if(v<0||v>=Vers) return -1; for(int i=v+1; i=Vers) return "no"; return ver[x]; } //返回G中指定顶点的位置,这个返回的是下标 int LocateVer2(TypeOfVer data){//遍历用这个函数 for(int i=0; i int Get_InDegree(int u); ~adjmatrix_graph() {//析构函数 for(int i=0; i void shuchu(adjmatrix_graph &tu,int n){ //cout< int adjmatrix_graph::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<>n; //顶点数 for(int i=0; i>b[i]; //顶点集合 //int no; //cin>>no; //无边标记 cin>>m; //边数 int **a; a=new int* [m]; for(int i=0; i>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>c[i]; //输入权集*/ //int u,v; //cin>>u>>v; //输入要删除边的弧头和弧尾 adjmatrix_graph tu(str,n,b,m,a); //cout<


说实话，一开始我读这个题的时候，我真的没有理解它的意思，我觉得题中有的东西说的都是矛盾的（上面的用例的颜色是我自己加上去的，没有对原本的题目做改动）。
它要求指定顶点的入度，输入用例的6个顶点是A，B，C，D，E，F，它要求的入度的顶点是3？？？？？？
看到这还可以理解，正常按题意应该是输出-1，因为3不在顶点集里面。
但是最后却输出了2？？？？？这2是啥？3不是顶点为什么会输出入度？？
还有一个就是如果找到了这个顶点，但是它还要输出它的序号，但是输出用例中并没有输出序号。这种种迹象让人（我）感觉很疑惑，相当疑惑。
然后我就一遍又一遍的读题，读了好久啊真的是，最后还是没有完全理解。
但是我看他给的函数传的参数是整型变量，我猜测它可能是要传的是顶点的下标，也只有这种解释可以理解。或者如果想认为他是想传一个顶点的话，那就把
int Get_InDegree(int u);

这个函数的参数成
int Get_InDegree(TypeOfVer u);

这个样子，应该也是可以做出来的。
但这种情况我没试，我按第一个方式做的就AC了。过了就行，因为还有好多其他的事情要做
【#|邻接矩阵（有向图顶点的入度）】 实现这个函数不难，把情况都考虑清楚，认真写一下就好了。

    推荐阅读


    上一篇：#|对简单字符串的排序整理（简单的2种方法）

    下一篇：我犯下的错误|错误（对不同类型变量定义相同变量名）