今天向大家介绍另一个图的宽度优先遍历示例-最小基因变化，具体题目的内容请见引文1。这里描述一下问题的分析思路，并给出一个实现仅供参考，期待能看到更多更优秀的代码实现，从中学习以不断进步。
首先我们可以将每一个基因建模为一个图节点，如果两个节点之间只有一个基因变化，则可以认为两个节点相邻，距离为1。距离大于1的两个节点可以不考虑其距离特性（默认为-1，表示为不直接相连）。关于图的表示问题，这里可以用矩阵进行表示，而且由于对称性，我们可以只利用上矩阵来进行图的搜索。
关于起始节点，如果在gene bank里边，则以起始节点开始进行图的宽度优先搜索，如果不再gene bank里边，则需要从gene bank里边去寻找与该节点的距离为1的所有节点作为候选起始节点，然后对所有可能的起始节点，依次调用图的宽度优先遍历搜索找到最短路径。因为每次都只改变一个基因，而且从起始节点到目标节点的距离已经定下来了（按顺序计算不同字母的个数），因此如果找到，我们可以从目标节点逆序看过来，就知道这个最小路径数就是距离（当然要通过搜索才能找到这样的路径），比如起始点和终点的距离为2，有可能搜索的时候，第一个后继节点和第二个后继节点与起始节点的距离都为1，但是第一个后继节点可能与重点的距离为3（又加了一个不同的基因），因此在最短路径搜索的时候会选择基于第二个后继节点。基于此我们可以得出结论，要么没有路径（返回-1），要么就等于起始节点和目标节点的不同基因数（也可能有多个路径，只要有一个路径找到即可返回，基于这点可以对搜索进行优化）。
具体实现代码可以参看引文2，欢迎读者提出优化建议，由于撰写匆忙加以思考过程可能不够全面深入，以及针对上述的问题分析中有任何问题也欢迎提出意见建议。
References
Leave a Reply