template <class Type> Graph <Type>: Graph(int sz)( /构造函数 for( int 1=0; 1< Sz; 1++) for( intj=0; j<Sz; j++) Edgell=0; CurrentEdges 三0 template <class Type> folat Graph<Type>:: Get Weight( int vl, int v2)i )给出以顶点V1和v2为两端点的边上的权值 if(v1!=-1&&v2!=-1 return Edgelv1v2]; else return o
template <class Type> Graph <Type> :: Graph ( int sz ) { //构造函数 for ( int i = 0; i < sz; i++ ) for ( int j = 0; j < sz; j++ ) Edge[i][j] = 0; CurrentEdges = 0; } template <class Type> folat Graph<Type> :: GetWeight( int v1, int v2 ) { //给出以顶点 v1 和 v2 为两端点的边上的权值 if (v1 != -1 && v2 != -1) return Edge[v1][v2]; else return 0; }
template <class Type> int Graph <Type>:: GetFirstNeighbor( const intv)i )给出顶点位置为V的第一个邻接顶点的位置 if(v!=-1){ for( int col=0; col<=VerticesList last col++) if( Edgelv]>0 && Edgelv[col]< Max Value return col else return-l
template <class Type> int Graph <Type>:: GetFirstNeighbor ( const int v ) { //给出顶点位置为v 的第一个邻接顶点的位置 if ( v != -1 ) { for ( int col = 0; col <= VerticesList.last; col++ ) if ( Edge[v][col] > 0 && Edge[v][col] < MaxValue ) return col; } else return -1; }
template <class Type> int Graph<Type>:: GetNextNeighbor( int v, int wi 给出顶点V的某邻接顶点W的下一个邻接顶点 int col: if(v!=-1&&wl=-1){ for( col=W+l; col < VerticesList lasts col++) if( edgell[col>0 & v Edge][col]< Max Value return col; return-1
template <class Type> int Graph<Type> :: GetNextNeighbor ( int v, int w ) { //给出顶点v的某邻接顶点w的下一个邻接顶点 int col; if ( v != -1 && w != -1 ) { for ( col = w+1; col <= VerticesList.last; col++ ) if ( Edge[v][col] > 0 && Edge[v][col] < MaxValue ) return col; } return -1; }
邻接表( Adjacency List) 无向图的邻接表 data adi dest link dest link 0A 3∧ ③B BeD 0 2∧ 1∧ 3 0∧ 同一个顶点发出的边链接在同一个边链表 中,每一个链结点代表一条边边结点结 点中有另一顶点的下标dest和指针link
邻接表 (Adjacency List) ◼ 无向图的邻接表 同一个顶点发出的边链接在同一个边链表 中，每一个链结点代表一条边(边结点), 结 点中有另一顶点的下标dest 和指针 link。 A B C D data adj A B C D 0 1 2 3 dest link dest link 1 3 0 2 1 0
有向图的邻接表和逆邻接表 data adi dest link ABO 0A+[1入 dest link 1B 0+2|人 2C| 邻接表出边表) data adi dest link 0A 1入 1B 0∧ 逆邻接表(入边表)
◼ 有向图的邻接表和逆邻接表 A B C data adj A B C 0 1 2 dest link dest link 邻接表 (出边表) data adj A B C 0 1 2 dest link 逆邻接表 (入边表) 1 0 2 0 1 1