Java實現(xiàn)深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)算法
一.深度優(yōu)先遍歷和廣度優(yōu)先遍歷
1.深度優(yōu)先遍歷
圖的深度優(yōu)先搜索(Depth First Search) .
1) 深度優(yōu)先遍歷，從初始訪問結(jié)點出發(fā)，初始訪問結(jié)點可能有多個鄰接結(jié)點，深度優(yōu)先遍歷的策略就是首先訪問第一個鄰接結(jié)點，然后再以這個被訪問的鄰接結(jié)點作為初始結(jié)點，訪問它的第一個鄰接結(jié)點，可以這樣理解:每次都在訪問完當前結(jié)點后首先訪問當前結(jié)點的第一個鄰接結(jié)點。
2)我們可以看到，這樣的訪問策略是優(yōu)先往縱向挖掘深入而不是對一個結(jié)點的所有鄰接結(jié)點進行橫向訪問。
3)顯然，深度優(yōu)先搜索是一個遞歸的過程(可以用棧來模擬)
例如這個圖進行深度優(yōu)先遍歷:V1--->V2--->V5--->V3--->V6-->V4
具體的代碼實現(xiàn)
public class Graph {
public ArrayList<String> vertexList;//存儲頂點的集合
public int[][] edges; //存儲圖對應(yīng)的鄰接矩陣
public int numOfEdges; //表示邊的數(shù)目
public boolean[] isVisted; //記錄某個節(jié)點是否被訪問
//初始化
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
isVisted = new boolean[n];
}
//得到第一個鄰接節(jié)點的下標w
//如果存在就返回對應(yīng)的下標,否則就返回-1
public int getFirstNeighbor(int index) {
for (int i = 0; i < getNumOfVertex(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//根據(jù)前一個鄰接節(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;
}
//返回結(jié)點i對應(yīng)的數(shù)據(jù)
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//深度優(yōu)先遍歷算法
//對dfs進行重載,遍歷所有的結(jié)點,并進行dfs
//避免不連通的情況出現(xiàn)
public void dfs() {
isVisted = new boolean[getNumOfVertex()];
//遍歷所有的結(jié)點
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisted[i]) {
dfs(i);
}
}
}
public void dfs(int i) {
//首先訪問此結(jié)點,輸出
System.out.print(getValueByIndex(i) + "-->");
//將該結(jié)點設(shè)置成已經(jīng)訪問過
isVisted[i] = true;
//查找i結(jié)點的第一個鄰接節(jié)點
int w = getFirstNeighbor(i);
while (w != -1) {//存在
if (!isVisted[w]) {
dfs(w);
}
//如果w結(jié)點已經(jīng)被訪問過了
w = getNextNeighbor(i, w);
}
}
}2.廣度優(yōu)先遍歷
圖的廣度優(yōu)先搜索(Breadth First Search) .
1)廣度優(yōu)先遍歷，從初始訪問結(jié)點出發(fā)，初始訪問結(jié)點可能有多個鄰接結(jié)點，廣度優(yōu)先遍歷的策略就是首先訪問第一個鄰接結(jié)點，然后依次訪問初始訪問結(jié)點的相鄰接點，然后訪問初始節(jié)點的第一個鄰接結(jié)點的鄰接頂點,初始節(jié)點第二個鄰接結(jié)點的鄰接節(jié)點.....，
2)廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結(jié)點的順序，以便按這個順序來訪問這些結(jié)點的鄰接結(jié)點
例如這個圖進行廣度優(yōu)先遍歷:V1--->V2--->V4--->V5--->V6-->V3
具體的代碼實現(xiàn)
public class Graph {
public ArrayList<String> vertexList;//存儲頂點的集合
public int[][] edges; //存儲圖對應(yīng)的鄰接矩陣
public int numOfEdges; //表示邊的數(shù)目
public boolean[] isVisted; //記錄某個節(jié)點是否被訪問
//初始化
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
isVisted = new boolean[n];
}
//得到第一個鄰接節(jié)點的下標w
//如果存在就返回對應(yīng)的下標,否則就返回-1
public int getFirstNeighbor(int index) {
for (int i = 0; i < getNumOfVertex(); i++) {
if (edges[index][i] > 0) {
return i;
}
}
return -1;
}
//根據(jù)前一個鄰接節(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;
}
//返回結(jié)點i對應(yīng)的數(shù)據(jù)
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//深度優(yōu)先遍歷算法
//對dfs進行重載,遍歷所有的結(jié)點,并進行dfs
//避免不連通的情況出現(xiàn)
public void dfs() {
isVisted = new boolean[getNumOfVertex()];
//遍歷所有的結(jié)點
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisted[i]) {
dfs(i);
}
}
}
public void bfs(int i) {
int u; //表示隊列頭結(jié)點對應(yīng)的下標
int w; //鄰接節(jié)點w
//隊列,記錄結(jié)點訪問的順序
LinkedList<Integer> queue = new LinkedList<>();
System.out.print(getValueByIndex(i) + "-->");
//標記為已訪問
isVisted[i] = true;
queue.offer(i);
while (!queue.isEmpty()) {
//取出隊列的頭結(jié)點下標
u = queue.poll();
w = getFirstNeighbor(u);
while (w != -1) {//找到存在的
//是否訪問過
if (!isVisted[w]) {
System.out.print(getValueByIndex(w) + "-->");
//標記訪問過
isVisted[w] = true;
queue.add(w);
}
//以u為前驅(qū)節(jié)點找w后面的下一個鄰接點
w = getNextNeighbor(u, w);//體現(xiàn)出廣度優(yōu)先
}
}
}
}二.圖像渲染
1.題目描述
有一幅以m x n的二維整數(shù)數(shù)組表示的圖畫image，其中image[i][j]表示該圖畫的像素值大小。
你也被給予三個整數(shù) sr , sc 和 newColor 。你應(yīng)該從像素image[sr][sc]開始對圖像進行 上色填充 。
為了完成 上色工作 ，從初始像素開始，記錄初始坐標的 上下左右四個方向上 像素值與初始坐標相同的相連像素點，接著再記錄這四個方向上符合條件的像素點與他們對應(yīng) 四個方向上 像素值與初始坐標相同的相連像素點，……，重復該過程。將所有有記錄的像素點的顏色值改為newColor。
最后返回 經(jīng)過上色渲染后的圖像。
力扣: 力扣
2.問題分析
這是一道典型的BFS和DFS的問題,
先來考慮廣度優(yōu)先遍歷的方法:我們可以先把初始點像素相同的的上下左右點全部涂完色,然后再把第一次涂上色的格子的上下左右點涂上色,以此類推,直到?jīng)]有可以涂色的格子
假設(shè)所有格子都可以涂色,那么廣度優(yōu)先的涂色順序如下圖所示進行涂色處理,這個過程中我們需要使用一個隊列進行模擬,每一次尋找上下左右可以涂色的位置(不越界,像素值相同)進行涂色,并且入隊列,把像素值替換為color
再來考慮深度優(yōu)先遍歷,深度優(yōu)先遍歷自然就是使用遞歸來實現(xiàn),每一次我們訪問上方的格子(默認的訪問順序是上下左右),直到不能訪問,然后訪問不能訪問上班的格子的下邊的格子,此格子不能訪問再訪問左邊格子,不能訪問再訪問右邊格子,一層一層的遞歸下去.......
3代碼實現(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.題目描述
給你一個大小為 m x n 的二進制矩陣 grid 。
島嶼是由一些相鄰的1(代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個 1 必須在 水平或者豎直的四個方向上 相鄰。你可以假設(shè)grid 的四個邊緣都被 0（代表水）包圍著。
島嶼的面積是島上值為 1 的單元格的數(shù)目。
計算并返回 grid 中最大的島嶼面積。如果沒有島嶼，則返回面積為 0 。
力扣:力扣
2.問題分析
這一題上一題相似,上一題是把像素相同的格子全部涂上顏色,這一題是尋找面積最大的島嶼,把能涂的格子全部涂上顏色,這一題是把一個島嶼的面積全部遍歷從而求出面積,在給出的海域中有很多的島嶼,我們只需要每次記錄面積最大的島嶼的面積,最后直接返回即可
廣度優(yōu)先遍歷:遍歷整個矩陣grid,找到為陸地(1),然后在這片陸地上進行遍歷,把遍歷到的陸地格子置為0,也就是海洋,隊列中沒有陸地格子了,說明這個島嶼全部都遍歷完了,和記錄的最大面積對比,最終直到全部的矩陣格子遍歷完成,返回最大的面積
深度優(yōu)先遍歷:和廣度優(yōu)先的思路一樣,唯一不一樣的點就是找到島嶼后的遍歷順序,具體看代碼
3.代碼實現(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.題目描述
給定一個 row x col 的二維網(wǎng)格地圖 grid ，其中：grid[i][j] = 1 表示陸地， grid[i][j] = 0 表示水域。
網(wǎng)格中的格子 水平和垂直 方向相連（對角線方向不相連）。整個網(wǎng)格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。
島嶼中沒有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網(wǎng)格為長方形，且寬度和高度均不超過 100 。計算這個島嶼的周長。
力扣:力扣
2.問題分析
求面積我們可以求出來,但是求周長確實不容易想出來.但是經(jīng)過我們仔細觀察,我們就可以發(fā)現(xiàn),如果島嶼的一邊是水或者是邊界地區(qū)的話,那么這一條邊就可以作為周長的一部分(周長+1)
廣度優(yōu)先遍歷:這一道題使用這個方法,沒必要創(chuàng)建隊列,我們只需要把這個二維數(shù)組遍歷完成,判斷每一塊陸地的周長,這樣我們就可以求出總的邊長了,如果這一道題是有很多個島嶼,求周長最大的島嶼的周長,我們還是需要用到隊列的
深度優(yōu)先遍歷:深度優(yōu)先遍歷和上邊的幾題一樣的思路,具體看代碼
3.代碼實現(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實現(xiàn)深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)算法的文章就介紹到這了,更多相關(guān)Java深度優(yōu)先和廣度優(yōu)先內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
springboot使用hibernate validation對參數(shù)校驗的實現(xiàn)方法
這篇文章主要介紹了spring-boot 使用hibernate validation對參數(shù)進行優(yōu)雅的校驗,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
SpringBoot封裝響應(yīng)數(shù)據(jù)實現(xiàn)過程詳解
這篇文章主要介紹了SpringBoot封裝響應(yīng)數(shù)據(jù)實現(xiàn)過程，SpringBoot響應(yīng)數(shù)據(jù)封裝是指在SpringBoot應(yīng)用程序中，將返回的數(shù)據(jù)進行封裝，以便于前端頁面或其他客戶端使用，感興趣想要詳細了解可以參考下文2023-05-05
這篇文章主要為大家介紹了java分布式基于RestTemplate的使用方法說明，有需要的朋友可以借鑒參考下希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-02-02
intelliJ IDEA 多行選中相同內(nèi)容的快捷鍵分享
這篇文章主要介紹了intelliJ IDEA 多行選中相同內(nèi)容的快捷鍵分享，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02
Spring Data JPA實現(xiàn)動態(tài)查詢的兩種方法
本篇文章主要介紹了Spring Data JPA實現(xiàn)動態(tài)查詢的兩種方法，具有一定的參考價值，有興趣的可以了解一下。2017-04-04
這篇文章主要為大家詳細介紹了java實現(xiàn)簡單快遞系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了java 異常詳解及應(yīng)用實例的相關(guān)資料,需要的朋友可以參考下2017-01-01
springBoot controller,service,dao,mapper,model層的作用說明
這篇文章主要介紹了springBoot controller,service,dao,mapper,model層的作用說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-11-11
大家好，本篇文章主要講的是java多態(tài)中的就近原則介紹，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
這篇文章主要為大家詳細介紹了HashSet、HashMap底層添加、遍歷元素的機制，追蹤并分析源碼，文中的示例代碼講解詳細，希望對大學有所幫助2022-07-07