template <class Type> Graph <Type>:: Graph( int sz )( ∥构造函数 for( int 1=0; 1< SZ; 1++) for( int j=0; j<Sz; j++) Edgell=0; CurrentEdges =0 template <class Type> folat Graph<Type>:: Get Weight( int vI, int v2)i ∥给出以顶点v1和v2为两端点的边上的权值 if (v1! =-1 &&v2 !=-1) return Edge[v1l[v2]; ese return u
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 int v)i )给出顶点位置为V的第一个邻接顶点的位置 if(v!=-1){ for( int col-0; col<= VerticesList last col++) if( edge[vi[col]>0 && Edgelvcol< Max value) return col; else return -1
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 w)t 给出顶点v的某邻接顶点W的下一个邻接顶点 int col if(v!=-1&&w!=-1){ for( col=w+l; col < VerticesList lasts col++) if( Edgell[col>0 & Edge[][col]< Max Value ) return col; return-l
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 B 0 2∧ 2e1| 3D 同一个顶点发出的边链接在同一个边链表 中,每一个链结点代表一条边(边结点)结 点中有另一顶点的下标dest和指针link
A B C D data adj ABCD 0123 dest link dest link 1 3 0 2 10
有向图的邻接表和逆邻接表 A data adi dest link 0A dest link B 1B 2 邻接表(出边表) data adi dest link A 1B 0∧ 2e 逆邻接表(入边表)
ABC data adj ABC 012 dest link dest link data adj ABC 012 dest link 10 2 011