Java實(shí)現(xiàn)深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)算法
一.深度優(yōu)先遍歷和廣度優(yōu)先遍歷
1.深度優(yōu)先遍歷
圖的深度優(yōu)先搜索(Depth First Search) .
1) 深度優(yōu)先遍歷，從初始訪問結(jié)點(diǎn)出發(fā)，初始訪問結(jié)點(diǎn)可能有多個(gè)鄰接結(jié)點(diǎn)，深度優(yōu)先遍歷的策略就是首先訪問第一個(gè)鄰接結(jié)點(diǎn)，然后再以這個(gè)被訪問的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問它的第一個(gè)鄰接結(jié)點(diǎn)，可以這樣理解:每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)。
2)我們可以看到，這樣的訪問策略是優(yōu)先往縱向挖掘深入而不是對(duì)一個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)進(jìn)行橫向訪問。
3)顯然，深度優(yōu)先搜索是一個(gè)遞歸的過程(可以用棧來模擬)
例如這個(gè)圖進(jìn)行深度優(yōu)先遍歷:V1--->V2--->V5--->V3--->V6-->V4
具體的代碼實(shí)現(xiàn)
public class Graph {
public ArrayList<String> vertexList;//存儲(chǔ)頂點(diǎn)的集合
public int[][] edges; //存儲(chǔ)圖對(duì)應(yīng)的鄰接矩陣
public int numOfEdges; //表示邊的數(shù)目
public boolean[] isVisted; //記錄某個(gè)節(jié)點(diǎn)是否被訪問
//初始化
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
isVisted = new boolean[n];
}
//得到第一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)w
//如果存在就返回對(duì)應(yīng)的下標(biāo),否則就返回-1
public int getFirstNeighbor(int index) {
for (int i = 0; i < getNumOfVertex(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//根據(jù)前一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)來獲取下一個(gè)鄰接節(jié)點(diǎn)
public int getNextNeighbor(int v1, int v2) {
for (int i = v2 + 1; i < getNumOfVertex(); i++) {
if (edges[v1][i] > 0) {
return i;
}
}
return -1;
}
//返回結(jié)點(diǎn)i對(duì)應(yīng)的數(shù)據(jù)
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//深度優(yōu)先遍歷算法
//對(duì)dfs進(jìn)行重載,遍歷所有的結(jié)點(diǎn),并進(jìn)行dfs
//避免不連通的情況出現(xiàn)
public void dfs() {
isVisted = new boolean[getNumOfVertex()];
//遍歷所有的結(jié)點(diǎn)
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisted[i]) {
dfs(i);
}
}
}
public void dfs(int i) {
//首先訪問此結(jié)點(diǎn),輸出
System.out.print(getValueByIndex(i) + "-->");
//將該結(jié)點(diǎn)設(shè)置成已經(jīng)訪問過
isVisted[i] = true;
//查找i結(jié)點(diǎn)的第一個(gè)鄰接節(jié)點(diǎn)
int w = getFirstNeighbor(i);
while (w != -1) {//存在
if (!isVisted[w]) {
dfs(w);
}
//如果w結(jié)點(diǎn)已經(jīng)被訪問過了
w = getNextNeighbor(i, w);
}
}
}2.廣度優(yōu)先遍歷
圖的廣度優(yōu)先搜索(Breadth First Search) .
1)廣度優(yōu)先遍歷，從初始訪問結(jié)點(diǎn)出發(fā)，初始訪問結(jié)點(diǎn)可能有多個(gè)鄰接結(jié)點(diǎn)，廣度優(yōu)先遍歷的策略就是首先訪問第一個(gè)鄰接結(jié)點(diǎn)，然后依次訪問初始訪問結(jié)點(diǎn)的相鄰接點(diǎn)，然后訪問初始節(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)的鄰接頂點(diǎn),初始節(jié)點(diǎn)第二個(gè)鄰接結(jié)點(diǎn)的鄰接節(jié)點(diǎn).....，
2)廣度優(yōu)先遍歷需要使用一個(gè)隊(duì)列以保持訪問過的結(jié)點(diǎn)的順序，以便按這個(gè)順序來訪問這些結(jié)點(diǎn)的鄰接結(jié)點(diǎn)
例如這個(gè)圖進(jìn)行廣度優(yōu)先遍歷:V1--->V2--->V4--->V5--->V6-->V3
具體的代碼實(shí)現(xiàn)
public class Graph {
public ArrayList<String> vertexList;//存儲(chǔ)頂點(diǎn)的集合
public int[][] edges; //存儲(chǔ)圖對(duì)應(yīng)的鄰接矩陣
public int numOfEdges; //表示邊的數(shù)目
public boolean[] isVisted; //記錄某個(gè)節(jié)點(diǎn)是否被訪問
//初始化
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
isVisted = new boolean[n];
}
//得到第一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)w
//如果存在就返回對(duì)應(yīng)的下標(biāo),否則就返回-1
public int getFirstNeighbor(int index) {
for (int i = 0; i < getNumOfVertex(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//根據(jù)前一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)來獲取下一個(gè)鄰接節(jié)點(diǎn)
public int getNextNeighbor(int v1, int v2) {
for (int i = v2 + 1; i < getNumOfVertex(); i++) {
if (edges[v1][i] > 0) {
return i;
}
}
return -1;
}
//返回結(jié)點(diǎn)i對(duì)應(yīng)的數(shù)據(jù)
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//深度優(yōu)先遍歷算法
//對(duì)dfs進(jìn)行重載,遍歷所有的結(jié)點(diǎn),并進(jìn)行dfs
//避免不連通的情況出現(xiàn)
public void dfs() {
isVisted = new boolean[getNumOfVertex()];
//遍歷所有的結(jié)點(diǎn)
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisted[i]) {
dfs(i);
}
}
}
public void bfs(int i) {
int u; //表示隊(duì)列頭結(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)
int w; //鄰接節(jié)點(diǎn)w
//隊(duì)列,記錄結(jié)點(diǎn)訪問的順序
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getValueByIndex(i) + "-->");
//標(biāo)記為已訪問
isVisted[i] = true;
queue.offer(i);
while (!queue.isEmpty()) {
//取出隊(duì)列的頭結(jié)點(diǎn)下標(biāo)
u = queue.poll();
w = getFirstNeighbor(u);
while (w != -1) {//找到存在的
//是否訪問過
if (!isVisted[w]) {
System.out.print(getValueByIndex(w) + "-->");
//標(biāo)記訪問過
isVisted[w] = true;
queue.add(w);
}
//以u(píng)為前驅(qū)節(jié)點(diǎn)找w后面的下一個(gè)鄰接點(diǎn)
w = getNextNeighbor(u, w);//體現(xiàn)出廣度優(yōu)先
}
}
}
}二.圖像渲染
1.題目描述
有一幅以m x n的二維整數(shù)數(shù)組表示的圖畫image，其中image[i][j]表示該圖畫的像素值大小。
你也被給予三個(gè)整數(shù) sr , sc 和 newColor 。你應(yīng)該從像素image[sr][sc]開始對(duì)圖像進(jìn)行 上色填充 。
為了完成 上色工作 ，從初始像素開始，記錄初始坐標(biāo)的 上下左右四個(gè)方向上 像素值與初始坐標(biāo)相同的相連像素點(diǎn)，接著再記錄這四個(gè)方向上符合條件的像素點(diǎn)與他們對(duì)應(yīng) 四個(gè)方向上 像素值與初始坐標(biāo)相同的相連像素點(diǎn)，……，重復(fù)該過程。將所有有記錄的像素點(diǎn)的顏色值改為newColor。
最后返回 經(jīng)過上色渲染后的圖像。
力扣: 力扣
2.問題分析
這是一道典型的BFS和DFS的問題,
先來考慮廣度優(yōu)先遍歷的方法:我們可以先把初始點(diǎn)像素相同的的上下左右點(diǎn)全部涂完色,然后再把第一次涂上色的格子的上下左右點(diǎn)涂上色,以此類推,直到?jīng)]有可以涂色的格子
假設(shè)所有格子都可以涂色,那么廣度優(yōu)先的涂色順序如下圖所示進(jìn)行涂色處理,這個(gè)過程中我們需要使用一個(gè)隊(duì)列進(jìn)行模擬,每一次尋找上下左右可以涂色的位置(不越界,像素值相同)進(jìn)行涂色,并且入隊(duì)列,把像素值替換為color
再來考慮深度優(yōu)先遍歷,深度優(yōu)先遍歷自然就是使用遞歸來實(shí)現(xiàn),每一次我們?cè)L問上方的格子(默認(rèn)的訪問順序是上下左右),直到不能訪問,然后訪問不能訪問上班的格子的下邊的格子,此格子不能訪問再訪問左邊格子,不能訪問再訪問右邊格子,一層一層的遞歸下去.......
3代碼實(shí)現(xiàn)
1.廣度優(yōu)先遍歷
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int m = image.length;
int n = image[0].length;
int curColor = image[sr][sc];
if (image[sr][sc] == color) {
return image;
}
LinkedList<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sr, sc});
image[sr][sc] = color;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int x = poll[0], y = poll[1];
for (int i = 0; i < 4; ++i) {
int mx = x + dx[i], my = y + dy[i];
//沒有越界,并且像素值和初始像素值相同
if (mx >= 0 && mx < m && my >= 0 && my < n && image[mx][my] == curColor) {
queue.offer(new int[]{mx, my});
image[mx][my] = color;
}
}
}
return image;
}2.深度優(yōu)先遍歷
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int currColor = image[sr][sc];
if (currColor != color) {
dfs(image, sr, sc, currColor, color);
}
return image;
}
public void dfs(int[][] image, int x, int y, int curColor, int color) {
if (image[x][y] == curColor) {
image[x][y] = color;
}
for (int i = 0; i < 4; ++i) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length && image[mx][my] == curColor) {
dfs(image, mx, my, curColor, color);
}
}
}三.島嶼的最大面積
1.題目描述
給你一個(gè)大小為 m x n 的二進(jìn)制矩陣 grid 。
島嶼是由一些相鄰的1(代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在 水平或者豎直的四個(gè)方向上 相鄰。你可以假設(shè)grid 的四個(gè)邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數(shù)目。
計(jì)算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
力扣:力扣
2.問題分析
這一題上一題相似,上一題是把像素相同的格子全部涂上顏色,這一題是尋找面積最大的島嶼,把能涂的格子全部涂上顏色,這一題是把一個(gè)島嶼的面積全部遍歷從而求出面積,在給出的海域中有很多的島嶼,我們只需要每次記錄面積最大的島嶼的面積,最后直接返回即可
廣度優(yōu)先遍歷:遍歷整個(gè)矩陣grid,找到為陸地(1),然后在這片陸地上進(jìn)行遍歷,把遍歷到的陸地格子置為0,也就是海洋,隊(duì)列中沒有陸地格子了,說明這個(gè)島嶼全部都遍歷完了,和記錄的最大面積對(duì)比,最終直到全部的矩陣格子遍歷完成,返回最大的面積
深度優(yōu)先遍歷:和廣度優(yōu)先的思路一樣,唯一不一樣的點(diǎn)就是找到島嶼后的遍歷順序,具體看代碼
3.代碼實(shí)現(xiàn)
1.廣度優(yōu)先遍歷
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] == 0)
continue;
LinkedList<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int count = 1;
grid[i][j] = 0;
while (!queue.isEmpty()) {
int[] poll = queue.poll();
for (int z = 0; z < 4; ++z) {
int mx = poll[0] + dx[z], my = poll[1] + dy[z];
if (mx >= 0 && my >= 0 && mx < grid.length && my < grid[0].length && grid[mx][my] != 0) {
count++;
grid[mx][my] = 0;
queue.offer(new int[]{mx, my});
}
}
}
ans = Math.max(ans, count);
}
}
return ans;
}2.深度優(yōu)先遍歷
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
ans = Math.max(ans, dfs(grid, i, j));
}
}
return ans;
}
public int dfs(int[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0)
return 0;
grid[x][y] = 0;
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int ans = 1;
for (int i = 0; i < 4; ++i) {
int mx = x + dx[i], my = y + dy[i];
ans += dfs(grid, mx, my);
}
return ans;
}四.島嶼的周長
1.題目描述
給定一個(gè) row x col 的二維網(wǎng)格地圖 grid ，其中：grid[i][j] = 1 表示陸地， grid[i][j] = 0 表示水域。
網(wǎng)格中的格子 水平和垂直 方向相連（對(duì)角線方向不相連）。整個(gè)網(wǎng)格被水完全包圍，但其中恰好有一個(gè)島嶼（或者說，一個(gè)或多個(gè)表示陸地的格子相連組成的島嶼）。
島嶼中沒有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網(wǎng)格為長方形，且寬度和高度均不超過 100 。計(jì)算這個(gè)島嶼的周長。
力扣:力扣
2.問題分析
求面積我們可以求出來,但是求周長確實(shí)不容易想出來.但是經(jīng)過我們仔細(xì)觀察,我們就可以發(fā)現(xiàn),如果島嶼的一邊是水或者是邊界地區(qū)的話,那么這一條邊就可以作為周長的一部分(周長+1)
廣度優(yōu)先遍歷:這一道題使用這個(gè)方法,沒必要?jiǎng)?chuàng)建隊(duì)列,我們只需要把這個(gè)二維數(shù)組遍歷完成,判斷每一塊陸地的周長,這樣我們就可以求出總的邊長了,如果這一道題是有很多個(gè)島嶼,求周長最大的島嶼的周長,我們還是需要用到隊(duì)列的
深度優(yōu)先遍歷:深度優(yōu)先遍歷和上邊的幾題一樣的思路,具體看代碼
3.代碼實(shí)現(xiàn)
1.廣度優(yōu)先遍歷
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public int islandPerimeter(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
for (int x = 0; x < 4; ++x) {
int mx = i + dx[x], my = j + dy[x];
if (mx < 0 || my < 0 || mx >= m || my >= n || grid[mx][my] == 0) {
ans++;
}
}
}
}
}
return ans;
}2.深度優(yōu)先遍歷
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public int islandPerimeter(int[][] grid) {
int m = grid.length, n = grid[0].length;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
ans += dfs(i, j, grid, m, n);
return ans;
}
}
}
return ans;
}
public int dfs(int x, int y, int[][] grid, int m, int n) {
if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] == 0)
return 1;
if (grid[x][y] == 2)
return 0;
grid[x][y] = 2;
int sum = 0;
for (int i = 0; i < 4; ++i) {
int mx = x + dx[i], my = y + dy[i];
sum += dfs(mx, my, grid, m, n);
}
return sum;
}
到此這篇關(guān)于Java實(shí)現(xiàn)深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)算法的文章就介紹到這了,更多相關(guān)Java深度優(yōu)先和廣度優(yōu)先內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
一文教會(huì)你使用jmap和MAT進(jìn)行堆內(nèi)存溢出分析
本文介紹關(guān)于jmap和MAT的使用來進(jìn)行堆內(nèi)存溢出分析，因?yàn)檫@個(gè)內(nèi)存溢出是我們手動(dòng)構(gòu)造出來的，查找比較簡單，真的到了生產(chǎn)上面需要我們仔細(xì)排除2021-09-09
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)簡單的聊天室功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
依賴注入是由“依賴”和“注入”兩個(gè)詞匯組合而成，那么我們?cè)僖淮雾樚倜?，分別分析這兩個(gè)詞語，這篇文章主要介紹了Spring DI依賴注入詳解,需要的朋友可以參考下2023-04-04
逆轉(zhuǎn)交替合并兩個(gè)鏈表的解析與實(shí)現(xiàn)
本篇文章主要介紹了將兩個(gè)鏈表逆轉(zhuǎn)交替合并的實(shí)現(xiàn)思路與方法,需要的朋友可以參考下2015-07-07
Spring+Quartz實(shí)現(xiàn)動(dòng)態(tài)任務(wù)調(diào)度詳解
這篇文章主要介紹了Spring+Quartz實(shí)現(xiàn)動(dòng)態(tài)任務(wù)調(diào)度詳解,最近經(jīng)常基于spring?boot寫定時(shí)任務(wù),并且是使用注解的方式進(jìn)行實(shí)現(xiàn),分成的方便將自己的類注入spring容器,需要的朋友可以參考下2024-01-01
事務(wù)的作用就是為了保證用戶的每一個(gè)操作都是可靠的，事務(wù)中的每一步操作都必須成功執(zhí)行，只要有發(fā)生異常就 回退到事務(wù)開始未進(jìn)行操作的狀態(tài)。事務(wù)管理是Spring框架中最為常用的功能之一，我們?cè)谑褂肧pring Boot開發(fā)應(yīng)用時(shí)，大部分情況下也都需要使用事務(wù)2022-08-08
JDK8中的HashMap初始化和擴(kuò)容機(jī)制詳解
這篇文章主要介紹了JDK8中的HashMap初始化和擴(kuò)容機(jī)制，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
SpringBoot注解@ConditionalOnClass底層源碼實(shí)現(xiàn)
這篇文章主要為大家介紹了SpringBoot注解@ConditionalOnClass底層源碼實(shí)現(xiàn)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-02-02
本文主要介紹了Java中Boolean引發(fā)缺陷的解決，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-06-06
這篇文章主要介紹了Java并發(fā)工具輔助類代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04