the design and realization of graph manipulation algorithms
本科阶段的毕业设计：基于舞蹈链的图操作算法的设计与实现
简述： 实现了三个算法，其中第一个算法是基于舞蹈链实现的全拓扑排序算法，第二个算法是基于Kruskal算法进行改进的全部最小生成树算法，第三个算法是基于Prim算法进行改进的全部最小生成树算法。 （虽然题目中描述为基于舞蹈链实现，但实际上只有第一个算法是基于舞蹈链的）
第一个算法：基于舞蹈链的全拓扑排序算法
一般地，使用深度优先遍历实现全拓扑排序时会遇到大量的回溯操作，使得算法的运行效率较低，为了解决这一问题，提出了将舞蹈链这一高效回溯的结构应用于深度优先遍历实现全拓扑排序的思路，从而以较高的效率实现全拓扑排序。
过程主要为三步：第一步为初始化，构建舞蹈链矩阵。第二步为迭代过程，基于舞蹈链矩阵进行深度优先遍历。第三步为输出，输出所有的拓扑序列。
第二个算法：改进的Kruskal算法 将边分为权值相等边和权值不等边，在执行Kruskal算法逐步探测边优先数组时面对权值相等边作分叉递归处理，从而找到所有最小生成树。 但是该算法在面对有大量权值相等边的图时，算法的效率会非常低（时间复杂度接近指数级），因此提出了更优的第三个算法。
第三个算法：改进的Prim算法
采取了详细的边分类的思想（将边分为三个状态，状态0的未选边，状态1的固定边，状态2的可选边），而这三种状态的确定依赖于分量扩张过程当中的四种处理情况。
第三个算法的核心思想在于简化图，将整个图划分为多个分量，每个分量的内部的部分最小生成树是确定的，而导致整个图出现多个最小生成树的原因在于这些分量之间的边的组合情况，决定了最终MST的数量。我们通过Prim算法进行分量扩张，再基于状态为1的边来完成分量合并，从而得到简化图，在简化图的基础之上进行改进的Kruskal算法，从而明显地提升算法地效率。（因为显著地减少了需要进行组合判断的边的数量，当然面对非常简单的图时，简化空间比较有限，可能会导致第三个算法效率不如第二个算法的情况出现，但是面对绝大多数图，第三个算法是要显著优于第二个算法的）
该简述部分是我在完成毕业设计很长一段时间之后才写的，而且写的非常匆忙，因此只做了最基本的描述，并且没有检查，所以可能会出现一些错误。