廣度優(yōu)先搜索

這個是很復雜的

在賓縣等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、網(wǎng)站制作 網(wǎng)站設(shè)計制作按需網(wǎng)站設(shè)計,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計,成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站建設(shè)公司,賓縣網(wǎng)站建設(shè)費用合理。

你可以百度這個算法

然后套進去寫代碼

LeetCode 力扣官方題解 - 1020. 飛地的數(shù)量

題目描述

給你一個大小為 m x n 的二進制矩陣 grid，其中 0 表示一個海洋單元格、1 表示一個陸地單元格。

一次 移動 是指從一個陸地單元格走到另一個相鄰（上、下、左、右）的陸地單元格或跨過 grid 的邊界。

返回網(wǎng)格中 無法 在任意次數(shù)的移動中離開網(wǎng)格邊界的陸地單元格的數(shù)量。

示例 1：

示例 2：

提示：

根據(jù)飛地的定義，如果從一個陸地單元格出發(fā)無法移動到網(wǎng)格邊界，則這個陸地單元格是飛地。因此可以將所有陸地單元格分成兩類：第一類陸地單元格和網(wǎng)格邊界相連，這些陸地單元格不是飛地；第二類陸地單元格不和網(wǎng)格邊界相連，這些陸地單元格是飛地。

我們可以從網(wǎng)格邊界上的每個陸地單元格開始深度優(yōu)先搜索，遍歷完邊界之后，所有和網(wǎng)格邊界相連的陸地單元格就都被訪問過了。然后遍歷整個網(wǎng)格，如果網(wǎng)格中的一個陸地單元格沒有被訪問過，則該陸地單元格不和網(wǎng)格的邊界相連，是飛地。

代碼實現(xiàn)時，由于網(wǎng)格邊界上的單元格一定不是飛地，因此遍歷網(wǎng)格統(tǒng)計飛地的數(shù)量時只需要遍歷不在網(wǎng)格邊界上的單元格。

代碼

Java

C#

C++

C

Python3

Golang

JavaScript

復雜度分析

也可以通過廣度優(yōu)先搜索判斷每個陸地單元格是否和網(wǎng)格邊界相連。

首先從網(wǎng)格邊界上的每個陸地單元格開始廣度優(yōu)先搜索，訪問所有和網(wǎng)格邊界相連的陸地單元格，然后遍歷整個網(wǎng)格，統(tǒng)計飛地的數(shù)量。

代碼

Java

C#

C++

C

Python3

Golang

JavaScript

復雜度分析

除了深度優(yōu)先搜索和廣度優(yōu)先搜索的方法以外，也可以使用并查集判斷每個陸地單元格是否和網(wǎng)格邊界相連。

并查集的核心思想是計算網(wǎng)格中的每個陸地單元格所在的連通分量。對于網(wǎng)格邊界上的每個陸地單元格，其所在的連通分量中的所有陸地單元格都不是飛地。如果一個陸地單元格所在的連通分量不同于任何一個網(wǎng)格邊界上的陸地單元格所在的連通分量，則該陸地單元格是飛地。

并查集的做法是，遍歷整個網(wǎng)格，對于網(wǎng)格中的每個陸地單元格，將其與所有相鄰的陸地單元格做合并操作。由于需要判斷每個陸地單元格所在的連通分量是否和網(wǎng)格邊界相連，因此并查集還需要記錄每個單元格是否和網(wǎng)格邊界相連的信息，在合并操作時更新該信息。

在遍歷網(wǎng)格完成并查集的合并操作之后，再次遍歷整個網(wǎng)格，通過并查集中的信息判斷每個陸地單元格是否和網(wǎng)格邊界相連，統(tǒng)計飛地的數(shù)量。

代碼

Java

C#

C++

C

Python3

Golang

JavaScript

復雜度分析

BY /

本文作者：力扣

java如何實現(xiàn) 深度優(yōu)先 廣度優(yōu)先

下面是我修改了滴源碼，是基于一張簡單的地圖，在地圖上搜索目的節(jié)點，依次用深度優(yōu)先、廣度優(yōu)先、Dijkstra算法實現(xiàn)。

import java.util.ArrayList;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Stack;

/**

*

* @author yinzhuo

*

*/

