C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例

更新時(shí)間：2022年06月06日 17:28:21 作者：拆掉思維的墻

這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

一、實(shí)驗(yàn)?zāi)康?/h2>
理解圖的基本概念，掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷算法與廣度優(yōu)先搜索遍歷算法。

二、實(shí)驗(yàn)內(nèi)容

利用鄰接矩陣描述示例圖，編寫程序輸出示例圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷序列。

具體步驟如下：

將圖的鄰接矩陣描述為一個(gè)二維數(shù)組，并將該數(shù)組定義為全局變量，以便數(shù)據(jù)的傳遞；
定義一個(gè)隊(duì)列，在廣度優(yōu)先搜索時(shí)，該隊(duì)列存儲(chǔ)已被訪問(wèn)的路徑長(zhǎng)度為1，2，…的頂點(diǎn)；
定義訪問(wèn)函數(shù)visit()、深度優(yōu)先搜索函數(shù)DFS()和廣度優(yōu)先搜索函數(shù)BFS()；
主函數(shù)實(shí)現(xiàn)各函數(shù)的調(diào)用。

三、實(shí)驗(yàn)工具

Dev-C++

四、實(shí)驗(yàn)代碼

//Authors:xiaobei
#include<stdio.h>
#include<stdlib.h>
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
//定義圖結(jié)構(gòu)
typedef struct{
 VerTexType vexs[MVNum];
 ArcType arcs[MVNum][MVNum];
 int vexnum,arcnum;
}AMGraph;
//定義輔助鏈隊(duì)
typedef struct QNode{
 char data;
 struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
 QueuePtr front;
 QueuePtr rear;
}LinkQueue;
//定義全局輔助數(shù)組visited[MVNum]
int visited[MVNum];
//函數(shù)返回定點(diǎn)下標(biāo)
int LocateVex(AMGraph G,char v){
 int i;
 for(i=0;i<G.vexnum;i++)
  if(G.vexs[i]==v)
   return i;
  return -1;
}
//函數(shù)訪問(wèn)并輸出頂點(diǎn)，返回下標(biāo)
int visit(AMGraph G,char v){
 int i;
 for(i=0;i<G.vexnum;i++)
  if(v==G.vexs[i])
   printf("%c",v);
 return LocateVex(G,v);
}
//函數(shù)創(chuàng)建無(wú)向圖，以鄰接矩陣形式
int CreateUDN(AMGraph &G){
 int i,j,k,v1,v2,w;
 printf("[輸入總頂點(diǎn)數(shù)和邊數(shù):]\n>>>");
 scanf("%d %d",&G.vexnum,&G.arcnum);
 for(i=0;i<G.vexnum;i++)
 {
  getchar();
  printf("[依次輸入各頂點(diǎn)的信息:]\n>>>");
  scanf("%c",&G.vexs[i]);
 }
 for(i=0;i<G.vexnum;i++)
  for(j=0;j<G.vexnum;j++)
   G.arcs[i][j] = MaxInt;
 for(k=0;k<G.arcnum;k++){
  getchar();
  printf("[輸入一條邊依附的頂點(diǎn)及權(quán)值:]\n>>>"); 
  scanf("%c %c %d",&v1,&v2,&w);
  i = LocateVex(G,v1);
  j = LocateVex(G,v2);
  G.arcs[i][j]=w;
  G.arcs[j][i]=G.arcs[i][j];
 }
 return 1;
}
//函數(shù)深度遍歷連通圖
void DFS_AM(AMGraph G,char v){
 int w,u;
 u = visit(G,v);
 visited[u] = 1;
 for(w=0;w<G.vexnum;w++){
  if((G.arcs[u][w]<MaxInt) && (!visited[w]))
   DFS_AM(G,G.vexs[w]);
 }
}
//函數(shù)初始化鏈隊(duì)
void InitQueue(LinkQueue &Q){
 Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));
 Q.front->next=NULL;
}
//函數(shù)數(shù)據(jù)進(jìn)隊(duì)
void EnQueue(LinkQueue &Q,char e){
 QueuePtr p;
 p = (QNode*)malloc(sizeof(QNode));
 p->data = e;
 p->next = NULL;
 Q.rear->next=p;
 Q.rear = p;
}
//函數(shù)數(shù)據(jù)出隊(duì)
void DeQueue(LinkQueue &Q,char &e){
 QueuePtr p;
 if(Q.front==Q.rear);
 else
 {
  p = Q.front->next;
  e = p->data;
  Q.front->next = p->next;
  if(Q.rear==p)
   Q.rear=Q.front;
  free(p);
 }
}
//函數(shù)判斷鏈隊(duì)是否為空
int QueueEmpty(LinkQueue Q){
 if(Q.front==Q.rear)
  return 1;
 else
  return 0;
}
//函數(shù)返回頂點(diǎn)下一個(gè)鄰接點(diǎn)下標(biāo)
int FirstAdjVex(AMGraph G,int c){
 int j;
 for(j=0;j<G.vexnum;j++)
  if(G.arcs[c][j]<MaxInt && visited[j]==0)
   return j;
  return -1;
}
//函數(shù)返回頂點(diǎn)下一個(gè)相對(duì)鄰接點(diǎn)下標(biāo)
int NextAdjVex(AMGraph G,int c,int w){
 int j;
 for(j=0;j<G.vexnum;j++)
  if(G.arcs[c][j]<MaxInt && visited[j]==0)
   return j;
  return -1;
}
//函數(shù)廣度遍歷連通圖
void BFS_AM(AMGraph G,char v){
 int c,w,i;
 char u;
 LinkQueue Q;
 c = visit(G,v);
 visited[c] = 1;
 InitQueue(Q);
 EnQueue(Q,v);
 while(!QueueEmpty(Q)){
  DeQueue(Q,u);
  c = LocateVex(G,u);
  for(w=FirstAdjVex(G,c);w>=0;w=NextAdjVex(G,c,w))
  {
   if(!visited[w]){
    i = visit(G,G.vexs[w]);
    visited[i] = 1;
    EnQueue(Q,G.vexs[w]);
   }
  }
 }
}
//菜單打印
void Menu(){
 printf("\n————————菜單————————\n");
 printf("\n1.創(chuàng)建圖結(jié)構(gòu);\n");
 printf("\n2.深度遍歷（DFS）;\n");
 printf("\n3.廣度遍歷（BFS）;\n");
 printf("\n0.退出;\n");
 printf("\n——————————————————\n");
 printf("[請(qǐng)輸入你的選擇:]\n>>>");
}
//主函數(shù)
int main(){
 int i,user;
 char v;
 AMGraph G;
 while(1){
  Menu();
  scanf("%d",&user);
  switch(user){
  case 1:{
   CreateUDN(G);
   break;
  }
  case 2:{
   //初始化輔助數(shù)組
   for(i=0;i<G.vexnum;i++)
    visited[i] = 0;
   printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>");
   getchar();
   scanf("%c",&v);
   DFS_AM(G,v);
   break;
  }
  case 3:{
   //初始化輔助數(shù)組
   for(i=0;i<G.vexnum;i++)
    visited[i] = 0;
   printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>");
   getchar();
   scanf("%c",&v);
   BFS_AM(G,v);
   break;
  }
  case 0:{
   exit(0);
   break;
  }
  }
 }
 return 0;
}

五、實(shí)驗(yàn)結(jié)果

六、總結(jié)與思考

無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖鄰接矩陣可能不對(duì)稱。
深度優(yōu)先搜索類似于棧結(jié)構(gòu)的出棧于入棧過(guò)程，模擬遞歸，其實(shí)遞歸也是通過(guò)堆棧的形式實(shí)現(xiàn)的。
廣度遍歷是非遞歸過(guò)程，借助隊(duì)列來(lái)實(shí)現(xiàn)。
輔助數(shù)組需要在全局使用，在主函數(shù)外定義。
DFS與BFS空間復(fù)雜度都是O（n）,鄰接矩陣時(shí)間復(fù)雜度都是O（n2），鄰接表時(shí)間復(fù)雜度為O（n+e）。

鄰接矩陣示意圖：

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建遍歷的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: