C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解

創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比梅江網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式梅江網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋梅江地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴。

輸入一組頂點(diǎn)，建立無(wú)向圖的鄰接矩陣。輸入一組頂點(diǎn)，建立有向圖的鄰接表。分別對(duì)無(wú)向圖和有向圖進(jìn)行DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）。寫出深度優(yōu)先遍歷的遞歸和非遞歸算法。根據(jù)建立的有向圖，判斷該圖是否是有向無(wú)環(huán)圖，若是，則輸出其一種拓?fù)溆行蛐蛄小?/p>

實(shí)現(xiàn)代碼：

#include  
#include  
#define MAX 20 
 
typedef struct ArcNode{ 
  int adjvex; 
  struct ArcNode *nextarc; 
}ArcNode; 
 
typedef struct{ 
  char data; 
  ArcNode *firstarc; 
}AdjList[MAX]; 
 
typedef struct{ 
  AdjList vertices; 
  int vexnum; 
  int arcnum; 
}ALGraph; 
 
typedef struct{ 
  int *base; 
  int front,rear; 
}CqQueue; 
 
void InitQueue(CqQueue &Q) 
{//初始化一個(gè)隊(duì)列 
  Q.base=(int*)malloc(MAX*sizeof(int)); 
  Q.front=Q.rear=0; 
} 
 
int QueueEmpty(CqQueue Q) 
{//判斷隊(duì)列是否為空 
  if(Q.rear==Q.front) 
    return 1; 
  return 0; 
} 
 
void EnQueue(CqQueue &Q,int e) 
{//入隊(duì)操作 
  if((Q.rear+1)%MAX==Q.front) 
    return; 
  Q.base[Q.rear]=e; 
  Q.rear=(Q.rear+1)%MAX; 
} 
 
void DeQueue(CqQueue &Q,int &e) 
{//出隊(duì)操作 
  if(Q.rear==Q.front) 
    return; 
  e=Q.base[Q.front]; 
  Q.front=(Q.front+1)%MAX; 
} 
 
int LocateVex(ALGraph G,char v) 
{//查找頂點(diǎn)v在圖G中的位置 
  for(int i=0;iadjvex=j; 
    s->nextarc=NULL; 
    if(!G.vertices[i].firstarc) 
      G.vertices[i].firstarc=s; 
    else{ 
      p=G.vertices[i].firstarc; 
      while(p->nextarc) 
        p=p->nextarc; 
      p->nextarc=s; 
    } 
    s=(ArcNode*)malloc(sizeof(ArcNode)); 
    s->adjvex=i; 
    s->nextarc=NULL; 
    if(!G.vertices[j].firstarc) 
      G.vertices[j].firstarc=s; 
    else{ 
      p=G.vertices[j].firstarc; 
      while(p->nextarc) 
        p=p->nextarc; 
      p->nextarc=s; 
    } 
  } 
} 
 
int visited[MAX]; 
 
void DFS(ALGraph G,int v) 
{//從頂點(diǎn)v開(kāi)始對(duì)圖G進(jìn)行深度優(yōu)先搜索 
  ArcNode *p; 
  printf("%3c",G.vertices[v].data); 
  visited[v]=1; 
  for(p=G.vertices[v].firstarc;p;p=p->nextarc) 
    if(!visited[p->adjvex]) 
      DFS(G,p->adjvex); 
} 
 
void DFSTraverse(ALGraph G) 
{//對(duì)用鄰接表存儲(chǔ)的無(wú)向圖G進(jìn)行深度優(yōu)先遍歷 
  int v; 
  for(v=0;vnextarc) 
          if(!visited[p->adjvex]){ 
            printf("%3c",G.vertices[p->adjvex].data); 
            visited[p->adjvex]=1; 
            EnQueue(Q,p->adjvex); 
          } 
      } 
    } 
} 
 
int main(){ 
  ALGraph G; 
  printf("建立無(wú)向圖的鄰接表：\n"); 
  CreateAdjList(G); 
  printf("無(wú)向圖的深度優(yōu)先遍歷序列如下：\n"); 
  DFSTraverse(G); 
  printf("\n\n無(wú)向圖的廣度優(yōu)先遍歷序列如下：\n"); 
  BFSTraverse(G); 
  printf("\n"); 
  return 0; 
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之圖的遍歷實(shí)例詳解-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)路徑：http://weahome.cn/article/cosdhj.html