图论算法笔记|04图论建模和Floodfill
1. 图论建模
大多数的时候我们遇到的问题都不会直接说明这是一个图论的问题，然后你需要使用什么方法来解决。大多数的时候是需要我们自己对问题进行抽象，然后将问题建模成一个图论的问题，然后求解。图论的问题求解过程绝大多数还是使用的dfs或者是bfs。不同的是对于不同的问题，我们需要在遍历的过程中记录我们需要的信息。这一篇中通过解决一些LeetCode上的问题来体会图论建模。
首先来看一个简单的题目，这个问题中我们不需要对问题进行建模。LeetCode785, 给一个无向图，判断是否是二分图。我们使用bfs来进行求解，当然对于这个问题，我们也可以使用dfs进行求解。这个问题在前面两篇中都讲解过。
给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
class Solution {
public:
vector<bool> visited;
vector<int> color;
bool bfs(vector<vector<int>>& graph, int s, int c){
queue<int> q;
q.push(s);
visited[s] = true;
color[s] = c;
while(!q.empty()){
int v = q.front();
q.pop();
for(auto w : graph[v])
{
if(!visited[w]){
q.push(w);
visited[w] = true;
color[w] = 1 - color[v];
}
else if(color[w] == color[v])
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
visited = vector<bool>(graph.size(), false);
color = vector<int>(graph.size(), -1);
for(size_t i=0;i<graph.size();++i)
{
if(!visited[i])
if(bfs(graph, i, 0) == false)
return false;
}
return true;
}
};
2. Floodfill
leetcode 695 岛屿的最大面积
func maxAreaOfIsland(grid [][]int) (area int) {
var dfs func(i, j int) int
if len(grid) <= 0{
return 0
}
MaxI, MaxJ := len(grid), len(grid[0])
dfs = func(i, j int) int {
if i < 0 || i > MaxI-1 || j < 0 || j > MaxJ-1 {
return 0
}
v := grid[i][j]
if v != 1 {
return 0
}
grid[i][j] = -1
return 1 + dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
}
for i := 0; i < MaxI; i++ {
for j := 0; j < MaxJ; j++ {
if grid[i][j] == 1 {
tmp := dfs(i, j)
if tmp > area {
area = tmp
}
}
}
}
return area
}
3. Floodfill的应用
leetcode #200 岛屿数量
func numIslands(grid [][] byte)int{
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
dir := [][]int{{-1,0},{1, 0}, {0, -1}, {0, 1}}
MaxI, MaxJ := len(grid), len(grid[0])
res := 0
var dfs func(i, j int)
dfs = func(i, j int){
if i < 0 || i > MaxI - 1 || j < 0 || j > MaxJ-1 {
return
}
if grid[i][j] != 1{
return
}
grid[i][j] = 0
for k:=0;k<len(dir);k++ {
dfs(i+dir[k][0], j+dir[k][1])
}
}
for i:=0;i<MaxI;i++{
for j:=0;j<MaxJ;j++ {
if grid[i][j] == 1 {
dfs(i, j)
res ++
}
}
}
return res
}
leetcode #1020 飞地的数量
func numEnclaves(A [][]int) int {
if len(A) == 0 || len(A[0]) == 0 {
return 0
}
MaxI, MaxJ := len(A), len(A[0])
var dfs func(i, j int)
dfs = func(i, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
if i < 0 || j < 0 || i > MaxI-1 || j > MaxJ-1 {
return
}
if A[i][j] == 0 {
return
}
A[i][j] = 0
for k := 0; k < len(dir); k++ {
dfs(i+dir[k][0], j+dir[k][1])
}
}
// 对边界上的点进行深度优先遍历，将其都写成0，剩下的1就是不能到达边界的了
for i := 0; i < MaxI; i++ {
for j := 0; j < MaxJ; j++ {
isEdge := (i == 0) || (j == 0) || (i == MaxI-1) || (j == MaxJ-1)
if isEdge && A[i][j] == 1 {
dfs(i, j)
}
}
}
//统计剩下1的数量
res := 0
for i := 0; i < MaxI; i++ {
for j := 0; j < MaxJ; j++ {
if A[i][j] == 1 {
res++
}
}
}
return res
}
leetcode #130 被围绕的区域
func solve(board [][]byte){
if len(board) < 3 || len(board[0]) < 3{
return
}
m, n := len(board), len(board[0])
var dfs func(i, j int)
dfs = func(i, j int) {
dir := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
if i < 0 || j < 0 || i > m-1 || j > n-1 {
return
}
if board[i][j] == 'X' || board[i][j] == '$' {
return
}
board[i][j] = '$'
for k := 0; k < len(dir); k++ {
dfs(i+dir[k][0], j+dir[k][1])
}
}
for i:=0;i<m;i++ {
for j:=0;j<n;j++ {
isEdge := (i == 0) || (j == 0) || (i == m-1) || (j == n-1)
if isEdge && board[i][j] == 'O' {
dfs(i, j)
}
}
}
for i:=0;i<m;i++ {
for j:=0;j<n;j++ {
if board[i][j] == '$'{
board[i][j] = 'O'
} else if board[i][j] == 'O'{
board[i][j] = 'X'
}
}
}
}
leetcode #733 图像渲染
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
m, n := len(image), len(image[0])
srcColor := image[sr][sc]
var dfs func(i,j int)
dfs = func(i, j int) {
if i<0||i>m-1||j<0||j>n-1{
return
}
if image[i][j] != srcColor || image[i][j] == newColor{
return
}
image[i][j] = newColor
dfs(i-1,j)
dfs(i+1,j)
dfs(i,j-1)
dfs(i,j+1)
}
dfs(sr,sc)
return image
}
leetcode #1034 边框着色
func colorBorder(grid [][]int, r0 int, c0 int, color int) [][]int {
m, n := len(grid), len(grid[0])
visited := make([]bool, m*n)
srcColor := grid[r0][c0]
var dfs func(i, j int) int
dfs = func(i, j int) int {
// 返回值: 0表示这个点不属于这个联通分量
if i < 0 || i > m-1 || j < 0 || j > n-1 {
return 0
}
// 因为后面修改了点的颜色属性，所以先要进行visited判断，如果遍历过，那么肯定属于这个连通分量的
if visited[i*n+j] == true {
return 1
}
//没有被遍历过，而且颜色和点击点不同，那么不属于这个连通分量
if grid[i][j] != srcColor {
return 0
}
visited[i*n+j] = true
res := dfs(i-1, j) + dfs(i+1, j) + dfs(i, j-1) + dfs(i, j+1)
if res < 4 {
grid[i][j] = color
}
return 1
}
dfs(r0, c0)
return grid
}
leetcode #529
leetcode #827
func largestIsland(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(x, y, cc int) int
area := make(map[int]int, m*n)
visited := make([]int, m*n)
dir := [][]int{{-1,0}, {1, 0}, {0, -1}, {0, 1}}
dfs = func(x, y, cc int) int {
if x < 0 || x > m-1 || y < 0 || y > n-1 || grid[x][y] != 1 {
return 0
}
if visited[x*n+y] != 0 {
return 0
}
visited[x*n+y] = cc
return 1 + dfs(x-1, y, cc) + dfs(x+1, y, cc) + dfs(x, y-1, cc) + dfs(x, y+1, cc)
}
cc := 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 && visited[i*n+j] == 0{
area[cc] = dfs(i, j, cc)
cc++
}
}
}
rt := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
resVal := 1
if grid[i][j] == 0 {
tmp := make(map[int]int, 4)
for k := 0; k < len(dir);k++ {
// 检查附近的4个点
if i + dir[k][0] >= 0 && i+dir[k][0] < m && j+dir[k][1] >= 0 && j+dir[k][1] < n{
x, y := i + dir[k][0], j + dir[k][1]
v := visited[x*n + y]
tmp[v] = 1
}
}
for k, _ :=range tmp {
resVal += area[k]
}
if resVal > rt{
rt = resVal
}
}
}
}
return rt
}
- 原文作者：Binean
- 原文链接：https://bzhou830.github.io/post/20170104%E5%9B%BE%E8%AE%BA%E7%AE%97%E6%B3%9504/
- 版权声明：本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。
