當前位置:首頁 » 操作系統 » 廣度優先演算法java

廣度優先演算法java

發布時間: 2023-07-01 18:19:59

java連連看代碼。 廣度優先搜索演算法實現,最小拐彎數,高手留下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];//游戲按鈕數組
JButton exitButton,resetButton,newlyButton; //退出,重列,重新開始按鈕 JLabel fractionLable=new JLabel("0"); //分數標簽
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=

❷ 常見演算法5、廣度優先搜索 Breadth-First Search

1、定義

廣度優先搜索 (Breadth-First Search)是最簡便的圖的搜索演算法之一,又稱 寬度優先搜索 ,這一演算法也是很多重要的圖演算法的原型。廣度優先搜索屬於一種盲目搜尋法,目的是系統地展開並檢查圖中的所有節點,以找尋結果。換句話說,它並不考慮結果的可能位置,徹底地搜索整張圖,直到找到結果為止。

2、應用

廣度優先搜索被用於解決 最短路徑問題(shortest-path problem)

廣度優先搜索讓你能夠找出兩樣東西之間的最短距離,不過最短距離的含義有很多!使用廣度優先搜索可以:

3、圖簡介

既然廣度優先搜索是作用於圖的一種演算法,這里對圖作一個簡單的介紹,先不深入了解。

圖由 節點 組成。一個節點可能與多個節點相連,這些節點被稱為鄰居。

廣度優先演算法的核心思想是:從初始節點開始,應用算符生成第一層節點,檢查目標節點是否在這些後繼節點中,若沒有,再用產生式規則將所有第一層的節點逐一擴展,得到第二層節點,並逐一檢查第二層節點中是否包含目標節點。若沒有,再用算符逐一擴展第二層的所有節點……,如此依次擴展,檢查下去,直到發現目標節點為止。即

廣度優先搜索使用隊列(queue)來實現,整個過程也可以看做一個倒立的樹形。

例:假如你需要在你的人際關系網中尋找是否有職業為醫生的人,圖如下:

而使用廣度優先搜索工作原理大概如下 :

1、Python 3 :

2、php

1、《演算法圖解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue類: https://www.php.net/manual/zh/class.splqueue.php

❸ java連連看使用廣度優先演算法實現,求具體解釋廣度優先演算法和代碼

void bfs(TreeNode t){
Queue q = new LinkedList<TreeNode>();
q.enqueue(t);
while(!q.isEmpty && q.peek().element != null){
TreeNode temp = q.dequeue();
System.out.println(temp.element);
q.enqueue(temp.leftchild);
q.enqueue(temp.rightchild);
}
}
class TreeNode <AnyType>{
AnyType element;
TreeNode rightchild;
TreeNode leftchild;
}

❹ 廣度優先演算法

廣度優先演算法(Breadth-First Search),同廣度優先搜索,又稱作寬度優先搜索,或橫向優先搜索,簡稱BFS,是一種圖形搜索演演算法。簡單的說,BFS是從根節點開始,沿著樹的寬度遍歷樹的節點,如果發現目標,則演算終止。廣度優先搜索的實現一般採用open-closed表。

❺ 廣度優先遍歷是什麼

1.廣度優先遍歷的思想廣度優先遍歷類似樹的按層次遍歷。設初始狀態時圖中的所有頂點未被訪問,則演算法思想為:首先訪問圖中某指定的起始頂點v,並將其標記為已訪問過,然後由v出發依次訪問v的各個未被訪問的鄰接點v1,v2,…,vk;並將其均標識為已訪問過,再分別從v1,v2,…,vk出發依次訪問它們未被訪問的鄰接點,並使「先被訪問頂點的鄰接點」先於「後被訪問頂點的鄰接點」被訪問。直至圖中所有與頂點v路徑相通的頂點都被訪問到。

若G是連通圖,則遍歷完成;否則,在圖G中另選一個尚未訪問的頂點作為新源點繼續上述搜索過程,直至圖G中所有頂點均被訪問為止。

2.廣度優先遍歷示例例如,對圖7-18(a)所示的圖G,假設指定從頂點v1開始進行廣度優先遍歷,首先訪問v1,因與v1相鄰並且未被訪問過的頂點有v2和v6,則訪問v2和v6,然後訪問與v2相鄰並未訪問的鄰接點v2,v7,再訪問與v6相鄰並且未被訪問過的鄰接點v5,按這樣的次序依次訪問與v2相鄰並且未被訪問過的鄰接點v4,v8,與v7相鄰並且未被訪問過的鄰接點v9,此時,與v5,v4,v8,v9相鄰並且未被訪問過的鄰接點沒有了,即圖G中的所有頂點訪問完,其遍歷序列為:v1->v2->v6->v2->v7->v5->v4->v8->v9。這種順序不是唯一的,如果從v1出發後,相鄰的多個頂點優先選擇序號大的頂點訪問,其遍歷序列為:v1->v6->v2->v5->v7->v2->v4->v9->v8。同理,圖7-18(b)是假設從v1開始,相鄰的多個頂點優先選擇序號小的頂點訪問,其遍歷序列為:v1->v2->v2->v4->v5->v6->v7->v8;相鄰的多個頂點優先選擇序號大的頂點訪問,其遍歷序列為:v1->v2->v2->v7->v6->v5->v4->v8。圖7-18(c)假設從a開始,相鄰的多個頂點優先選擇ASCII碼小的頂點訪問,其遍歷序列為:a->b->d->e->f->c->g;相鄰的多個頂點優先選擇ASCII碼大的頂點訪問,其遍歷序列為:a->f->e->d->b->g->c。

2.廣度優先遍歷的演算法在廣度優先遍歷中,要求先被訪問的頂點其鄰接點也被優先訪問,因此,必須對每個頂點的訪問順序進行記錄,以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點的訪問順序,將訪問的每個頂點入隊,然後再依次出隊。

