public void bfs(int [,]M,int []visit,int i)
{
Queue<int> q = new Queue<int>();
q.Enqueue(i);
while(q.Count > 0)
{
int temp = q.Dequeue();
for(int j = 0;j < M.GetLength(0);j++)
{
if(M[temp,j] == 1 && visit[j] == 0)
{
visit[j] = 1;
q.Enqueue(j);
}
}
}
}
這是一個C#的簡易BFS模型拆又，實際上是兩個隊列母谎，一個記錄當(dāng)前最新元素，一個記錄是否訪問過
從訪問元素的隊列里取出當(dāng)前最后一個訪問的元素往弓，然后從數(shù)據(jù)源集合循環(huán)取值和是否訪問過得隊列查找旦装，如果沒有页衙，那證明是新元素的臨近點，然后入列阴绢，然后再循環(huán)店乐，以此類推。
private static void bfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Integer> dist,
char start) {
Queue<Character> q = new LinkedList<>();
q.add(start);//將s作為起始頂點加入隊列
dist.put(start, 0);
int i = 0;
while (!q.isEmpty()) {
char top = q.poll();//取出隊首元素
i++;
System.out.println("The " + i + "th element:" + top + " Distance from s is:" + dist.get(top));
int d = dist.get(top) + 1;//得出其周邊還未被訪問的節(jié)點的距離
for (Character c : graph.get(top)) {
if (!dist.containsKey(c))//如果dist中還沒有該元素說明還沒有被訪問
{
dist.put(c, d);
q.add(c);
}
}
}
}
一個JAVA版的BFS旱函。
無權(quán)圖最短路徑.png
其中dist[W]相當(dāng)于之前BFS里的訪問標(biāo)識數(shù)組响巢，初始化時候，可以直接把size設(shè)置成數(shù)據(jù)源長度棒妨，然后全部賦值為非常詭異的數(shù)字比如MAX之類的踪古，這樣很容易判斷含长，是否訪問過。
dist[S]才是正經(jīng)的路徑距離
path[W]就是記錄點
