企业官网建设流程全解析

BFS是一种遍历或搜索树或图的算法。其基本思想是从某一起始点出发，探索所有之前没被探索过的邻居节点，层层推进，直到遍历所有。

下图是对BFS的理解：

现在来一道题：洛谷P1032[NOIP2002提高组] 字串变换

解题思路：要求得到最小的变换步数或者no answer，在变换法则数目一定（记为x）的情况下 ，每一步都要尝试这x种可能，而且它要我们得出最少步数（即最优解），这让我们容易想到BFS,因为BFS是一层层遍历下去的，所以第一个找到的满足条件的解一定是最优解。

而BFS的代码实现，就是我们建立一个队列来存储中心点集（中心点集：本文的一种说法，即需要从其遍历邻居节点的点集合。起始中心点集当然只有初始状态了），然后从队列中取头部元素，开始找到邻居顶点，将其并入中心点集尾部，当该元素邻居遍历完了，将该元素踢出队列。而本题要注意所处的层次（即第几步），这只需要一个标记变量，我们知道：当某一步最后一种情况被遍历后，队列里所有的元素就都是走过相同步数而达到的了。具体实现看下方代码：

#include <iostream> #include <deque> #include <string> using namespace std; deque<string>dq; int getmin(string from, string to, string from2[], string to2[], int k); int main() { string from, to; string from2[6]; string to2[6]; cin >> from >> to; dq.push_back(from); int k = 0; while (cin>>from2[k]>>to2[k]) { k++; } int gh = getmin(from, to, from2, to2, k); if (gh) cout << gh; else cout << "NO ANSWER!"; return 0; } int getmin(string from,string to,string from2[],string to2[], int k) { int sign = 1; int sb = 0; string str2="12345671234567123456"; int flag = 1; while (sign <= 10) { string str = dq.front(); int num = str.size(); for (int i = 0; i < k; i++) { int num1 = from2[i].size(); for (int j = 0; j < num - num1+1; j++) { if (str.substr(j, num1) == from2[i]) { str2 = str.substr(0, j); str2.append(to2[i]); str2.append(str.substr(j + num1 )); if (str2 == to)return sign; dq.push_back(str2); } } } dq.pop_front(); flag--; if (!flag) { sign++; flag = dq.size(); } } return 0; }