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模型，实际上是两个队列，一个记录当前最新元素，一个记录是否访问过
从访问元素的队列里取出当前最后一个访问的元素，然后从数据源集合循环取值和是否访问过得队列查找，如果没有，那证明是新元素的临近点，然后入列，然后再循环，以此类推。
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;//得出其周边还未被访问的节点的距离
for (Character c : graph.get(top)) {
if (!dist.containsKey(c))//如果dist中还没有该元素说明还没有被访问
{
dist.put(c, d);
q.add(c);
}
}
}
}
一个JAVA版的BFS。
无权图最短路径.png
其中dist[W]相当于之前BFS里的访问标识数组，初始化时候，可以直接把size设置成数据源长度，然后全部赋值为非常诡异的数字比如MAX之类的，这样很容易判断，是否访问过。
dist[S]才是正经的路径距离
path[W]就是记录点