public class Arithmatic {

boolean flag = true;

// 一張地圖

static int[][] map = new int[][]// 地圖數(shù)組

{

{ 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0 },

{ 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };

Java連連看代碼。 廣度優(yōu)先搜索算法實現(xiàn)，最小拐彎數(shù)，高手留下qq。

import javax.swing.*;

import java.awt.*;

import java.awt.event.*;

public class lianliankan implements ActionListener

{

JFrame mainFrame; //主面板

Container thisContainer;

JPanel centerPanel,southPanel,northPanel; //子面板

JButton diamondsButton[][] = new JButton[6][5];//游戲按鈕數(shù)組

JButton exitButton,resetButton,newlyButton; //退出，重列，重新開始按鈕 JLabel fractionLable=new JLabel("0"); //分數(shù)標簽

JButton firstButton,secondButton; //分別記錄兩次被選中的按鈕

int grid[][] = new int[8][7];//儲存游戲按鈕位置

static boolean pressInformation=false; //判斷是否有按鈕被選中

int x0=0,y0=0,x=0,y=0,fristMsg=0,secondMsg=0,validateLV; //游戲按鈕的位置坐標 int i,j,k,n;//消除方法控制

public void init(){

mainFrame=new JFrame("JKJ連連看");

thisContainer = mainFrame.getContentPane();

thisContainer.setLayout(new BorderLayout());

centerPanel=new JPanel();

southPanel=new JPanel();

northPanel=new JPanel();

thisContainer.add(centerPanel,"Center");

thisContainer.add(southPanel,"South");

thisContainer.add(northPanel,"North");

centerPanel.setLayout(new GridLayout(6,5));

for(int cols = 0;cols 6;cols++){

for(int rows = 0;rows 5;rows++ ){

diamondsButton[cols][rows]=new JButton(String.valueOf(grid[cols+1][rows+1])); diamondsButton[cols][rows].addActionListener(this);

centerPanel.add(diamondsButton[cols][rows]);

}

}

exitButton=new JButton("退出");

exitButton.addActionListener(this);

resetButton=new JButton("重列");

resetButton.addActionListener(this);

newlyButton=new JButton("再來一局");

newlyButton.addActionListener(this);

southPanel.add(exitButton);

southPanel.add(resetButton);

1/8頁

southPanel.add(newlyButton);

fractionLable.setText(String.valueOf(Integer.parseInt(fractionLable.getText())));

northPanel.add(fractionLable);

mainFrame.setBounds(280,100,500,450);

mainFrame.setVisible(true);

}

public void randomBuild() {

int randoms,cols,rows;

for(int twins=1;twins=15;twins++) {

randoms=(int)(Math.random()*25+1);

for(int alike=1;alike=2;alike++) {

cols=(int)(Math.random()*6+1);

rows=(int)(Math.random()*5+1);

while(grid[cols][rows]!=0) {

cols=(int)(Math.random()*6+1);

rows=

鄰接表做深度優(yōu)先遍歷和廣度優(yōu)先遍歷的代碼

3、廣度優(yōu)先搜索算法

(1)鄰接表表示圖的廣度優(yōu)先搜索算法

void BFS(ALGraph*G，int k)

{// 以vk為源點對用鄰接表表示的圖G進行廣度優(yōu)先搜索

int i；

CirQueue Q； //須將隊列定義中DataType改為int

EdgeNode *p；

InitQueue(Q)；//隊列初始化

//訪問源點vk

printf("visit vertex：％e"，G-adjlist[k].vertex)；

visited[k]=TRUE；

EnQueue(Q，k)；//vk已訪問，將其人隊。（實際上是將其序號人隊）

while(!QueueEmpty(Q)){//隊非空則執(zhí)行

i=DeQueue(Q)； //相當于vi出隊

p=G-adjlist[i].firstedge； //取vi的邊表頭指針

while(p){//依次搜索vi的鄰接點vj(令p-adjvex=j)

if(!visited[p-adivex]){ //若vj未訪問過

printf("visitvertex：％c"，C-adjlistlp-adjvex].vertex)； //訪問vj

visited[p-adjvex]=TRUE；

EnQueue(Q，p-adjvex)；//訪問過的vj人隊

}//endif

p=p-next；//找vi的下一鄰接點

}//endwhile

}//endwhile

}//end of BFS

（2）鄰接矩陣表示的圖的廣度優(yōu)先搜索算法

void BFSM(MGraph *G，int k)

{以vk為源點對用鄰接矩陣表示的圖G進行廣度優(yōu)先搜索

int i，j；

CirQueue Q；

InitQueue(Q)；

printf("visit vertex：％c"，G-vexs[k])； //訪問源點vk

visited[k]=TRUE；

EnQueue(Q，k)；

while(!QueueEmpty(Q)){

i=DeQueue(Q)； //vi出隊

for(j=0;jG-n;j++)//依次搜索vi的鄰接點vj

if(G-edges[i][j]==1!visited[j]){//vi未訪問

printf("visit vertex：％c"，G-vexs[j])；//訪問vi

visited[j]=TRUE；

EnQueue(Q，j)；//訪問過的vi人隊

}

}//endwhile

}//BFSM