图的遍历

深度优先遍历

DFS

每一次访问某个顶点的时候判断该结点是否背访问过

设置访问标志

设置一个一维数组

初始化为假

void DFSTtaverse(Graph G Status(*Visit)(int v))

{ 

  VisitFunc=Visit;

  for(v=0;i<G.vexnum;++v)

   visit[v]=false;

 for(v=0,v<G.vexnum;++v)

  if(!visit[v])

   DFS(G，v);

} 

  void DFS(G,v)

{  visit[v]=true;VisitFunc(v);

   for(w=FisrtAdjVex(G,v)；w!=0;w=NextAdjVex(G,v,w))

 if(!visit[w]) DFS(G.w);

}

所得到的树就是深度优先生成树

先跟遍历得到

BFS  广度优先搜索遍历

从V0出发

访问所有邻接点

按照访问邻接点的顺序访问邻接点的所有邻接点

广度优先生成树

广度优先生成森林

与逻辑结构有关

void BFSTraverse(G Graph ,Status (*Visit(int v)))

{
  for(v=0;v<G.vexnum;v++)  visit[v]=false;

  IninQueue(Q); if(!visit[v])

  EnQueue(Q,v);

 visit[v]=true;Visit(v)

 while(!QueueEmpty(Q))

   {

     DeQueue(Q,u);

  for (w=