图采用邻接矩阵为存储结构，其广度优先遍历算法如下：public staticvoid BFs(MatGraphclass g,int v)1 /定义一个队列Queue<Integer>qu=new LinkedList<Integer>();1/访间顶点vSystem.out.print(v+"");1/置已访问标记visited[v]=1;1 /v进队qu.offer(v);1/队列不空循环while（!qu.isEmpty())1/出队顶点V( v=qu.poll();for(int w=o;w<g.n;w++){if (g.edges[v][w]!=0 &&g.edges[v][w]!=g.INF)//存在边<v,W>并且w未访问{ if (visited[w]==0)1/访问顶点W{System.out.print(w+"");1/置已访问标记visited[w]=l;1/W进队qu.offer(w);时间复杂度入为0t11/84
图采用邻接矩阵为存储结构，其广度优先遍历算法如下： public static void BFS(MatGraphClass g,int v) { Queue<Integer> qu=new LinkedList<Integer>(); //定义一个队列 System.out.print(v+" "); //访问顶点v visited[v]=1; //置已访问标记 qu.offer(v); //v进队 while (!qu.isEmpty()) //队列不空循环 { v=qu.poll(); //出队顶点v for (int w=0;w<g.n;w++) { if (g.edges[v][w]!=0 &&g.edges[v][w]!=g.INF) { if (visited[w]==0) //存在边<v,w>并且w未访问 { System.out.print(w+" "); //访问顶点w visited[w]=1; //置已访问标记 qu.offer(w); //w进队 } } } } } 时间复杂度为O(n 2)。 11/84
（a）一个有向图G4（b）图G.的邻接表BFS:01253412/84
1 4 0 2 3 5 （b）图G4的邻接表 0 v0 1 1 v1 5 ∧ 2 v2 3 3 v4 ∧ （a）一个有向图G4 2 ∧ 4 5 ∧ 5 v5 ∧ 4 v3 3 ∧ BFS: 0 1 2 5 3 4 1 4 0 2 3 5 12/84
理解广度优先遍历过程13/84
14 0 2 35 0 v 0 1 1 v 1 5 ∧ 2 v 2 3 3 v 4 ∧ 2 ∧ 4 5 ∧ 5 v 5 ∧ 4 v 3 3 ∧ 1 3 0 2 5 4 13/84
起始点0到图中其他顶点的路径长度：BFS:0125344→3→说明类似树的层次遍历。14/84
0 0 → 1 0 → 2 0 → 1 → 5 0 → 2 → 5 0 → 2 → 3 0 → 2 → 4 0 → 2 → 4 → 3 起始点0到图中其他顶点的路径长度： BFS: 0 1 2 5 3 4 说明 类似树的层次遍历。 1 3 0 2 5 4 14/84
8.3.4非连通图的遍历无向图连通图：一次遍历能够访问到图中的所有顶点。非连通图：一次遍历只能访问到起始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择起始点，分别进行遍历，才能够访问到图中的所有顶点。15/84
连通图：一次遍历能够访问到图中的所有顶点。 非连通图：一次遍历只能访问到起始点所在连通分量中的所有顶点， 其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通 分量中选择起始点，分别进行遍历，才能够访问到图中的所有顶点。 无向图 1 3 5 2 4 6 0 15/84