C語言數據結構圖如何創建與遍歷

本篇內容介紹了“C語言數據結構圖如何創建與遍歷”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

一、 實驗目的

理解圖的基本概念，掌握圖的存儲結構，實現圖的深度優先搜索遍歷算法與廣度優先搜索遍歷算法。

二、 實驗內容

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

具體步驟如下：

• 將圖的鄰接矩陣描述為一個二維數組，并將該數組定義為全局變量，以便數據的傳遞；

• 定義一個隊列，在廣度優先搜索時，該隊列存儲已被訪問的路徑長度為1，2，…的頂點；

• 定義訪問函數visit()、深度優先搜索函數DFS()和廣度優先搜索函數BFS()；

• 主函數實現各函數的調用。

三、 實驗工具

Dev-C++

四、 實驗代碼

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

五、 實驗結果

六、總結與思考

• 無向圖的鄰接矩陣是對稱的，有向圖鄰接矩陣可能不對稱。

• 深度優先搜索類似于棧結構的出棧于入棧過程，模擬遞歸，其實遞歸也是通過堆棧的形式實現的。

• 廣度遍歷是非遞歸過程，借助隊列來實現。

• 輔助數組需要在全局使用，在主函數外定義。

• DFS與BFS空間復雜度都是O（n）,鄰接矩陣時間復雜度都是O（n2），鄰接表時間復雜度為O（n+e）。

鄰接矩陣示意圖：

“C語言數據結構圖如何創建與遍歷”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！