f(vll=-1&&v2!=-1) return Edgelv1lv2]; else return o template <class Name'Type, class DistType> int Graph<Name Type, DistType>:: GetFirstNeighbor( const int v)t )给出顶点攸置为ν的第一个邻接顶点的位置 if(v!=-1){ for( int col-0; col< CurrentEdges; col++) if( eage[rowl[col>0)return col; return -1
if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2]; else return 0; } template <class NameType, class DistType> int Graph<NameType, DistType>:: GetFirstNeighbor ( const int v ) { //给出顶点位置为 v 的第一个邻接顶点的位置 if ( v != -1 ) { for ( int col = 0; col < CurrentEdges; col++ ) if ( Edge[row][col] > 0 ) return col; } return -1; }
template <class Name Type, class DistType> int Graph<NameType, DistType> GetNextNeighbor( const int vl, const int v2)t 给出顶点叭的某郐接顶点的下一个邻接顶点 if(v1l=-1&&v2l=-1){ for( int col=v2+l; col< CurrentEdges; col++) if Edgell]col>0)return col return -1
template <class NameType, class DistType> int Graph<NameType, DistType>:: GetNextNeighbor ( const int v1, const int v2 ) { //给出顶点v1的某邻接顶点v2的下一个邻接顶点 if ( v1 != -1 && v2 != -1 ) { for ( int col = v2+1; col < CurrentEdges; col++ ) if ( Edge[v1][col] > 0 ) return col; } return -1; }
邻接表( Adjacency List) 无向图的邻接表 data adi dest link dest link 0A B 123 BCD 2001 3∧ G8 Nodef'able Edge linked list 把同一个顶点发出的边链接在同一个边链表中, 链表的每一个结点代表一条边,叫做边结点, 结点中保存有与该边相关联的另一顶点的顶点 下标dest和指向同一链表中下一个边结点的指 针link
有向图的邻接表和逆邻接表 data adj dest link dest link data adj dest link A 1A 0A BCD 2∧ B 3∧ ∧ dest link 4∧ 3|D 2∧ 0∧ 3∧ nodef'able出边表 nodefT'able入边表 (a)邻接表 b)逆邻接表 在有向图的邻接表中,第i个边链表链接的边 都是顶点i发出的边。也叫做出边表 在有向图的逆邻接表中,第i个边链表链接的 边都是进入顶点i的边。也叫做入边表
带权图的边结点中保存该边上的权值 cost 顶点i的边链表的表头指针ad在顶点表的下 标为i的顶点记录中,该记录还保存了该顶点 的其它信息。 在邻接表的边链表中,各个边结点的链入顺序 任意,视边结点输入次序而定。 设图中有n个顶点,e条边,则用邻接表表示 无向图时,需要n个顶点结点,2e个边结点; 用邻接表表示有向图时,若不考虑逆邻接表, 只需n个顶点结点,e个边结点