《常用组合算法程序汇编》

第一章枚举计数1

1.1生成所有子集（NEXSUB/LEXSUB）1

1.2生成所有K-子集（NEXKSB/NXKSRD）9

1.3生成整数的所有有序K-划分（NEXCOM）16

1.4生成整数的所有无序划分（NEXPAR）20

1.5生成集合的所有划分（NEXEQU）26

1.6生成所有排列（NEXPER）32

1.7排列的轮换结构（CYCLES）38

第二章随机抽样及组合变换45

2.1随机生成子集（RANSUB）46

2.2随机生成K-子集（RANKSB）49

2.3随机生成整数的有序k-划分（RANCOM）55

2.4随机生成整数的无序划分（RANPAR）56

2.5随机生成集合的划分（RANEQU）62

2.6随机生成排列（RANPER）67

2.7矩阵行列的重新编号（RENUMB）70

2.8偏序集的三角编号（TRIANG）75

2.9麦比乌斯函数（MOBIUS）80

第三章图86

3.1广度优先搜索（BREADTH—FIRST—SEARCH）86

3.2深度优先搜索（DEPTH—FIRST—SEARCH）94

3.3求基本割集矩阵（CUTSET）101

3.4求有向图中强连通分量（STRONC）107

3.5求有向图的递归点（RECURS）113

3.6求基本回路矩阵（LFORM）117

3.7求平面图的网孔矩阵（MM）126

3.8求一条Hamilton回路（HAMILTON）129

3.9求不带权二分图的最大匹配与带权二分图的最佳匹配（MOOMAT）141

3.10求图的着色多项式（CHROMP）156

3.11规划评审技术（PERT）166

第四章最短路174

4.1最短路径的Di jkstra算法（DIJKSTRA—ALGORITHM）174

4.2最短路径的双扫描算法（DOUBLE—SWEEP）181

4.3带负权有向图的最短路（SPOFNW ）190

4.4求两点间最短路径（DXTRA1）＆一点到其余各点的最短路径（DXTRA2）198

4.5每一对结点之间的最短路径（MULTITERMITNAL—SHORTEST—PATHS）205

4.6顶点对之间最短路的FLOYD算法（FLOYDS）213

4.7最长路径（LONGEST—PATHS）218

第五章树225

5.1哈夫曼树（ HUFFMAN TREE）225

5.2最优字母树的HU—TUCKER算法（HU—TUCKER）232

5.3最优字母树的CARSIC—WACHS算法（CARSIC—WACHS）249

5.4随机生成无标号有根树（RANRUT）259

5.5求无向图的一棵生成树（TREE）264

5.6求有向图的生成树（DIRTRE）271

5.7求最小生成树（MINSPT）275

5.8最小生成树的PRIMS方法（PRIMS—MIN—SPANNING—TREE）279

第六章网络的最大流287

6.1最大流的Ford—Fulkerson算法（FORD—FULKERSON—MAX—FLOW）289

6.2最大流的DINIC算法（DINIC—MAX—FLOW ）301

6.3最大流的Karzanov算法（NETFLO）314

6.4 网络的最优费用最大流（MICMAF）335

第七章动态规划346

7.1多阶段网络中的最短路（MULTI—STAGE—NETWORK）347

7.2资源分配问题（RESOURCE—ALLOCATION）356

7.3背包问题（KNAPSACK）365

7.4背包问题的周期解法PERIODIC—SOLUTION FOR KNAPSAK）372

7.5最优字母树的动态规划算法（OPTIMUM—ALPHABETIC—TREE）382

第八章回溯法391

8.1回溯子程序（ BACKTR）391

8.2求所有生成树（SPNTRE）396

8.3求图中所有Euler回路（EU LCRC）406

8.4求图中所有Hamilton回路（HAMCRC）417

8.5求图的所有适当着色（COLVRT）423

8.6八皇后问题（EIGHT—QUEENS）430

8.7背包问题的分枝一限界法（BRANCH—BOUND）439

第九章启发式算法445

9.1换零钱问题（COIN—CHANGING）445

9.2装箱问题（FIRST—FIT）452

9.3凸多边形的最优划分（HURISTIC—ALGORITHM）458