有关图的题目
1.深度优先搜索理论
dfs 与 bfs 区别
1.dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 2.bfs是先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。
代码框架
图的深度优先搜索类似树的前序遍历
图的广度优先搜索类似树的层序遍历
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本节点所连接的其他节点) {
处理节点;
dfs(图,选择的节点); // 递归
回溯,撤销处理结果
}
}
深搜三部曲
确认递归函数,参数
void dfs(参数)
通常我们递归的时候,我们递归搜索需要了解哪些参数,其实也可以在写递归函数的时候,发现需要什么参数,再去补充就可以。
一般情况,深搜需要 二维数组数组结构保存所有路径,需要一维数组保存单一路径,这种保存结果的数组,我们可以定义一个全局遍历,避免让我们的函数参数过多。
vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图,目前搜索的节点)
2.确认终止条件
if (终止条件) {
存放结果;
return;
}
终止添加不仅是结束本层递归,同时也是我们收获结果的时候。
3.处理目前搜索节点出发的路径
一般这里就是一个for循环的操作,去遍历 目前搜索节点 所能到的所有节点。
for (选择:本节点所连接的其他节点) {
处理节点;
dfs(图,选择的节点); // 递归
回溯,撤销处理结果
}
例题:
797. 所有可能的路径
class Solution {
vector<vector<int>> all_path;
vector<int> path;
void search(vector<vector<int>>& graph,int point)
{
path.push_back(point); //进入先放进去
if (point == graph.size() -1 )//达到 n -1 收集结果
{
all_path.push_back(path);
}
for (int i = 0; i < graph[point].size(); ++i) {
search(graph, graph[point][i]);
path.pop_back();//回溯
}
}
public:
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
search(graph,0);
return all_path;
}
};
547. 省份数量
class Solution {
int sum = 0;
vector<bool> isVis;
void backtracking(vector<vector<int>>& isConnected ,int i)
{
if(isVis[i]) return;
isVis[i] = true;
for (int j = 0; j < isConnected[i].size(); ++j) {
if(isConnected[i][j]) backtracking( isConnected , j);
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
isVis.assign(isConnected.size(),false);
backtracking(isConnected,0);
sum++;
for (int i = 0; i < isConnected.size(); ++i) {
if (!isVis[i])
{
backtracking( isConnected , i);
sum++;
}
}
return sum;
}
};
2.广度优先搜索
使用队列,无向图的最短路径问题,也可以使用广度优先搜索。
经典例题:
127. 单词接龙
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// 将vector转成unordered_set,提高查询速度
unordered_set<string> wordSet(wordList.begin(),wordList.end());
// 如果endWord没有在wordSet出现,直接返回0
if (wordSet.find(endWord) == wordSet.end()) return 0;
// 记录word是否访问过
unordered_map<string,int> Map;// <word, 查询到这个word路径长度>
// 初始化队列
queue<string> que;
// 初始化visitMap
que.push(beginWord);
Map.insert(pair(beginWord,1));
while (!que.empty())
{
string word = que.front();
que.pop();
int path = Map[word];//记录当前长度
for (int i = 0; i < word.size(); ++i) {
string newword = word;
for (int j = 0; j < 26; ++j) {
newword[i] = j + 'a';
if (newword == endWord) return path+1;
// wordSet出现了newWord,并且newWord没有被访问过
if (wordSet.find(newword)!=wordSet.end() &&
Map.find(newword)==Map.end())
{
Map.insert(pair(newword,path+1));
que.push(newword);
}
}
}
}
return 0;
}
};
934. 最短的桥
class Solution {
bool is_find = false;
//感染函数,把所有 1 变为2
void ganran(vector<vector<int>>& grid ,int i , int j ,int num)
{
if (i < 0 || j < 0 || i >= grid.size() || j >= grid.size()) return;
if (grid[i][j] != 1) return;
grid[i][j] = num;
ganran(grid , i + 1, j,num);
ganran(grid , i - 1, j,num);
ganran(grid , i , j- 1,num);
ganran(grid , i , j + 1,num);
}
//扩建函数
void kuojian(vector<vector<int>>& grid ,int num)
{
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid.size(); ++j) {
if (grid[i][j] == num - 1)
{
if(i > 0 && grid[i - 1][j] == 1||j > 0 && grid[i][j - 1] == 1||i < grid.size() - 1 && grid[i + 1][j] == 1||j < grid.size() - 1 && grid[i][j + 1] == 1)
{
is_find = true;
return;
}
if (i > 0 && grid[i - 1][j] == 0)grid[i - 1][j] = num;
if (j > 0 && grid[i][j - 1] == 0)grid[i][j - 1] = num;
if (i < grid.size() - 1 && grid[i + 1][j] == 0)grid[i + 1][j] = num;
if (j < grid.size() - 1 && grid[i][j + 1] == 0)grid[i][j + 1] = num;
}
}
}
}
public:
int shortestBridge(vector<vector<int>>& grid) {
//先找到一处为1的点 i j
bool find = false ;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid.size(); ++j) {
if(grid[i][j] == 1)
{
//随便标记一处岛屿 2
ganran(grid,i,j,2);
find = true;
break;
}
}
if (find) break;
}
//将岛屿向外面扩展 , 每次扩展 + 1操作 ,如果遇到 1 ,那么扩展的次数就为桥梁的数
int count = 0;
while (!is_find)
{
kuojian( grid , count + 3);
count++;
}
return count - 1;
}
};
130. 被围绕的区域
class Solution {
void ganran(vector<vector<bool>>& grid ,vector<vector<char>>& board,int i , int j )
{
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return;
if (grid[i][j] == true || board[i][j] != 'O') return;
grid[i][j] = true;
ganran(grid ,board, i + 1, j);
ganran(grid ,board, i - 1, j);
ganran(grid , board,i , j- 1);
ganran(grid , board,i , j + 1);
}
public:
void solve(vector<vector<char>>& board) {
//标记外城的‘O'
vector<vector<bool>> ischoosed(board.size(),vector<bool>(board[0].size(), false));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == 'O' && (i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1))
{
ganran(ischoosed ,board, i , j );
}
}
}
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[0].size(); ++j) {
if (board[i][j] == 'O' && ischoosed[i][j] == false)
{
board[i][j] = 'X';
}
}
}
}
};
3.并查集
547. 省份数量
//方法一 并查集
class Solution {
int father[202] = {0};
void init()
{
for (int i = 0; i < 202; ++i) {
father[i] = i;
}
}
int find(int n)
{
return father[n] == n ? n : father[n] = find(father[n]);
}
void unions(int a ,int b)
{
int fa = find(a);
int fb = find(b);
if (fa == fb) return;
father[fa] = fb;
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
init();
unordered_set<int> uset;
for (int i = 0; i < isConnected.size(); ++i) {
for (int j = i; j < isConnected[i].size(); ++j) {
if (isConnected[i][j] == 1)
{
unions(i ,j);
}
}
}
for (int i = 0; i < isConnected.size(); ++i) {
uset.insert(find(i));
}
return uset.size();
}
};
684. 冗余连接
题目说是无向图,返回一条可以删去的边,使得结果图是一个有着N个节点的树。
如果有多个答案,则返回二维数组中最后出现的边。
那么我们就可以从前向后遍历每一条边,边的两个节点如果不在同一个集合,就加入集合(即:同一个根节点)。
如果边的两个节点已经出现在同一个集合里,说明着边的两个节点已经连在一起了,如果再加入这条边一定就出现环了。
class Solution {
const static int MAX_SIZE = 1005;
int father[MAX_SIZE];
//初始化并查集
void init()
{
for (int i = 0; i < MAX_SIZE; ++i) {
father[i] = i;
}
}
//合并
void unions(int x , int y)
{
int x_f = find(x);
int y_f = find(y);
if(x_f == y_f) return;
father[x_f] = y_f;
}
//找到祖先+路径压缩
int find(int x)
{
if (x == father[x]) return x;
father[x] = find(father[x]);
return father[x];
}
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
init();
unions(edges[0][0] , edges[0][1]);
for (int i = 1; i < edges.size(); ++i) {
if (find(edges[i][0]) == find(edges[i][1])) return edges[i];
unions(edges[i][0] , edges[i][1]);
}
return {};
}
};
4.拓扑排序
拓扑排序(topological sort)是一种常见的,对有向无环图排序的算法。给定有向无环图中的 N 个节点,我们把它们排序成一个线性序列;若原图中节点 i 指向节点 j,则排序结果中 i 一定在 j 之前。拓扑排序的结果不是唯一的,只要满足以上条件即可。
我们可以先建立一个邻接矩阵表示图,方便进行直接查找。这里注意我们将所有的边反向, 使得如果课程 i 指向课程 j,那么课程 i 需要在课程 j 前面先修完。这样更符合我们的直观理解。 拓扑排序也可以被看成是广度优先搜索的一种情况:我们先遍历一遍所有节点,把入度为 0 的节点(即没有前置课程要求)放在队列中。在每次从队列中获得节点时,我们将该节点放在目 前排序的末尾,并且把它指向的课程的入度各减 1;如果在这个过程中有课程的所有前置必修课 都已修完(即入度为 0),我们把这个节点加入队列中。当队列的节点都被处理完时,说明所有的 节点都已排好序,或因图中存在循环而无法上完所有课程。
210. 课程表 II
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses,vector<int>()); //定义图的邻接矩阵,行为 1 列为0 ,表示先修 - 》 后修
vector<int> indegree(numCourses,0),res; // 定义入度矩阵
for (const auto & prerequisite:prerequisites) {
graph[prerequisite[1]].push_back(prerequisite[0]); //零阶矩阵 对应 如[0,1] 就是 1-> 0,1为先修课程
indegree[prerequisite[0]]++; //入度加一
}
//定义队列 , 若队列有入度为0的则加入队列
queue<int> que;
for (int i = 0; i < indegree.size(); ++i) {
if (!indegree[i]) que.push(i);
}
//对队列取出元素,相应的元素对应的度都减一,如果度为0则加入队列
while (!que.empty())
{
int top = que.front();
res.push_back(top);
que.pop();
for (int x:graph[top]) {
indegree[x]--;
if (!indegree[x]) que.push(x);
}
}
//最后遍历indegree入度表,如果存在大于一的说明不能完成
for (auto x: indegree) {
if (x) return {};
}
return res;
}
};