演算法——廣度優先搜索

03-31

概念：

"廣度優先搜索"是一種通過逐層遍歷所有訪問對象，從而找到通過最短節點數到達目標的演算法。

學習準備：

學習前，需要先掌握圖（Graph）、隊列（queue）、棧（stack）的概念。還得了解「鄰接矩陣」的用法。

示例：

在下圖（graph）中，找到從A點到G點的最短距離。

廣度優先演算法的搜索方式：通過逐層遍歷所有相鄰節點，從而暴力的找出最短路徑。如下圖：

代碼演示：

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Collections;//調用queue的時候需要該名稱空間namespace 廣度優先搜索{ class nodeClass { public string nodeName; public bool isVisited; public nodeClass(string name)//類的構造器 { nodeName = name; } } class Gragh { const int nodeNumMax = 10; nodeClass[] nodes = new nodeClass[nodeNumMax];//節點數組 int[,] adjmatrix = new int[nodeNumMax, nodeNumMax]; int nodeNumNow = 0;//統計當前有幾個節點數 public Gragh()//利用類構造器的優先機制，首先初始化圖的關係矩陣 { for (int i = 0; i < nodeNumMax; i++) { for (int j = 0; j < nodeNumMax; j++) { adjmatrix[i, j] = 0; } } } public void addNode(string newNodeName) { nodes[nodeNumNow] = new nodeClass(newNodeName); nodeNumNow++; } public void addEdge(int nodeNum1, int nodeNum2) { adjmatrix[nodeNum1, nodeNum2] = 1; } public void displayNode(int nodePosition) { Console.WriteLine(nodes[nodePosition].nodeName); } public int visiteNode(int oneNode)//檢查某節點是否還有未訪問過的相鄰節點。 { for (int j = 0; j < nodeNumMax; j++) { if (adjmatrix[oneNode, j] == 1 && nodes[j].isVisited == false) return j; } return -1; } public void 廣度優先搜索() { //創建隊列，以方便實現自動搜索。 Queue nodeQueue = new Queue(); //訪問第一個節點 nodes[0].isVisited = true; displayNode(0); nodeQueue.Enqueue(0); //訪問之後的節點 int node1; int node2; while (nodeQueue.Count > 0 && nodes[nodeNumNow - 1].isVisited != true)//除了判斷節點以外，新加了一個判斷，當最後一個節點被訪問了以後，整個循環就停止 { node1 = (int)nodeQueue.Dequeue();//將隊列中的第一個節點彈出，並記錄。 node2 = visiteNode(node1);//尋找節點1指向的節點。 while (node2 != -1 && nodes[nodeNumNow - 1].isVisited != true) { Console.WriteLine(nodes[node1].nodeName + "=>" + nodes[node2].nodeName);//顯示哪個節點指向哪個節點。 //廣度優先搜索，首先就是把與第一個點相鄰的點全部找出來，儲存在queue裡面。 nodeQueue.Enqueue(node2); nodes[node2].isVisited = true; displayNode(node2); node2 = visiteNode(node1); } } } //重置所有被訪問過的節點 public void resetNode() { for (int i = 0; i < nodeNumMax; i++) { nodes[i].isVisited = false; } } } class Program { static void Main(string[] args) { Gragh graphInstance = new Gragh(); //添加節點 graphInstance.addNode("A");//編號0 graphInstance.addNode("B");//編號1 graphInstance.addNode("C");//編號2 graphInstance.addNode("E");//編號3 graphInstance.addNode("D");//編號4 graphInstance.addNode("F");//編號5 graphInstance.addNode("G");//編號6 graphInstance.addNode("H");//編號7 //添加邊 graphInstance.addEdge(0, 1);//A=>B graphInstance.addEdge(0, 2);//A=>C graphInstance.addEdge(1, 4);//B=>D graphInstance.addEdge(4, 2);//D=>C graphInstance.addEdge(2, 3);//C=>E graphInstance.addEdge(4, 5);//D=>F graphInstance.addEdge(3, 5);//E=>F graphInstance.addEdge(5, 6);//F=>G graphInstance.addEdge(0, 0);//G=>H graphInstance.addEdge(2, 7);//C=>H graphInstance.廣度優先搜索(); } }}