图的模板基类 const int maxWeight=......; /无穷大的值(=∞) const int Default Vertices 30; /最大顶点数(=n) template <class T,class E> class Graph /图的类定义 protected: int max Vertices; /图中最大顶点数 int numEdges; 川当前边数 int num Vertices; 川当前顶点数 virtual int get VertexPos(T vertex); /给出顶点vertex在图中位置 public: 11
图的模板基类 const int maxWeight = ……; //无穷大的值(=) const int DefaultVertices = 30; //最大顶点数(=n) template <class T, class E> class Graph { //图的类定义 protected: int maxVertices; //图中最大顶点数 int numEdges; //当前边数 int numVertices; //当前顶点数 virtual int getVertexPos (T vertex); //给出顶点vertex在图中位置 public: 11
Graph (int sz Default Vertices); /构造函数 GraphO; /析构函数 bool GraphEmpty (const /判图空否 {return numEdges ==0;} int NumberOfVertices ()return num Vertices; 川返回当前顶点数 int NumberOfEdges ()return numEdges; /返回当前边数 virtual T get Value (int i); /取顶点i的值 virtual E get Weight(int vl,intv2);/取边上枚值 virtual int getFirstNeighbor (int v); /取顶点V的第一个邻接顶点 12
Graph (int sz = DefaultVertices); //构造函数 ～Graph(); //析构函数 bool GraphEmpty () const //判图空否 { return numEdges == 0; } int NumberOfVertices () { return numVertices; } //返回当前顶点数 int NumberOfEdges () { return numEdges; } //返回当前边数 virtual T getValue (int i); //取顶点 i 的值 virtual E getWeight (int v1, int v2); //取边上权值 virtual int getFirstNeighbor (int v); //取顶点 v 的第一个邻接顶点 12
virtual int getNextNeighbor (int v,int w); /取邻接顶点W的下一邻接顶点 virtual bool insert Vertex(const T vertex); /插入一个顶点vertex virtual bool insertEdge (int v1,int v2,E cost); /插入边(V1,v2),权为c0st virtual bool remove Vertex (int v); /删去顶点V和所有与相关联边 virtual bool removeEdge (int v1,int v2); /川在图中删去边(1，V2) }; 所有虚丞数都与具体存储表示相关。 13
virtual int getNextNeighbor (int v, int w); //取邻接顶点w 的下一邻接顶点 virtual bool insertVertex (const T vertex); //插入一个顶点vertex virtual bool insertEdge (int v1, int v2, E cost); //插入边(v1,v2), 权为cost virtual bool removeVertex (int v); //删去顶点 v 和所有与相关联边 virtual bool removeEdge (int v1, int v2); //在图中删去边(v1,v2) }; 所有虚函数都与具体存储表示相关。 13
邻接矩阵(Adjacency Matrix)表示 ·在图的邻接矩阵表示中，有一个记录各个顶点信 息的顶点表，还有一个表示各个顶点之间关系的 邻接矩阵。 .设图A=(V,E)是一个有n个顶点的图，图的邻接 矩阵是一个二维数组A.Edgeln]n,定义： Aedge o. 1,如果<i,j>eE或者(i,)eE ,否则 14
邻接矩阵 (Adjacency Matrix)表示 • 在图的邻接矩阵表示中，有一个记录各个顶点信 息的顶点表，还有一个表示各个顶点之间关系的 邻接矩阵。 • 设图 A = (V, E) 是一个有 n 个顶点的图, 图的邻接 矩阵是一个二维数组 A.Edge[n][n]，定义： 14 = , , , ( , ) . [ ][ ] 否 则 如 果 或 者 0 1 < > A Edge i j E i j E i j
0 0 1 0 1 1 0 1 0 1 2 A.Edge 0 1 0 1 3 1 0 1 0 0 0 1 0 1 A.Edge 0 1 0 0 0 2 15
15 = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 A.Edge 0 1 2 3012 = 0 0 0 1 0 1 0 1 0 A.Edge