生活随笔
收集整理的這篇文章主要介紹了
广度优先搜索_计算机入门必备算法——广度优先遍历搜索
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
1、? 序言
又很久沒有學習了，上次學到哈希表又稱散列表的相關知識，這次我們學習一種新的數據結構來建立網絡模型。這種數據結構被稱作圖。首先，我們先應該先了解一下什么是圖，其次學習第一種圖的算法，這種圖的算法被稱作是廣度優先搜索算法(breadth-first search ,BFS)。
???????? 廣度優先搜索算法其實就是幫助你找出兩樣東西之間的最短距離，掌握了這種算法之后，我們可以完成以下幾項內容：
--------此示例來源于《算法圖解》
2、? 圖簡介
聽說戶縣到咸陽的大巴已經停運了，那么我們去咸陽的話就需要重新計算路線，(我們暫時排除自駕到咸陽的路線)假設我們乘坐公共交通工具前往，并且希望中間的換乘最少，可以到達的部分交通線路如下：
??我們從圖中可以發現想從石油大學直接到達咸陽湖景區，除了自駕其它并不能一步到達景區，接著我們使用兩步、三步、四步發現都不能直接到達景區，最少也得需要五步，路線為：從石油大學東門(周南站)乘坐101路到鄠邑站，然后乘坐動車到達阿房宮站，然后乘坐1061路到達灃東第一學校站，接著換成咸陽郭杜線到達統一廣場站，最終不步行到達咸陽湖景區。當然還有其他到達景區的路線，但它們執行起來路程會更遠。這個算法發現，前往咸陽湖景區需要五步，這種問題在專業上稱為“最短路徑問題(shorterest-path problem)”。解決最短路徑的問題的算法被稱為廣度優先搜索。
就像上圖一樣，我們將路線用圖解的形式展現出來，這就是圖！其實非常簡單，圖由節點和邊組成。一個節點可能與眾多節點直接相連，這些眾多節點都被稱為這個節點的鄰節點，在上圖，大十字站和亞迪路站都被稱為郭寨橋站的鄰節點。
??一句話概括起來：圖用于模擬不同的東西是如何相連的。
3、? 廣度優先搜索
??廣度優先搜索算法是一種可用于圖的查找算法，可以幫助回答兩類問題：
??????????從節點A出發，有前往節點B的路徑嗎？
??從節點A出發，前往節點B的哪條路徑最短？
舉個例子，假設你經營著一個果園，每年秋天果子成熟了你需要將蘋果賣給他。在微信上，你在好友列表中去找這么一個人。這種查找很簡單，只需每看到一個人，然后想想他是不是收蘋果的。
假設你沒有朋友是收蘋果的，那么就必須在朋友的朋友中進行查找。然后問到信息之后立馬把他記在小本本上，這樣一來，不僅需要在朋友中進行查找，還需要在朋友的朋友中查找。如果你當前看到的朋友并不是收蘋果的，就將其加入小本本里，這就意味著你將在他的人際關系中進行查找。這種算法最終會將你整個人際關系網進行搜索，直到找到蘋果經銷商，這就是廣度優先搜索算法。
? 在剛才的例子中，我們先從自己的朋友開始找起，后來從朋友的朋友繼續查找，自己朋友稱為一度關系，朋友的朋友稱為二度關系，顯然，一度關系優于二度關系。
?????搜索時，肯定是先自己的朋友，其次是朋友的朋友。當然只有按添加順序查找時，才能達到搜索的目的。舉個例子，張三是自己的朋友，李四是張三的朋友，但是李四先添加到名單中時，假設張三和李四都是收蘋果的，但是由于添加順序不對，必定會先搜索李四，然后再搜索張三，這樣的話只是搜索到了蘋果經銷商，但沒搜索到最近的朋友。
? 別忘了廣度優先搜索需要解決兩個問題：第一個是存在嗎？第二個是最短嗎？
????但是這種按照順序存儲的數據結構竟然存在，它的專業術語叫做“隊列”。
? 數據結構的隊列就如同我們吃飯排隊，秉承先來后到的原則，先到的先吃飯。隊列類似于棧，你不能隨機地訪問隊列中的元素，隊列只支持兩種操作：入隊和出隊。
? 隊列是一種先進先出的數據結構(First in First Out，FIFO)
3、? 代碼實現
package cn.yanhao.breadthfirstsearch;/**
??* 定義圖類*/public class Graph
?{private final int ?Max_VERTS = 6;?? //圖中頂點的個數private Vertex vertexList[];??????? //用來存儲頂點的數組//用鄰接矩陣來存儲邊，數組元素表示沒有邊界，1表示有邊界private ?int adjMat[][];private int nVerts;???????? //頂點個數private QueueX queue;?????? //用隊列實現廣度優先搜索/*頂點類
????? */class Vertex{public char label;public boolean wasVisited;public Vertex(char label){this.label ?= label;wasVisited = false;
???????? }
???? }
???? Graph(){//頂點數組長度初始化為20vertexList = new Vertex[Max_VERTS];//初始化20x20矩陣adjMat ?= new int[Max_VERTS][Max_VERTS];nVerts = 0; //初始化頂點個數為0
???? ????//初始化鄰接矩陣所有元素都為0，即所有頂點沒有邊for (int i = 0; i ?< Max_VERTS; i++) {for (int j = 0; j ?< Max_VERTS; j++) {adjMat[i][j] ?= 0;
???????????? }
???????? }queue = new QueueX();
???? }//將頂點添加到數組中，是否訪問位置置為wasVisited ?= false(未訪問)public ?void addVertex(char lab){//先添加在加1vertexList[nVerts++] = new Vertex(lab);
???? }//用鄰接矩陣表示邊，是對稱的，兩部分都要賦值public ?void addEdge(int start,int end){adjMat[start][end] ?= 1;adjMat[end][start] ?= 1;
???? }//打印某個頂點表示的值public ?void displayVertex(int v){
???????? System.out.print(vertexList[v].label+"");
???? }//找到與某一頂點鄰接且未被訪問的頂點public ?int getAdjUnvisitedVertex(int v){for (int i = 0; i ?< nVerts; i++) {//v頂點與i頂點相鄰且未被訪問if(adjMat[v][i] ?== 1 && vertexList[i].wasVisited ?== false){return i;
???????????? }
???????? }return -1;
???? }/**
????? * 廣度優先搜索* 1、用remove方法檢查棧頂* 2、試圖找到這個頂點還未被訪問的鄰接點* 3、如果沒有找到，該頂點出列* 4、如果找到這樣的頂點，訪問這個頂點，并把它放入隊列中*/public void breadthFirstSearch()
???? {//第一個頂點可訪問vertexList[0].wasVisited ?= true;//打印第一個頂點的值displayVertex(0);//隊列插入第一個元素queue.insert(0);int v2;//如果隊列不為空while(!queue.isEmpty()){int v1 = queue.remove();while ((v2 = ?getAdjUnvisitedVertex(v1)) != -1){vertexList[v2].wasVisited ?= true;
???????????????? displayVertex(v2);queue.insert(v2);
???????????? }
???????? }//搜索完畢，初始化，便于下次搜索for (int i = 0; i ?< nVerts; i++) {vertexList[i].wasVisited ?= false;
???????? }
???? }public static ?void main(String[] args) {
???????? Graph graph = new Graph();
???????? graph.addVertex('A');
???????? graph.addVertex('B');
???????? graph.addVertex('C');
???????? graph.addVertex('D');
???????? graph.addVertex('E');
???????? graph.addEdge(0,1);???? //ABgraph.addEdge(1,2);???? //BCgraph.addEdge(0,3);???? //ADgraph.addEdge(3,4);???? //DESystem.out.println("廣度優先搜索算法：");
???????? graph.breadthFirstSearch();
???? }
?} |
總結
以上是生活随笔為你收集整理的广度优先搜索_计算机入门必备算法——广度优先遍历搜索的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
