回溯算法(重中之重)
回溯法解决的问题都可以抽象为树形结构，集合的大小就构成了树的广度，递归的深度就构成了树的深度。
(回溯的核心：分清楚什么数据作为广度，什么数据作为深度！！！！！)
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
void backtrack(路径，选择列表){
if(满足结束条件){
result.add(结果);
}
for(选择：选择列表){
做出选择;
backtrack(路径，选择列表);
撤销选择;
}
}组合问题
(N个数里面按一定规则找出k个数的集合)
组合
组合问题中[1,2] 和[2,1] 是同一个，需要去除重复，因此递归需要向后偏移 ( 循环因子+1)
剪枝优化
( 已经选择的元素个数：path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历，因为包括起始位置，我们要是一个左闭的集合。
例如，n = 4，k = 3， 目前已经选取的元素为空（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。起始界限不能大于2，即从2开始搜索都是合理的，可以是组合[2, 3, 4]。)
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // i为本次搜索的起始位置
path.push_back(i); // 处理节点
backtracking(n, k, i + 1);
path.pop_back(); // 回溯，撤销处理的节点
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};组合总和III
剪枝 (已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉)
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (sum > targetSum) { // 剪枝
return;
}
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};电话号码的字母组合
数字和字母如何映射
每一个数字代表的是不同集合，也就是求不同集合之间的组合 (组合求的是同一个集合中的组合！)
取index指向的数字，并找到对应的字符集（手机键盘的字符集）作为广度
输入数字个数 作为深度
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]);
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
};组合总和
关键点： 无限制重复被选取
如果是一个集合来求组合的话，就需要startIndex
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex
(递归的深度因子不用加一！！！！表示可以重复读取当前的数)
在求和问题中，排序之后加剪枝是经典操作！
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
// 如果 sum + candidates[i] > target 就终止遍历
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking(candidates, target, 0, 0);
return result;
}
};组合总和II
(需要考虑去重) 这个题目需要考虑的是广度去重
一般需要对数组排序
直接的思路就是增加一个判断是否使用过的标志位数组
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used); // 和组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};其实index作为循环因子也可以起到去重作用 (考虑到函数的参数一般不超过4个！！！)
在剪枝过程中，i从大于startindex处开始剪
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// 要对同一树层使用过的元素进行跳过
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0);
return result;
}
};切割问题
一个字符串按一定规则有几种切割方式
分割回文串
(需要考虑如何切割，且不能重复选取，递归因子需要+1) (多角度考虑的经典问题)
一般判断回文的思路
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}剪枝优化(融合 动态规划思想) 经典
给定字符串"abcde", 在已知"bcd"不是回文字串时, 不再需要去双指针操作"abcde"而可以直接判定它一定不是回文字串
即 给定一个字符串s, 长度为n, 它成为回文字串的充分必要条件是s[0] == s[n-1]且s[1:n-1]是回文字串
class Solution {
private:
vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
vector<vector<bool>> isPalindrome; // 放事先计算好的是否回文子串的结果
void backtracking (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome[startIndex][i]) { // 是回文子串
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else { // 不是回文，跳过
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程，弹出本次已经添加的子串
}
}
void computePalindrome(const string& s) {
// isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串
isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); // 根据字符串s, 刷新布尔矩阵的大小
for (int i = s.size() - 1; i >= 0; i--) {
// 需要倒序计算, 保证在i行时, i+1行已经计算好了
for (int j = i; j < s.size(); j++) {
if (j == i) {isPalindrome[i][j] = true;}
else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}
else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}
}
}
}
public:
vector<vector<string>> partition(string s) {
computePalindrome(s);
backtracking(s, 0);
return result;
}
};复原IP地址
(经典回溯) 难点在于考虑如何判断子串的有效性，如何确定递归结束的条件，收集结果的检查处理
子串合法性判断
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
采用在原串上修改的策略
class Solution {
private:
vector<string> res;
bool check(string& s, int start, int end){
if(start > end){
return false;
}
if(s[start] == '0' && start != end) return false;
int num = 0;
for(int i = start; i <= end; i++){
num = num * 10 + (s[i] - '0');
if(num > 255) return false;
}
return true;
}
void backtracking(string& s, int index, int node){
if(node == 3){
if(check(s, index, s.size()-1))
res.push_back(s);
return;
}
string tmp;
for(int i = index; i < s.size(); i++){
if(check(s, index, i)){
s.insert(s.begin() + i+1, '.');
node++;
}else
break;
backtracking(s, i + 2, node);
s.erase(s.begin() + i + 1);
node--;
}
}
public:
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return res;
}
};关键点(不合法时break出当前广度循环，或者continue到下一索引位(考虑切割的右界))
子集问题
一个N个数的集合里有多少符合条件的子集
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合
子集
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path); // 收集子集
if (startIndex >= nums.size()) { // 终止条件可以不加
return;
}
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};子集II
需要考虑元素去重 (去重需要先对集合排序！！！！)
去重的方法一般标记数组或哈希集合
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}if (uset.find(nums[i]) != uset.end()) {
continue;
}也可以使用index去重
if(i > index && nums[i] == nums[i-1]) continue;使用标记数组
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
};非递减子序列
需要元素去重(同一父节点下的同层上使用过的元素就不能再使用了)
记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) {
result.push_back(path);
}
int used[201] = {0}; // 这里使用数组来进行去重操作，数值范围[-100, 100]
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back())
|| used[nums[i] + 100] == 1) {
continue;
}
used[nums[i] + 100] = 1; // 记录这个元素在本层用过了，本层后面不能再用了
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};(数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组)
排列问题
N个数按一定规则全排列，有几种排列方式
首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合 (处理排列问题就不用使用Index来约束广度了)
标记数组 (记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次)
全排列
(在叶子节点收获结果，同时考虑不重复使用元素，此时的标记数组也要参与回溯)
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue; // path里已经收录的元素，直接跳过
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};全排列II
(此时需要考虑去重问题了，去重的关键在于需要先排序(方便通过相邻的节点来判断是否重复使用了))
给定一个可包含重复数字的序列，要返回所有不重复的全排列
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};有个细节(如果要对广度中前一位去重，即used[i - 1] == false，如果要对深度前一位去重，即used[i - 1] == true)
对于排列问题，广度上去重和深度上去重，都是可以的，但是广度上去重效率更高！(有点横看成岭侧成峰的韵味)
重新安排行程
难点如下：当有多种解法，字母序靠前排在前面，如何该记录映射关系 ？终止条件是什么？
搜索的过程中，如何遍历一个机场所对应的所有机场，一个行程中，如果航班处理不好容易变成一个圈，成为死循环？
关键点1：出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。
处理过程：可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。
如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了
终止条件：因为只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线
遇到的机场个数，如果达到了（航班数量+1），就将航班收集起来
综上：既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效
unordered_map<string, map<string, int>> targets记录映射关系(方便处理一个起飞地的降落点接着下一个起飞地)
for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}class Solution {
private:
// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
if (result.size() == ticketNum + 1) {
return true;
}
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
if (target.second > 0 ) { // 记录到达机场是否飞过了
result.push_back(target.first);
target.second--;
if (backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
targets.clear();
vector<string> result;
for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
backtracking(tickets.size(), result);
return result;
}
};或者
class Solution {
private:
vector<string> res;
unordered_map<string, map<string,int>> target;
bool backtracking(vector<vector<string>>& tickets, int tickNum){
if(res.size() == tickets.size() + 1)
return true;
for(pair<const string, int>& tmp : target[res.back()]){
if(tmp.second > 0){
res.push_back(tmp.first);
tmp.second--; //控制航班次数
if(backtracking(tickets, tmp.second)) return true;
tmp.second++;
res.pop_back();
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
for(vector<string>& vec : tickets){
target[vec[0]][vec[1]]++;
}
res.push_back("JFK");
backtracking(tickets, 0);
return res;
}
};棋盘问题(经典问题)
回溯解决二维矩阵问题，不同于《重新安排行程》，棋盘问题涉及两维度多方向思考；
核心在于如何抽象出 树的深度和树的广度
N皇后
关键点：处理棋盘的合法性，不能同行，不能同列，不能同斜线 （45度和135度角）
对于同行，在广度遍历的同时顺便检查；最后在树的叶子节点收集结果
判断合法性时需要从回溯搜索的方向去考虑！！！！！(即从已填地方出发)
class Solution {
private:
vector<vector<string>> res;
vector<string> path;
bool check(vector<string>& board, int row, int col,int n){
for(int i = 0; i < row; i++){
if(board[i][col] == 'Q')
return false;
}
for(int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--){
if(board[i][j] == 'Q')
return false;
}
for(int i = row-1, j = col+1; i >=0 && j < n; i--,j++){ //col + 1 防止叠加考虑
if(board[i][j] == 'Q')
return false;
}
return true;
}
void backtracking(vector<string>& board, int row, int n){
if(row == n){
res.push_back(board);
return;
}
for(int col = 0; col < n; col++){
if(check(board, row, col, n)){
board[row][col] = 'Q';
backtracking(board, row+1, n);
board[row][col] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
path.resize(n, string(n, '.'));
backtracking(path, 0, n);
return res;
}
};解数独
不同于n皇后，数独的棋盘可以认为是3*3再嵌套3倍，为了更好地模拟问题，因此需要做二维递归
棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查是否合法，解数独的树形结构要比N皇后更广更深
关键在于：合法性检查，同行是否重复，同列是否重复，9宫格里是否重复
收集唯一解，如何处理终止条件 (可以采用bool返回值，当回溯不满足条件时终止)
9宫格考虑重复需要花点心思(可采用3等分划分)
class Solution {
private:
bool backtracking(vector<vector<char>>& board) {
for (int i = 0; i < board.size(); i++) { // 遍历行
for (int j = 0; j < board[0].size(); j++) { // 遍历列
if (board[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
}
return false; // 9个数都试完了，都不行，那么就返回false
}
}
}
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) { // 判断行里是否重复
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) { // 判断列里是否重复
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};图算法(图论)
无向图中有几条边连接该节点，该节点就有几度
在有向图中，每个节点有出度和入度。出度：从该节点出发的边的个数。入度：指向该节点边的个数。
在图中表示节点的连通情况，称之为连通性，在无向图中，任何两个节点都是可以到达的，称之为连通图；强连通图： 在有向图中任何两个节点是可以相互到达
在无向图中的极大连通子图称之为该图的一个连通分量；在有向图中极大强连通子图称之为该图的强连通分量
主要解决的问题有网格图(考虑横纵坐标的变换关系)、连接图(考虑当前点与连接关系)
图的构造
一般使用邻接表、邻接矩阵 或者用类来表示；主要是邻接表和邻接矩阵
输入如下的图
5 5
1 3
3 5
1 2
2 4
4 5
输出连接关系
1 3 5
1 2 4 5邻接矩阵
邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组
邻接矩阵的优点：
- 表达方式简单，易于理解
- 检查任意两个顶点间是否存在边的操作非常快
- 适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。
缺点：
- 遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径
void dfs (const vector<vector<int>>& graph, int x, int n) {
// 当前遍历的节点x 到达节点n
if (x == n) { // 找到符合条件的一条路径
result.push_back(path);
return;
}
for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
if (graph[x][i] == 1) { // 找到 x链接的节点
path.push_back(i); // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path.pop_back(); // 回溯，撤销本节点
}
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
while (m--) {
cin >> s >> t;
// 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的
graph[s][t] = 1;
}
path.push_back(1); // 无论什么路径已经是从0节点出发
dfs(graph, 1, n); // 开始遍历
// 输出结果
if (result.size() == 0) cout << -1 << endl;
for (const vector<int> &pa : result) {
for (int i = 0; i < pa.size() - 1; i++) {
cout << pa[i] << " ";
}
cout << pa[pa.size() - 1] << endl;
}
}邻接表
邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
有多少边 邻接表才会申请多少个对应的链表节点
邻接表的优点：
- 对于稀疏图的存储，只需要存储边，空间利用率高
- 遍历节点连接情况相对容易
缺点：
- 检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
- 实现相对复杂，不易理解
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径
void dfs (const vector<list<int>>& graph, int x, int n) {
if (x == n) { // 找到符合条件的一条路径
result.push_back(path);
return;
}
for (int i : graph[x]) { // 找到 x指向的节点
path.push_back(i); // 遍历到的节点加入到路径中来
dfs(graph, i, n); // 进入下一层递归
path.pop_back(); // 回溯，撤销本节点
}
}
int main() {
int n, m, s, t;
cin >> n >> m;
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表
while (m--) {
cin >> s >> t;
// 使用邻接表 ，表示 s -> t 是相连的
graph[s].push_back(t);
}
path.push_back(1); // 无论什么路径已经是从0节点出发
dfs(graph, 1, n); // 开始遍历
// 输出结果
if (result.size() == 0) cout << -1 << endl;
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res[i].size()-1; j++){
cout << res[i][j] << " ";
}
cout << res[i][res[i].size() -1];
cout << endl;
}
}图的遍历
图的遍历方式基本是两大类：
- 深度优先搜索（dfs）
- 广度优先搜索（bfs）
深度优先搜索
- 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
- 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本节点所连接的其他节点) {
处理节点;
dfs(图，选择的节点); // 递归
回溯，撤销处理结果
}
}(一般需要二维数组结构保存所有路径，需要一维数组保存单一路径，这种保存结果的数组，可以定义一个全局变量，避免让函数参数过多)
广度优先搜索
适合于解决两个点之间的最短路径问题
关键：需要一个容器，能保存遍历过的元素
用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
从一个点(x,y)向上下左右四个方向进行搜索
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; // 定义队列
que.push({x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
while(!que.empty()) { // 开始遍历队列里的元素
pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
int curx = cur.first;
int cury = cur.second; // 当前节点坐标
for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了，直接跳过
if (!visited[nextx][nexty]) { // 如果节点没被访问过
que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
}
}
}
}网格图的搜索
岛屿数量
深度优先搜索 (该图 为 网格图)
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
void dfs(vector<vector<int>>& graph, vector<vector<bool>>& flag, int cur_x, int cur_y){
if(graph[cur_x][cur_y] == 0 || flag[cur_x][cur_y]) return;
flag[cur_x][cur_y] = true;
for(int i =0; i < 4; i++){
int nxt_x = cur_x + dir[i][0];
int nxt_y = cur_y + dir[i][1];
//判断是否越界
if(nxt_x < 0 || nxt_x >= graph.size() || nxt_y < 0 || nxt_y >= graph[0].size())
continue;
dfs(graph, flag, nxt_x, nxt_y);
}
}
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> graph[i][j];
}
}
vector<vector<bool>> flag(n, vector<bool>(m, false));
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!flag[i][j] && graph[i][j] == 1){
res++;
dfs(graph, flag, i, j);
}
}
}
cout << res << endl;
return 0;
}广度优先搜索 (对于坐标的存储，可以使用 pair 结构)
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
void bfs(vector<vector<int>>& graph, vector<vector<bool>>& flag, int cur_x, int cur_y){
queue<pair<int, int>> que;
que.push({cur_x, cur_y});
flag[cur_x][cur_y] = true; //入队就标记
while(!que.empty()){
pair<int, int> now = que.front(); que.pop();
int now_x = now.first;
int now_y = now.second;
for(int i = 0; i < 4; i++){
int nxt_x = now_x + dir[i][0];
int nxt_y = now_y + dir[i][1];
if(nxt_x < 0 || nxt_x >= graph.size() || nxt_y < 0 || nxt_y >= graph[0].size())
continue;
if(!flag[nxt_x][nxt_y] && graph[nxt_x][nxt_y] == 1){
que.push({nxt_x, nxt_y});
flag[nxt_x][nxt_y] = true; //入队就标记
}
}
}
}岛屿的最大面积
深度优先搜索
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
visited[x][y] = true; // 标记访问过
count++;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
dfs(grid, visited, nextx, nexty);
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
count = 0; // 因为dfs处理当前节点，所以遇到陆地计数为0，进dfs之后在开始从1计数
dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
result = max(result, count);
}
}
}
cout << result << endl;
}广度优先搜索 (对于坐标的存储，也可以使用 pair 结构)
class Solution {
private:
int count;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<int> que;
que.push(x);
que.push(y);
visited[x][y] = true; // 加入队列就意味节点是陆地可到达的点
count++;
while(!que.empty()) {
int xx = que.front();que.pop();
int yy = que.front();que.pop();
for (int i = 0 ;i < 4; i++) {
int nextx = xx + dir[i][0];
int nexty = yy + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界
if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 节点没有被访问过且是陆地
visited[nextx][nexty] = true;
count++;
que.push(nextx);
que.push(nexty);
}
}
}
}
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
count = 0;
bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
result = max(result, count);
}
}
}
return result;
}
};孤岛的总面积
(本质就是找到不靠边的陆地面积，那么只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋，然后再去重新遍历地图 统计此时还剩下的陆地即可。)
深度优先搜索
(思路中，将陆地变成海洋，因此不用刻意使用标记) 深搜在于进入递归函数后即刻处理
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
int count;
void dfs(vector<vector<int>>& grid, int x, int y) {
grid[x][y] = 0;
count++;
for (int i = 0; i < 4; i++) { // 向四个方向遍历
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 超过边界
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
// 不符合条件，不继续遍历
if (grid[nextx][nexty] == 0) continue;
dfs (grid, nextx, nexty);
}
return;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左侧边，和右侧边 向中间遍历
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1) dfs(grid, i, 0);
if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
}
count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) dfs(grid, i, j);
}
}
cout << count << endl;
}广度优先搜索 广搜在于载入队列后即刻处理
void bfs(vector<vector<int>>& grid, int x, int y) {
queue<pair<int, int>> que;
que.push({x, y});
grid[x][y] = 0; // 只要加入队列，立刻标记
count++;
while(!que.empty()) {
pair<int ,int> cur = que.front(); que.pop();
int curx = cur.first;
int cury = cur.second;
for (int i = 0; i < 4; i++) {
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1];
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 越界了，直接跳过
if (grid[nextx][nexty] == 1) {
que.push({nextx, nexty});
count++;
grid[nextx][nexty] = 0; // 只要加入队列立刻标记
}
}
}
}沉没孤岛
思路和孤岛总面积类似 (一般思路：定义一个 标记 二维数组，单独标记周边的陆地，然后遍历地图的时候同时对 地图数组 和 标记数组 进行判断，决定 陆地是否变成水域)
可以不用额外定义空间了，标记周边的陆地，可以直接改陆地为其他特殊值作为标记
处理完孤岛后
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, int x, int y) {
grid[x][y] = 2;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
// 超过边界
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;
// 不符合条件，不继续遍历
if (grid[nextx][nexty] == 0 || grid[nextx][nexty] == 2) continue;
dfs (grid, nextx, nexty);
}
return;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 从左侧边，和右侧边 向中间遍历
for (int i = 0; i < n; i++) {
if (grid[i][0] == 1) dfs(grid, i, 0);
if (grid[i][m - 1] == 1) dfs(grid, i, m - 1);
}
// 从上边和下边 向中间遍历
for (int j = 0; j < m; j++) {
if (grid[0][j] == 1) dfs(grid, 0, j);
if (grid[n - 1][j] == 1) dfs(grid, n - 1, j);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) grid[i][j] = 0;
if (grid[i][j] == 2) grid[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << grid[i][j] << " ";
}
cout << endl;
}
}水流问题
直接模拟可能会超时，采用反证法，假设从边界逆流而上
从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。
同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。
然后两方都标记过的节点就是既可以流边界一也可以流边界二的节点
int n, m;
int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
if (visited[x][y]) return;
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nextx = x + dir[i][0];
int nexty = y + dir[i][1];
if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
if (grid[x][y] > grid[nextx][nexty]) continue; // 注意：这里是从低向高遍历
dfs (grid, visited, nextx, nexty);
}
return;
}
int main() {
cin >> n >> m;
vector<vector<int>> grid(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j];
}
}
// 标记从第一组边界上的节点出发，可以遍历的节点
vector<vector<bool>> firstBorder(n, vector<bool>(m, false));
// 标记从第一组边界上的节点出发，可以遍历的节点
vector<vector<bool>> secondBorder(n, vector<bool>(m, false));
// 从最上和最下行的节点出发，向高处遍历
for (int i = 0; i < n; i++) {
dfs (grid, firstBorder, i, 0); // 遍历最左列，接触第一组边界
dfs (grid, secondBorder, i, m - 1); // 遍历最右列，接触第二组边界
}
// 从最左和最右列的节点出发，向高处遍历
for (int j = 0; j < m; j++) {
dfs (grid, firstBorder, 0, j); // 遍历最上行，接触第一组边界
dfs (grid, secondBorder, n - 1, j); // 遍历最下行，接触第二组边界
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (firstBorder[i][j] && secondBorder[i][j]) cout << i << " " << j << endl;
}
}
}建造最大岛屿
一个暴力想法，是遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。
计算地图的最大面积：遍历地图 + 深搜岛屿，时间复杂度为 n * n。
每改变一个0的方格，都需要重新计算一个地图的最大面积，整体时间复杂度为：n^4。
( 空间换时间 ) 两次遍历地图：
第一遍 使用哈希映射来给岛屿编号和统计面积 unordered_map<int ,int>
第二遍 使用哈希集合来给遍历过的岛屿去重 unordered_set<int> 并判断
int count;
int dir[4][2] = {0,1,1,0, 0,-1,-1,0};
void dfs(vector<vector<int>>& graph, int cur_x, int cur_y, int mark){
if(graph[cur_x][cur_y] == 0 || graph[cur_x][cur_y] == mark) return;
count++;
graph[cur_x][cur_y] = mark;
for(int i = 0; i< 4; i++){
int nxt_x = cur_x + dir[i][0];
int nxt_y = cur_y + dir[i][1];
if(nxt_x < 0 || nxt_x >= graph.size() || nxt_y < 0 || nxt_y >= graph[0].size())
continue;
dfs(graph, nxt_x, nxt_y, mark);
}
}
int main(){
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> graph[i][j];
}
}
unordered_map<int, int> num2size;
vector<vector<bool>> flag(n, vector<bool>(m, false));
int mark = 2;
bool isAllGrid = true;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(graph[i][j] == 0) isAllGrid = false;
if(graph[i][j] == 1){
count = 0;
dfs(graph, i, j, mark);
num2size[graph[i][j]] = count;
mark++;
}
}
}
if(isAllGrid){
cout << n * m << endl;
return 0;
}
unordered_set<int> visited;
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
count = 0;
visited.clear(); // 需要清空
if(graph[i][j] == 0){
count = 1;
for(int k = 0; k < 4; k++){
int nxt_x = i + dir[k][0];
int nxt_y = j + dir[k][1];
if(nxt_x < 0 || nxt_x >= n || nxt_y < 0 || nxt_y >= m)
continue;
if(visited.find(graph[nxt_x][nxt_y]) != visited.end()) continue;
count += num2size[graph[nxt_x][nxt_y]];
visited.insert(graph[nxt_x][nxt_y]);
}
}
res = max(count, res);
}
}
cout << res << endl;
return 0;
}岛屿的周长
惯性思维会去思考dfs或者bfs，但是计算周长，其实可以在遍历地图时统计岛屿周围的水域即可
int solution(vector<vector<int>>& grid)
int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
int result = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == 1) {
for (int k = 0; k < 4; k++) { // 上下左右四个方向
int x = i + direction[k][0];
int y = j + direction[k][1]; // 计算周边坐标x,y
if (x < 0 // x在边界上
|| x >= grid.size() // x在边界上
|| y < 0 // y在边界上
|| y >= grid[0].size() // y在边界上
|| grid[x][y] == 0) { // x,y位置是水域
result++;
}
}
}
}
}
return res;
}也可以统计岛屿数量，有一对相邻两个的岛屿，边的总数就要减2
result = 岛屿数量 * 4 - cover * 2
int solution(vector<vector<int>>& graph){
int sum = 0;
int cover = 0;
for(int i =0; i < graph.size(); i++){
for(int j = 0; j < graph[0].size(); j++){
if(graph[i][j] == 1){
sum++;
if(i-1 >= 0 && graph[i-1][j] == 1) cover++;
if(j-1 >= 0 && graph[i][j-1] == 1) cover++;
}
}// 为什么没统计下边和右边？ 因为避免重复计算
}
return sum * 4 - cover * 2;
}连接图的搜索
字符串接龙
抽象成一个无向图(连接图) 求起点和终点的最短路径长度
无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径
unordered_set 可以用来收集路径和去重以及用find方法来快速查询
unordered_map用来记录当前所到字符串，及连通长度
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
void bfs(unordered_set<string>& hash_set, string& startstr, string& endstr){
queue<string> que;
que.push(startstr);
unordered_map<string, int> visit_map;
visit_map.insert(pair<string, int>(startstr, 1)); // 构造当前连通长度
while(!que.empty()){
string word = que.front(); que.pop();
int len = visit_map[word];
for(int i = 0; i < word.size(); i++){
string newword = word;
for(int j = 0; j < 26; j++){
newword[i] = 'a' + j;
if(newword == endstr){
cout << len + 1 << endl;
return ;
}
if(hash_set.find(newword) != hash_set.end() &&
visit_map.find(newword) == visit_map.end()){
visit_map.insert(pair<string, int>(newword, len + 1)); //当前长度+1
que.push(newword);
}
}
}
}
cout << 0 << endl;
}
int main(){
int n;
cin >> n;
string startstr, endstr;
cin >> startstr >> endstr;
unordered_set<string> hash_set;
for(int i =0; i < n; i++){
string tmp;
cin >> tmp;
hash_set.insert(tmp);
}
bfs(hash_set, startstr, endstr);
return 0;
}有向图的完全可达性
有向图推荐使用邻接表存储, 有向图可以不依赖4个方向去搜索，根据连接的边搜索
有向图搜索全路径的问题
深度优先搜索
(区别于之前网格图的搜索， 此时递归的是当前的节点)
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {
if (visited[key]) return;
visited[key] = true;
list<int> keys = graph[key];
for (int key : keys)
dfs(graph, key, visited);
}
int main() {
int n, m, s, t;
cin >> n >> m;
// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表
while (m--) {
cin >> s >> t;
// 使用邻接表 ，表示 s -> t 是相连的
graph[s].push_back(t);
}
vector<bool> visited(n + 1, false);
dfs(graph, 1, visited);
//检查是否都访问到了
for (int i = 1; i <= n; i++) {
if (visited[i] == false) {
cout << -1 << endl;
return 0;
}
}
cout << 1 << endl;
}广度优先搜索
void bfs(vector<list<int>>& graph, vector<bool>& flag, int startnode){
queue<int> que;
que.push(startnode);
flag[startnode] = true;
while(!que.empty()){
int curnode = que.front(); que.pop();
list<int> nodes = graph[curnode]; //取出一条链表
for(int tmp : nodes){
if(!flag[tmp]){
que.push(tmp);
flag[tmp] = true;
}
}
}
}