有向图有向图，若从起始点到图中的其他每个顶点都有路径，则能够访问到图中的所有顶点。否则不能访问到所有顶点，为此同样需要再选起始点，继续进行遍历，直到图中的所有顶点都被访问过为止。16/84
有向图，若从起始点到图中的其他每个顶点都有路径，则能够访问到 图中的所有顶点。 否则不能访问到所有顶点，为此同样需要再选起始点，继续进行遍历， 直到图中的所有顶点都被访问过为止。 有向图 1 2 3 0 4 5 16/84
非连通图采用邻接表存储结构，其深度优先遍历算法如下：public static voidDFSA（AdjGraphclass G）//非连通图的DFs//visited数组元素均置为0Arrays.fill(visited,o);for (int i=o;i<G.n;i++)if (visited[i]==0)DFS(G,i);/从顶点i出发深度优先遍历17/84
public static void DFSA(AdjGraphClass G) //非连通图的DFS { Arrays.fill(visited,0); //visited数组元素均置为0 for (int i=0;i<G.n;i++) if (visited[i]==0) DFS(G,i); //从顶点i出发深度优先遍历 } 非连通图采用邻接表存储结构，其深度优先遍历算法如下： 17/84
非连通图采用邻接表存储结构，其广度优先遍历算法如下：public static voidBFSA（AdjGraphclass G）//非连通图的BFs//visited数组元素均置为0Arrays.fill(visited,o);for (int i=o;i<G.n;i++)if (visited[i]==0)BFS(G,i);/从顶点i出发广度优先遍历18/84
public static void BFSA(AdjGraphClass G) //非连通图的BFS { Arrays.fill(visited,0); //visited数组元素均置为0 for (int i=0;i<G.n;i++) if (visited[i]==0) BFS(G,i); //从顶点i出发广度优先遍历 } 非连通图采用邻接表存储结构，其广度优先遍历算法如下： 18/84
【例8.5】假设图采用邻接表存储，设计一个算法，判断一个无向图是否连通。若连通则返回true；否则返回false。public static void DFsi(AdjGraphclass G,int v)//图G从V出发的深度优先遍历( int w;ArcNode p;1/置已访间标记visited[v]=1;//p指向顶点v的第一个邻接点p=G.adjlist[v].firstarc;while(p!=null)(w=p.adjvex;if(visited[w]==0)若W顶点未访问，递归访问它DFS1(G,w);//p置为下一个邻接点p=p.nextarc;19/84
【例8.5】假设图采用邻接表存储，设计一个算法，判断一个无向图 是否连通。若连通则返回true；否则返回false。 public static void DFS1(AdjGraphClass G,int v) //图G从v出发的深度优先遍历 { int w; ArcNode p; visited[v]=1; //置已访问标记 p=G.adjlist[v].firstarc; //p指向顶点v的第一个邻接点 while (p!=null) { w=p.adjvex; if (visited[w]==0) DFS1(G,w); //若w顶点未访问,递归访问它 p=p.nextarc; //p置为下一个邻接点 } } 19/84
public static boolean Connect(AdjGraphclass G)/判断无向图G的连通性boolean flag=true;//visited数组元素均置为0Arrays.fill(visited,o);DFS1(G,0);//调用DSF1算法，从出发深度优先遍历for (int i=o;i<G.n;i++)if (visited[i]==0)二存在没有访问的顶点，则不连通{ flag=false;break;好return flag;20/84
public static boolean Connect(AdjGraphClass G) //判断无向图G的连通性 { boolean flag=true; Arrays.fill(visited,0); //visited数组元素均置为0 DFS1(G,0); //调用DSF1算法,从0出发深度优先遍历 for (int i=0;i<G.n;i++) if (visited[i]==0) { flag=false; //存在没有访问的顶点，则不连通 break; } return flag; } 20/84