无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。 在有向图中,统计第i行1的个数可得顶点i的出 度,统计第/列1的个数可得顶点j的入度。 在无向图中统计第i行(列)1的个数可得顶点 的度
• 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出 度，统计第 j 列 1 的个数可得顶点 j 的入度。 • 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。 16 • 无向图的邻接矩阵是对称的; • 有向图的邻接矩阵可能是不对称的
网络(带权图)的邻接矩阵 w(ij,若i≠沮<i,j>∈E或(ij∈E AEde训门={m, 若i≠<,j>gE或(i,j￠E 0 若i==j 0092 52 A Edge 3508 060 17
17 = 6 0 3 5 0 8 0 9 2 0 1 4 A.Edge 8 6 3 1 9 5 2 4 2 0 3 1 网络（带权图）的邻接矩阵 == = i j i j i , j i , j i j i j i , j i , j i j 若 若 且 或 若 且 或 , , ( ) ( , ), ( ) [ ][ ] 0 E E W E E A.Edge
用邻接矩阵表示的图的类定义 template <class T, class E> class graphmtx public Graph<t, e> i friend istream& operator >> istream& in, Graphmtx<T, E>&G) friend ostream& operator <<(ostream& out, GraphmtX<T, E>&G); /出 private: T☆Ⅴ erticesList; 项点表 E**Edge ∥邻接矩阵 int get VertexPos(t vertex)( 给出顶点 vertex在图中的位置 for (int 1=0; 1< num Vertices; 1++) if (VerticesList[== vertex)return i return -I
template <class T, class E> class Graphmtx : public Graph<T, E> { friend istream& operator >> ( istream& in, Graphmtx<T, E>& G); friend ostream& operator << (ostream& out, Graphmtx<T, 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; }; 18 用邻接矩阵表示的图的类定义
public Graphmtx( int sz= Default vertices);/构造函数 Graphmtxo 析构函数 i delete[verticeslist for(i=0; 1< max vertices; 1++) delete edge 1 delete[ edge; j T get value(int it 取顶点i的值.i不合理返回0 returni>=o&&i< num vertices Verticeslisti]: NUL e get Weight( (int vl,intv2){∥取边(v1,v2)上权值 return vl !=-1&& v2!=-1? edgev1llv2]: 0;
public: Graphmtx (int sz = DefaultVertices); //构造函数 ～Graphmtx () //析构函数 { delete [ ]VerticesList; for (i = 0; i < maxVertices; i++) delete [ ] Edge [i]; 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; } 19
int get FirstNeighbor(int v) 取顶点V的第一个邻接顶点 int getNextNeighbor(int v, int w); 取v的邻接顶点W的下一邻接顶点 bool insert Vertex(const T vertex) /插入顶点 vertex bool insertedge(int vl, int v2, E cost); ∥插入边(V1,V2),权值为cost bool remove Vertex(int v) /删去顶点V和所有与它相关联的边 bool removeEdge(int vl, int v2) 在图中删去边(V1,v2)
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) }; 20