图的棋板基类 const int max Weight ,穷大的值(=∞) const int default vertices=30;/最大顶点数(=n) template <class t, class ex class Graph i ∥图的类定义 rotected pI int max Vertices ∥图中最大顶点数 int nudGes ∥/当前边数 int num Vertices ∥当前顶点数 virtual int get Vertex Pos(t vertex) /给出顶点 vertex在图中位置 pu ublic
图的模板基类 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 Graph Empty o const /判图空否 ireturn num Edges==0; 1 int NumberofVerticeso return num Vertices; 3 /返回当前顶点数 int NumberOfEdgesoi return numEdges /回当前边数 virtual T get Value(int 1); 取顶点i的值 virtual e get Weight(int vI,intv2);/取边上权值 virtual int getFirstNeighbor (int v) 取顶点V的第一个邻接顶点
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 vl, int v2, E cost); 插入边vl,v2),权为cost virtual bool remove Vertex(int v); /删去顶点V和所有与相关联边 virtual bool remove Edge(int vl, int v2) 在图中删去边(v1,v2) 所有虚函数都与具体存储表示相关
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 matri刈)表示 在图的邻接矩阵表示中,有一个记录各个顶点信 息的顶点表,还有一个表示各个顶点之间关系的 邻接矩阵。 设图A=(V,E)是一个有n个顶点的图,图的邻接 矩阵是一个二维数组 A Edgez,定义: A Edge ill1如果<ij>∈E或者(i)∈E 0,否则
邻接矩阵 (Adjacency Matrix)表示 • 在图的邻接矩阵表示中，有一个记录各个顶点信 息的顶点表，还有一个表示各个顶点之间关系的 邻接矩阵。 • 设图 A = (V, E) 是一个有 n 个顶点的图, 图的邻接 矩阵是一个二维数组 A.Edge[n][n]，定义： 14 = , , , ( , ) . [ ][ ] 否 则 如 果 或 者 0 1 < > A Edge i j E i j E i j
0101 1010 ①2 A Edge 0101 3 「010 AEdge=101 000
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