亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定

算法學習java-廣度優先搜索算法(BFS)

最近在学习算法,刚开始简单的时候有很多的例子和大神们写的博客可以参考,到后面越来难得时候虽然也有很多的博客可以参考,但自己水平有限,对c++不太了解,也不能为了学算法先把c++语言再学一遍。今天终于把这个拿下来了

广度优先搜索算法

广度优先搜索算法是先访问图中的一个节点,然后再访问所有和它相邻的符合条件的节点依次往后直到访问完图中所有的节点。

这些理论知识网上一搜都是一大把,就不详细赘述了。

/*
 *访问所有数组里的值
 */
import java.util.LinkedList;
import java.util.Queue;

public class 广度优先搜索算法 {
    private int r=4;//行
    private int c=4;//列
    //数组
    private int[][] graph=new int[][]{{1,2,3,4},
                                        {5,6,7,8},
                                        {9,10,11,12},
                                        {13,14,15,16}};
    private int[][] gr=new int[r][c];//标记
    int[][] rc=new int[][]{{0,-1},{-1,0},{0,1},{1,0}};//左上右下,四个方向
    public static void main(String[] args) {
        new 广度优先搜索算法().BFS();
    }
    //方法内部类,定义数据结构
    class Node{
        int r;//行
        int c;//列
        int k;//第几波被访问的
        Node(int r,int c,int k){
            this.r=r;
            this.c=c;
            this.k=k;
        }
    }
    private void BFS() {
        // TODO Auto-generated method stub
        Node node=new Node(0,0,0);//初始化,从0,0开始,
        gr[0][0]=1;//0,0默认已访问过
        Queue<广度优先搜索算法.Node> que=new LinkedList<广度优先搜索算法.Node>();//初始化队列
        que.offer(node);//把初始化过的node传入队列
        while (!que.isEmpty()) {
            Node tem=que.poll();//获取并移除队列头
            for(int i=0;i<4;i++){//循环四次,四个方向
                int newr=tem.r+rc[i][0];//新的行
                int newc=tem.c+rc[i][1];//新的列
                if(newr<0||newc<0||newr>=r||newc>=c)continue;//如果新的行和列超出范围就跳过这次循环
                if(gr[newr][newc]!=0)continue;//如果新的节点已被访问也跳过此次循环
                gr[newr][newc]=1;//标记当前节点已被访问
                que.offer(new Node(newr,newc,tem.k+1));//加入队列
                //输出遍历到数组的值
                System.out.println(graph[newr][newc]+" "+(tem.k+1));
            }
        }
    }
}

运行结果
图片描述

點擊查看更多內容
3人點贊

若覺得本文不錯,就分享一下吧!

評論

作者其他優質文章

正在加載中
感謝您的支持,我會繼續努力的~
掃碼打賞,你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃,即可進行掃碼打賞哦
今天注冊有機會得

100積分直接送

付費專欄免費學

大額優惠券免費領

立即參與 放棄機會
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號

舉報

0/150
提交
取消