网络工程师考点：图的深度及广度遍历

深度广度遍历：

// ----------------------- 深度及广度优先遍历 -------------------------

// 对已经访问的顶点做标记
int visited[MAX_VERTEX_NUM];

// 深度优先遍历的递归函数DFS()
void DFS(AMLGraph &G,int v){
  int w;
  cout< ";
  visited[v]=TRUE;
  for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
    if(visited[w]!=TRUE){
      DFS(G,w);
    }
  }
}

// 深度优先遍历图
void DFSTraverse(AMLGraph &G){
  int i;
  cout<<"\nDFSTraverse--------------------\n\n";
  for(i=0;i    visited[i]=FALSE;
  }
  for(i=0;i    if(!visited[i]){
      DFS(G,i);
      cout<<"NULL\n";
    }
  }
  cout<<"\nDFSTraverse--------------------\n\n";
}

// 广度优先遍历图
void BFSTraverse(AMLGraph &G){
  int v,w,i;
  LinkQueue Q;
  InitQueue(Q);
  cout<<"\nBFSTraverse--------------------\n\n";
  for(v=0;v    visited[v]=FALSE;
  }
  for(i=0;i    if(!visited[i]){
      visited[i]=TRUE;
      cout< ";
      EnQueue(Q,i);
      while(!QueueEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){
          if(!visited[w]){
            visited[w]=TRUE;
            cout< ";
            EnQueue(Q,w);
          }
        }
      }
      cout<<"NULL\n";
    }
  }
  cout<<"\nBFSTraverse--------------------\n\n";
}


void main(){
  AMLGraph G;
  char *edges;
  // 输入边序列，每条边的两个顶点依次输入
  edges="98817565636051434230212010";
  // 建立图，顶点数为10，边数为13，边序列为edges
  createAMLGraph(G,10,13,edges);
  PrintGraph(G);
  DFSTraverse(G);
  BFSTraverse(G);
}