層層遞進-廣度優先搜尋算法

廣度優先搜尋算法常用于通過隊列求最短路徑，下面隻實作了搜尋算法

1、算法思想

廣度優先搜尋算法是通過一層一層的周遊的，周遊思想如下：

1、 選取根節點r

2、 周遊r的子節點，并計算根節點r到子節點的權值，注意的是目前節點的到根節點的權值等于目前節點的父節點到根節點的權值

3、 依次周遊所有節點

4、 所有節點隻能周遊一遍，即當一個節點有兩個父節點時，隻能被一個父節點周遊

例子：先標明1節點，然後會周遊1的子節點2、3，并在周遊的時候計算2、3的權值，2的權值為1，3的權值為5，然後周遊2節點的子節點4、5，計算4、5的節點的權值為，節點4：1+7=8，節點5：1+5=6；之後周遊3節點的子節點，由于5節點已被2節點周遊，那麼隻周遊6号節點即可，最後其他的節點一次類推，直到周遊所有節點。

2、實作代碼

package 搜尋.廣度優先搜尋BFS;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    static int[][] G = {    //圖
            { , , , -, -, -, -, -, - },
            { , , , , , -, -, -, - },
            { , , , -, , , -, -, - },
            { -, , -, , , -, , -, - },
            { -, , , , , , , , - },
            { -, -, , -, , , -, , - },
            { -, -, -, , , -, , ,  },
            { -, -, -, -, , , , ,  },
            { -, -, -, -, -, -, , ,  },
    };

    static boolean[] status = new boolean[];   //是否被選中

    private static BlockingQueue<Node> blockingQueue = new LinkedBlockingQueue<>();     //周遊隊列
    private static List<Node> list = new ArrayList<>();     //儲存節點的資訊
    public static void main(String[] ages){
        Node node = new Node(,,);
        blockingQueue.add(node);
        list.add(node);
        status[] = true;

        while (!blockingQueue.isEmpty()){
            Node node1 = blockingQueue.poll();      // 擷取隊列首元素
            for (int i = ; i < G[node1.n-].length; i++){  //循環目前節點的子節點，并排除周遊過的
                if (G[node1.n-][i] !=  && G[node1.n-][i] != - && !status[i]){
                    Node node2 = new Node(i+, node1.n, node1.s+G[node1.n-][i]);
                    blockingQueue.add(node2);
                    list.add(node2);
                    status[i] = true;
                }
            }
        }
        for (Node node1: list){
            System.out.println(node1.n+"->"+node1.f+"->"+node1.s);
        }
    }
}
class Node{
    int n;   //節點編号
    int f;   //父節點的編号
    int s;   //總權值

    Node(int n, int f, int s){
        this.f =f;
        this.n = n;
        this.s = s;
    }
}

/*
結果
1->0->0
2->1->1
3->1->5
4->2->8
5->2->6
6->3->12
7->4->11
8->5->15
9->7->18
*/