在廣度優先遍歷過程中,為了避免重復訪問某個頂點,也需要創建一個一維數組visited[n](n是圖中頂點的數目),用來記錄每個頂點是否已被訪問過。

❻ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊,他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1) 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧,廣度優先遍歷的非遞歸的通用做法是採用隊列。

2) 深度優先遍歷:對每一個可能的分支路徑深入到不能再深入為止,而且每個結點只能訪問一次。要特別注意的是,二叉樹的深度優先遍歷比較特殊,可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下:

先序遍歷:對任一子樹,先訪問根,然後遍歷其左子樹,最後遍歷其右子樹。
中序遍歷:對任一子樹,先遍歷其左子樹,然後訪問根,最後遍歷其右子樹。
後序遍歷:對任一子樹,先遍歷其左子樹,然後遍歷其右子樹,最後訪問根。
廣度優先遍歷:又叫層次遍歷,從上往下對每一層依次訪問,在每一層中,從左往右(也可以從右往左)訪問結點,訪問完一層就進入下一層,直到沒有結點可以訪問為止。

3)深度優先搜素演算法:不全部保留結點,佔用空間少;有回溯操作(即有入棧、出棧操作),運行速度慢。

廣度優先搜索演算法:保留全部結點,佔用空間大; 無回溯操作(即無入棧、出棧操作),運行速度快。

❼ java如何實現 深度優先 廣度優先

下面是我修改了滴源碼,是基於一張簡單的地圖,在地圖上搜索目的節點,依次用深度優先、廣度優先、Dijkstra演算法實現。

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[][]// 地圖數組
{
{ 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 } };

❽ 基本演算法——深度優先搜索(DFS)和廣度優先搜索(BFS)

        深度優先搜索和廣度優先搜索,都是圖形搜索演算法,它兩相似,又卻不同,在應用上也被用到不同的地方。這里拿一起討論,方便比較。

一、深度優先搜索

        深度優先搜索屬於圖演算法的一種,是一個針對圖和樹的遍歷演算法,英文縮寫為DFS即Depth First Search。深度優先搜索是圖論中的經典演算法,利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表,利用拓撲排序表可以方便的解決很多相關的圖論問題,如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止,而且每個節點只能訪問一次。

基本步奏

(1)對於下面的樹而言,DFS方法首先從根節點1開始,其搜索節點順序是1,2,3,4,5,6,7,8(假定左分枝和右分枝中優先選擇左分枝)。

(2)從stack中訪問棧頂的點;

(3)找出與此點鄰接的且尚未遍歷的點,進行標記,然後放入stack中,依次進行;

(4)如果此點沒有尚未遍歷的鄰接點,則將此點從stack中彈出,再按照(3)依次進行;

(5)直到遍歷完整個樹,stack里的元素都將彈出,最後棧為空,DFS遍歷完成。

二、廣度優先搜索

        廣度優先搜索(也稱寬度優先搜索,縮寫BFS,以下採用廣度來描述)是連通圖的一種遍歷演算法這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS,屬於一種盲目搜尋法,目的是系統地展開並檢查圖中的所有節點,以找尋結果。換句話說,它並不考慮結果的可能位置,徹底地搜索整張圖,直到找到結果為止。基本過程,BFS是從根節點開始,沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問,則演算法中止。一般用隊列數據結構來輔助實現BFS演算法。

基本步奏

(1)給出一連通圖,如圖,初始化全是白色(未訪問);

(2)搜索起點V1(灰色);

(3)已搜索V1(黑色),即將搜索V2,V3,V4(標灰);

(4)對V2,V3,V4重復以上操作;

(5)直到終點V7被染灰,終止;

(6)最短路徑為V1,V4,V7.

❾ 實現圖的廣度優先搜索演算法需使用的輔助數據結構是什麼

廣度優先用隊列,深度優先用棧。簡單說明如下:
廣度優先:當一個節點被加入隊列時,要標記為已遍歷,遍歷過程中,對於隊列第一個元素,遍歷其所有能夠能一步達到的節點,如果是標記未遍歷的,將其加入隊列,從第一個元素出發所有能一步直接達到的節點遍歷結束後將這個元素出列。
深度優先:當遍歷到某個節點A時,如果是標記未遍歷,將其入棧,遍歷它能夠一步直接達到的節點,如果是標記未遍歷,將其入棧且標記為已遍歷,然後對其進行類似A的操作,否則找能夠一步直接達到的節點進行類似操作。直到所有能夠一步直接達到的節點都已遍歷,將A出棧。
這里使用「能夠能一步達到的節點」而非「與其相鄰的節點」是考慮到有向圖因素。
具體可以找個圖,然後使用廣度和深度演算法搜索一遍,每步自己手工修改隊列和棧就明白怎麼回事了。

熱點內容
前端android 發布:2025-03-20 06:50:42 瀏覽:93
進制轉換棧c語言 發布:2025-03-20 06:50:31 瀏覽:339
myeclipse不自動編譯了 發布:2025-03-20 06:41:38 瀏覽:777
led汽車大燈和鹵素燈該選哪個配置 發布:2025-03-20 06:40:55 瀏覽:917
sql網校 發布:2025-03-20 06:16:42 瀏覽:279
安卓手機圖標排列為什麼會混亂 發布:2025-03-20 06:16:05 瀏覽:761
手機pin初始密碼是多少 發布:2025-03-20 06:15:59 瀏覽:900
javaif常量變數 發布:2025-03-20 06:15:57 瀏覽:344
iis安裝sql 發布:2025-03-20 06:05:31 瀏覽:149
製作自解壓安裝 發布:2025-03-20 05:41:49 瀏覽:305