DFS:015 23 46/84
1 4 0 2 3 5 1 4 0 2 3 5 0 v0 1 1 v1 5 ∧ 2 v2 3 3 v3 ∧ 2 ∧ 4 5 ∧ 5 v5 ∧ 4 v4 3 ∧ DFS: 0 1 5 2 3 4 6/84
理解深度优先遍历过程7/84
14 0 2 35 0 v 0 1 1 v 1 5 ∧ 2 v 2 3 3 v 3 ∧ 2 ∧ 4 5 ∧ 5 v 5 ∧ 4 v 4 3 ∧ 1 3 0 2 5 4 7/84
起始点到图中其他顶点的路径长度：DFS:0152344→3说明类似树的先根遍历。8/84
0 0 → 1 0 → 1 → 5 0 → 2 0 → 2 → 5 0 → 2 → 3 0 → 2 → 4 0 → 2 → 4 → 3 起始点0到图中其他顶点的路径长度： DFS: 0 1 5 2 3 4 说明 类似树的先根遍历。 1 3 0 2 5 4 8/84
8.3.3广度优先遍历首先访问起始点V。接着访问顶点v的所有未被访问过的邻接点V1、V2、…、Vt。然后再按照v1、V2、…、Vt的次序，访问每一个顶点的所有未被访问过的邻接点。依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已访问顶点的邻接点都被访问过为止。队列相邻顶点：先访问先处理9/84
首先访问起始点v。 接着访问顶点v的所有未被访问过的邻接点v1、v2、.、vt。 然后再按照v1、v2、.、vt的次序，访问每一个顶点的所有未被访问 过的邻接点。 依次类推，直到图中所有和初始点v有路径相通的顶点或者图中所有已 访问顶点的邻接点都被访问过为止。 相邻顶点：先访问先处理 9/84
图采用邻接表为存储结构，其广度优先遍历算法如下：public static void BFs(AdjGraphclass G,int vArcNode p; int w;//定义一个队列Queue<Integer>qu=newLinkedList<Integer>();1/访问顶点VSystem.out.print(v+"");1/置已访问标记visited[v]-1;1/v进队qu.offer(v);while(!qu.isEmpty())1/队列不空循环//出队顶点Vv=qu.pol1();//找顶点v的第一个邻接点p=G.adjlist[v].firstarc;while (p!=null) w=p.adjvex;1/若v的邻接点w未访问if(visited[w]==0)1/访问顶点w{System.out.print(w+"");1/置已访标记visited[w]=1;1 /w进队qu.offer(w);1/找下一个邻接顶点p=p.nextarc;10/84时间复杂度为o（n+e）
图采用邻接表为存储结构，其广度优先遍历算法如下： public static void BFS(AdjGraphClass G,int v) { ArcNode p; int w; 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 p=G.adjlist[v].firstarc; //找顶点v的第一个邻接点 while (p!=null) { w=p.adjvex; if (visited[w]==0) //若v的邻接点w未访问 { System.out.print(w+" "); //访问顶点w visited[w]=1; //置已访问标记 qu.offer(w); //w进队 } p=p.nextarc; //找下一个邻接顶点 } } } 时间复杂度为O(n+e)。 10/84