網(wǎng)絡(luò)工程師考點：圖的深度及廣度遍歷

深度廣度遍歷：

// ----------------------- 深度及廣度優(yōu)先遍歷 -------------------------

// 對已經(jīng)訪問的頂點做標(biāo)記
int visited[MAX_VERTEX_NUM];

// 深度優(yōu)先遍歷的遞歸函數(shù)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);
    }
  }
}

// 深度優(yōu)先遍歷圖
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";
}

// 廣度優(yōu)先遍歷圖
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";
  // 建立圖，頂點數(shù)為10，邊數(shù)為13，邊序列為edges
  createAMLGraph(G,10,13,edges);
  PrintGraph(G);
  DFSTraverse(G);
  BFSTraverse(G);
}