题目：
若初始序列为gbfcdae，那么至少需要多少次两两交换，才能使该序列变为abcdefg ？任给一个自由a--g这7个字母组成的排列，最坏的情况下需要至少多少次两两交换，才能使序列变为abcdefg ？
分析一：字母交换问题
字母可以任意交换，最坏情况是每个字符都需要交换一次来达到最终位置，
最后一次交换使的两个字符同时到达最终位置。N个字符最坏情况需要至少N-1次交换，
gbfcdae中b已经在自己的位置上又少了一次，所以5次。
分析二：图论的拓扑排序
拓扑排序定义：简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓 扑序列(Topological order)。
由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。
有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。
拓扑排序是对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
