.无向图的邻接矩阵是对称的： ·有向图的邻接矩阵可能是不对称的。 .在有向图中，统计第i行1的个数可得顶点i的出 度，统计第j列1的个数可得顶点的入度。 在无向图中，统计第i行（列列）1的个数可得顶点i 的度。 16
• 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出 度，统计第 j 列 1 的个数可得顶点 j 的入度。 • 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。 16 • 无向图的邻接矩阵是对称的; • 有向图的邻接矩阵可能是不对称的
网络（带权图)的邻接矩阵 W(i,j),若i≠j且<i,j>∈E或(i,j)∈E A.Edge [i][], 若i≠且<i,j>廷E或(i,)年E 0, 若i==j 8 2 0 1 00 4 6 00 0 9 2 3 9 5 2 A.Edge= 3 5 0 8 4 00 00 6 0 0 1 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> friend istream&operator>>(istream&in,Graphmtx<T E>&G); friend ostream&operator <(ostream&out,Graphmtx<T, E>&G); /输出 private: T *VerticesList; /顶点表 E**Edge; /邻接矩阵 int get VertexPos (T vertex){ /给出顶点vertex在图中的位置 for (inti=0;i<num Vertices;i++) if (VerticesList[i]=vertex)return i; return -1; }; 18
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); /构造函数 Graphmtx ( 川析构函数 {delete []VerticesList; for (i=0;i<max Vertices;i++) delete Edge [i]; delete Edge; T getValue (int i){ /川取顶点i的值，i不合理返回0 returni>=0 &&i<num Vertices VerticesList[i:NULL; E get Weight(int vl,intv2){/取边(vl,v2)上权值 return v1 !=-1 &v2!=-1 Edge[v1][v2]0; 3 19
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 getFirstNeighbor (int v); 川取顶点V的第一个邻接顶点 int getNextNeighbor (int v,int w); 川取V的邻接顶点W的下一邻接顶点 bool insert Vertex(const T vertex); /插入顶点vertex bool insertEdge (int v1,int v2,E cost); /插入边(V1,V2),权值为c0st bool remove Vertex (int v); /川删去顶点V和所有与它相关联的边 bool removeEdge (int vl,int v2); /在图中删去边(V1,V2) ; 20
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