图论做题笔记：bfs-Toy模板网

这篇具有很好参考价值的文章主要介绍了图论做题笔记：bfs。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Leetcode - 433:最小基因变化

题目：

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

笔记：

这道题是真抽象，对字符串进行bfs，这里的思路是：直接对字符串去处理不要讲单个字符单独处理。首先建立一个处理队列，将start加入其中，此时队列中的元素表示未处理的元素，接下来记录当前层的大小，遍历当前层的元素（只有start一个），接着对字符串进行处理，这里我们创建一个数组来存储字符可变化的样子（也就是方向数组），从当前处理的字符串的头开始向后遍历，一一替换当前遍历到的位置，如果替换后的字符串可以在bank中找到并且没有被访问过我们就将其加入que的第二层，在遍历完当前层元素后step++代表变换元素的次数。

注意：

（1）当我们向队列加入一个元素后，立即将其标记为已访问。

（2）将vector类型的bank数组改为set数组更好处理：

在一个set数组中查找元素是否存在：set.count(目标）文章来源地址https://www.toymoban.com/news/detail-845681.html

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> visited;
        unordered_set<string> bank_set(bank.begin(), bank.end());
        char keys[4] = {'A', 'C', 'G', 'T'};
        int step = 0;
        queue<string> que;
        que.push(startGene);
        visited.insert(startGene);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; i++){
                string cur = que.front();
                que.pop();
                if(cur == endGene){
                    return step;
                }
                for(int j = 0; j < cur.size(); j++){
                    for(int k = 0; k < 4; k++){
                        string next = cur;
                        next[j] = keys[k];
                        if(bank_set.count(next) && !visited.count(next)){
                            que.push(next);
                            visited.insert(next);
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }
};

到了这里，关于图论做题笔记：bfs的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！