济南大学信息科学与工程学院数据结构课件 第八章（1）.ppt

用邻接矩阵表示的图的类定义 template class T, class E class Graphmtx : public GraphT, E { friend istream operator ( istream in, GraphmtxT, E G); //输入 friend ostream operator (ostream out, GraphmtxT, E G); //输出 private: T *VerticesList; //顶点表 E **Edge; //邻接矩阵 int getVertexPos (T vertex) { //给出顶点vertex在图中的位置 for (int i = 0; i numVertices; i++) if (VerticesList[i] == Vertex) return i; return -1; }; public: Graphmtx (int sz = DefaultVertices); //构造函数 ～Graphmtx () //析构函数 { delete [ ]VerticesList; delete [ ]Edge; } T getValue (int i) { //取顶点 i 的值, i 不合理返回0 return i = 0 i = numVertices ? VerticesList[i] : NULL; } E getWeight (int v1, int v2) { //取边(v1,v2)上权值 return v1 != -1 v2 != -1 ? Edge[v1][v2] : 0; } int getFirstNeighbor (int v); //取顶点 v 的第一个邻接顶点 int getNextNeighbor (int v, int w); //取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex (const T vertex); //插入顶点vertex bool insertEdge (int v1, int v2, E cost); //插入边(v1, v2),权值为cost bool removeVertex (int v); //删去顶点 v 和所有与它相关联的边 bool removeEdge (int v1, int v2); //在图中删去边(v1,v2) }; template class T, class E GraphmtxT, E::Graphmtx (int sz) { //构造函数 maxVertices = sz; numVertices = 0; numEdges = 0; int i, j; VerticesList = new T[maxVertices]; //创建顶点表 Edge = (int **) new int *[maxVertices]; for (i = 0; i maxVertices; i++) Edge[i] = new int[maxVertices]; //邻接矩阵 for (i = 0; i maxVertices; i++) //矩阵初始化 for (j = 0; j maxVertices; j++) Edge[i][j] = (i == j) ？ 0 : maxWeight; }; template class T, class E int GraphmtxT, E::getFirstNeighbor (int v) { //给出顶点位置为v的第一个邻接顶点的位置, //如果找不到, 则函数返回-1 if (v != -1) { for (int col = 0; col numVertices; col++) if (Edge[v][col] Edge[v][col] maxWeight) return col; } return -1; }; template class T, class E int GraphmtxT, E: