73.1相邻矩阵 【代码72】图的基类 class Edge i ∥边类 public int from,to, weight;∥from是边的始点to是终点, weight是边的权 edge i ∥缺省构造函数 from=-1; to=-1; weight=0; Edge(int f, int t, int w)( ∥给定参数的构造函数 from =f; to=t; weight=w; class graph i public: int num Vertex: ∥图中顶点的个数 int numEdge; ∥图中边的条数 int marks ∥标记图的顶点是否被访问过 int *Indegree; ∥存放图中顶点的入度 Graph(int num vert)i ∥图的构造函数 num Vertex num Vert num edge=0 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.1 相邻矩阵 【代码7.2】 图的基类 class Edge { // 边类 public: int from, to, weight; // from是边的始点,to是终点,weight是边的权 Edge() { // 缺省构造函数 from = -1; to = -1; weight = 0; } Edge(int f,int t,int w) { // 给定参数的构造函数 from = f; to = t; weight = w; } }; class Graph { public: int numVertex; // 图中顶点的个数 int numEdge; // 图中边的条数 int *Mark; // 标记图的顶点是否被访问过 int *Indegree; // 存放图中顶点的入度 Graph(int numVert) { // 图的构造函数 numVertex = numVert; numEdge = 0;
73.1相邻矩阵 Indegree new int Vertex Mark= new intnumVertex for (int i=0;i< numVertex; i++)i Marki=UNVISItED ∥|标志位设为 UNVISITED Indegree=0 ∥入度设为0 Grapho i 析构函数 delete l Mark; 释放Mark数组 delete d Indegree ∥释放 Indegree a数组 int VerticesNumo i ∥返回图中顶点的个数 return numVertex; bool Is edge(edge one edge)i ∥ one edge是否是边 if (one Edge weight >0&& one edge weight INFINITY & one edge to >=0) return true else return false; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7.3.1 相邻矩阵 Indegree = new int[numVertex]; Mark = new int[numVertex]; for (int i = 0; i < numVertex; i++) { Mark[i] = UNVISITED; // 标志位设为UNVISITED Indegree[i] = 0; // 入度设为0 } } ~Graph() { // 析构函数 delete [] Mark; // 释放Mark数组 delete [] Indegree; // 释放Indegree数组 } int VerticesNum() { // 返回图中顶点的个数 return numVertex; } bool IsEdge(Edge oneEdge) { // oneEdge是否是边 if (oneEdge.weight > 0 && oneEdge.weight < INFINITY && oneEdge.to >= 0) return true; else return false; } };
代码73用相邻矩阵表示图 class Graph: public graph i private: int*matrⅸx;∥指向相邻矩阵的指针 public Graph(int num Vert): Graph(num Vert) ∥构造函数 tii;∥i,作为for循环中的计数器 matrix =(int*)new int*num Vertex; ∥申请 matrix数组行向量数组 for (i=0;i< num Vertex; i++) ∥申请 matrix数组行的存储空间 matrix=new int num Vertex ]; for(i=0; i num Vertex; i++) ∥相邻矩阵的所有元素都初始化为0 forgj=0;j< num Vertex: j ++) matrix [0=0; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 [代码7.3] 用相邻矩阵表示图 class Graphm: public Graph { private: int **matrix; // 指向相邻矩阵的指针 public: Graphm(int numVert):Graph(numVert) { // 构造函数 int i,j; // i, j作为for循环中的计数器 matrix = (int**)new int*[numVertex]; // 申请matrix数组行向量数组 for (i = 0;i < numVertex;i++) // 申请matrix数组行的存储空间 matrix[i] = new int[numVertex]; for (i = 0;i < numVertex;i++) // 相邻矩阵的所有元素都初始化为0 for (j = 0;j < numVertex;j++) matrix[i][j] = 0; }
Edge FirstEdge(int one Vertex)i ∥返回顶点 one vertex的第一条边 Edge my edge; my Edge from=one Vertex; ∥将顶点0 ne vertex作为边的始点 ∥寻找第一个使得 matrixone Vertex[不为0的道值 for (int i=0; i< numVertex; i ++)t if (matrix one Vertex!=0)t my Edge to =i my Edge weight= matrix one Vertex i; break;/找到了顶点 one vertex的第一条边 return my Edge; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 Edge FirstEdge(int oneVertex) { // 返回顶点oneVertex的第一条边 Edge myEdge; myEdge.from = oneVertex; // 将顶点oneVertex作为边的始点 // 寻找第一个使得matrix[oneVertex][i]不为0的i值 for (int i = 0; i < numVertex; i ++) { if (matrix[oneVertex][i] != 0) { myEdge.to = i; myEdge.weight = matrix[oneVertex][i]; break; //找到了顶点oneVertex的第一条边 } } return myEdge; }
Edge Nextedge( Edge pre edge){∥返回与边有相同关联顶点的下一条边 Edge my Edge ∥ myEdge的初始成员变量to为1 my Edge from= pre edge from;∥置边的始点为与上一条边 preedge相同 if(pre Edge to < num Vertex)& ∥如果 preedge to+1>= num Vertex,那么就不存在下一条边了 for(int i=preedge to+l; i< numVertex; i++)i ∥寻找下一个使得 matrixlpre Edge from不为0的道值,即下一条边 if(matrixpre edge from i!=0)i myEdge. to=1; my Edge weight=matrixpre Edge from rea return my edge; “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 Edge NextEdge(Edge preEdge) { // 返回与边有相同关联顶点的下一条边 Edge myEdge; // myEdge的初始成员变量to为-1 myEdge.from = preEdge.from; // 置边的始点为与上一条边preEdge相同 if (preEdge.to < numVertex){ // 如果preEdge.to+1 >= numVertex,那么就不存在下一条边了 for (int i = preEdge.to+1;i< numVertex;i++){ // 寻找下一个使得matrix[preEdge.from][i]不为0的i值，即下一条边 if (matrix[preEdge.from][i] != 0) { myEdge.to=i; myEdge.weight = matrix[preEdge.from][i]; break; } } } return myEdge; }