0001 template <typename Tv, typename Te> template <typename PU> //优先级搜索(全图) 0002 void Graph<Tv, Te>::pfs ( int s, PU prioUpdater ) { //assert: 0 <= s < n 0003 reset(); int v = s; //初始化 0004 do //逐一检查所有顶点 0005 if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点 0006 PFS ( v, prioUpdater ); //即从该顶点出发启动一次PFS 0007 while ( s != ( v = ( ++v % n ) ) ); //按序号检查,故不漏不重 0008 } 0009 0010 template <typename Tv, typename Te> template <typename PU> //顶点类型、边类型、优先级更新器 0011 void Graph<Tv, Te>::PFS ( int s, PU prioUpdater ) { //优先级搜索(单个连通域) 0012 priority ( s ) = 0; status ( s ) = VISITED; parent ( s ) = -1; //初始化,起点s加至PFS树中 0013 while ( 1 ) { //将下一顶点和边加至PFS树中 0014 for ( int w = firstNbr ( s ); -1 < w; w = nextNbr ( s, w ) ) //枚举s的所有邻居w 0015 prioUpdater ( this, s, w ); //更新顶点w的优先级及其父顶点 0016 for ( int shortest = INT_MAX, w = 0; w < n; w++ ) 0017 if ( UNDISCOVERED == status ( w ) ) //从尚未加入遍历树的顶点中 0018 if ( shortest > priority ( w ) ) //选出下一个 0019 { shortest = priority ( w ); s = w; } //优先级最高的顶点s 0020 if ( VISITED == status ( s ) ) break; //直至所有顶点均已加入 0021 status ( s ) = VISITED; type ( parent ( s ), s ) = TREE; //将s及与其父的联边加入遍历树 0022 } 0023 } //通过定义具体的优先级更新策略prioUpdater,即可实现不同的算法功能