template <class T, class e> Graphite<T,E>: Graphix( int sz){/构造函数 max vertices = SZ; num Vertices=0; numEdges=0 Verticeslist=newT[ max Vertices」;/刨建顶点表 edge=(e**)new E*[max vertices ]; for (i=0; i< max Vertices; i++) Edge[i=newE[ max Vertices];∥邻接矩阵 for(i=0;i< max Vertices;i+)矩阵初始化 for g=0; j< max Vertices; j++) Edge=(i==0? 0: max Weight 21
template <class T, class E> Graphmtx<T, E>::Graphmtx (int sz) { //构造函数 maxVertices = sz; numVertices = 0; numEdges = 0; int i, j; VerticesList = new T[maxVertices]; //创建顶点表 Edge = (E **) new E*[maxVertices]; for (i = 0; i < maxVertices; i++) Edge[i] = new E[maxVertices]; //邻接矩阵 for (i = 0; i < maxVertices; i++) //矩阵初始化 for (j = 0; j < maxVertices; j++) Edge[i][j] = (i == j) ？ 0 : maxWeight; }; 21
template <class t, class e> int Graphmtx<T, E>: get FirstNeighbor (int v)t /)给出顶点位置为V的第一个邻接顶点的位置 如果找不到则函数返回-1 if(V!=-1){ for(int col=0; col num Vertices; col++) if (Edge v col]>0 && edgelvilcol] max Weight) return col; return-1
template <class T, class E> int Graphmtx<T, E>::getFirstNeighbor (int v) { //给出顶点位置为v的第一个邻接顶点的位置, //如果找不到, 则函数返回-1 if (v != -1) { for (int col = 0; col < numVertices; col++) if (Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col; } return -1; }; 22
template <class t, class e> int Graphmtx<T, E>: getNextNeighbor(int v, int w)t /给出顶点V的某邻接顶点W的下一个邻接顶点 if(V!=-1&&w!=-1){ for (int col=w+l; col num Vertices; col++) if(Edge v col]>0&& edgel v]col] max Weight return col: return };
template <class T, class E> int Graphmtx<T, E>::getNextNeighbor (int v, int w) { //给出顶点 v 的某邻接顶点w 的下一个邻接顶点 if (v != -1 && w != -1) { for (int col = w+1; col < numVertices; col++) if (Edge[v][col] >0 && Edge[v][col] < maxWeight) return col; } return -1; }; 23
邻接表( Adjacency List) 以邻接矩阵表示图,当边数远远小于m2的时候,大量元 素是 max Weigh,会造成空间浪费 邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的 各行分别组织为一个单链表。 在邻接表中,同一个顶点发出的边链接在同一个边链表 中,每一个链表结点代表一条边(边结点),结点中有 另一顶点的标识dest和指针ink。对于带权图,边结点 中还要保存该边的权值cost 顶点表的第i个顶点中保存该顶点的数据,以及它对应 边链表的头指针adj 24
邻接表 (Adjacency List) • 以邻接矩阵表示图，当边数远远小于n 2 的时候，大量元 素是maxWeight，会造成空间浪费。 • 邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的 各行分别组织为一个单链表。 • 在邻接表中，同一个顶点发出的边链接在同一个边链表 中，每一个链表结点代表一条边（边结点），结点中有 另一顶点的标识 dest 和指针 link。对于带权图，边结点 中还要保存该边的权值cost。 • 顶点表的第 i 个顶点中保存该顶点的数据，以及它对应 边链表的头指针adj。 24
无向图的邻接表 data adj dest link dest link A OA 3∧ 1 B B C 2∧ 2C 1∧ 3D 0 统计某顶点对应边链表中结点个数,可得该顶点 的度。 某条边(v,vy在邻接表中有两个边结点,分别在第 i个顶点和第j个顶点对应的边链表中。 25
无向图的邻接表 • 统计某顶点对应边链表中结点个数，可得该顶点 的度。 • 某条边(vi , vj )在邻接表中有两个边结点，分别在第 i 个顶点和第 j 个顶点对应的边链表中。 25 A B C D data adj A B C D 0 1 2 3 dest link dest link 1 3 0 2 1 0