template <class T,class E> Graphmtx<T,E>::Graphmtx (int sZ){ /造函数 max Vertices sZ; num Vertices =0;numEdges =0; int i,j; VerticesList=new T[max Vertices];/创建顶点表 Edge=(E **new E*[max Vertices]; for (i=0;i<max Vertices;i++) Edge[i]new E[max Vertices]; /邻接矩阵 for (i=0;i<max Vertices;i++) /川矩阵初始化 for (j=0;j<max Vertices;j++) Edge[i][i]=(i==j)?0:maxWeight; }; 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>:getFirstNeighbor (int v){ /川给出顶点位置为V的第一个邻接顶点的位置， /如果找不到，则函数返回-1 if(v=-1){ for (int col =0;col num Vertices;col++) if (Edge[v][col]>0&&Edge[v][col]maxWeight) return col; } return -1; }; 22
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){ /川给出顶点V的某邻接顶点W的下一个邻接顶点 if(v!=-1&&w!=-1){ for (int col w+1;col num Vertices;col++) if (Edge[v][col]>0&&Edge[v][col]maxWeight) return col; return -1; }; 23
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) 以邻接矩阵表示图，当边数远远小于2的时候，大量元 素是max Weight,会造成空间浪费。 邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的 各行分别组织为一个单链表。 。 在邻接表中，同一个顶点发出的边链接在同一个边链表 中，每一个链表结点代表一条边（边结点)，结点中有 另一顶点的标识dest和指针ink。对于带权图，边结点 中还要保存该边的权值cost。 顶点表的第ⅰ个顶点中保存该顶点的数据，以及它对应 边链表的头指针adj。 24
邻接表 (Adjacency List) • 以邻接矩阵表示图，当边数远远小于n 2 的时候，大量元 素是maxWeight，会造成空间浪费。 • 邻接表是邻接矩阵的改进形式。为此需要把邻接矩阵的 各行分别组织为一个单链表。 • 在邻接表中，同一个顶点发出的边链接在同一个边链表 中，每一个链表结点代表一条边（边结点），结点中有 另一顶点的标识 dest 和指针 link。对于带权图，边结点 中还要保存该边的权值cost。 • 顶点表的第 i 个顶点中保存该顶点的数据，以及它对应 边链表的头指针adj。 24
无向图的邻接表 data adj dest link dest link A 3 B B 2 3 统计某顶点对应边链表中结点个数，可得该顶点 的度。 某条边W,V)在邻接表中有两个边结点，分别在第 ⅰ个顶点和第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