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