實驗六 圖基本操作的編程實現【實驗目的】圖基本操作的編程實現要求：圖基本操作的編程實現（2學時，驗證型），掌握圖的建立、遍歷、插入、刪除等基本操作的編程實現，存儲結構可以在順序結構、鏈接結構、聯合使用多種結構等中任選，也可以全部實現。也鼓勵學生利用基本操作進行一些應用的程序設計。【實驗性質】驗證性實驗（學時數：2H）【實驗內容】編程對圖進行存儲（鄰接矩陣或鄰接表都可以，由學生自由選擇），之后可以詢問任何兩個結點之間是否有通路和路徑數。設計一個將圖形轉成鄰接鏈表的程序。設計一個深度優先搜索法來查找圖形的程序。設計一個廣度優先搜索法來查找一個圖形的程序。鼓勵開發出難度更高的程序。【思考問題】1. 圖的定義和特性？2. 圖的主要存儲結構是什么？是獨立的某種還是多種數據結構的綜合？3. 圖的主要遍歷思路是哪些？4. 舉出圖的應用范例？【參考代碼】（一）基礎篇/將一個圖采用鄰接表存儲，并在該存儲方法上進行深度優先遍歷/程序構思：/用戶鍵盤輸入結點與各條邊，再將邊轉成鄰接鏈表。/然后對采用鄰接表表示的圖進行深度優先遍歷。#include#include #define vertexnum 100 /定義最大可輸入的結點個數typedef struct node /定義圖形的頂點結構 int vertex; /圖中的頂點信息為數字 struct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結點int Visitedvertexnum; /遍歷記錄void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結點聲明 Graph *New; /新結點聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /顯示菜單printf( 歡迎使用圖的操作演示軟件n);printf(t1、創建圖的鄰接表n);printf(t2、圖的輸出n);printf(t3、圖的深度優先遍歷n);printf(t4、退出程序n);void print_l_graph(Graph *head) /輸出鄰接鏈表的數據 Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(n);void DFS(int vertex) /深度優先遍歷 Graph *SearchP; /結點聲明 /標記某個結點已遍歷過 printf(%d=,vertex); SearchP=headvertex.next; while(SearchP!=NULL) if( ) /判斷結點未被遍歷過 /遞歸調用深度優先遍歷函數 SearchP=SearchP-next; /下一個鄰接點 void main() int source; /圖中一條邊的起始頂點 int destination; /圖中一條邊的終止頂點 int i,j; int vermax; /定義圖中最大的頂點數 int edgemax; /定義圖中最大的邊數 int choice; int no; while(1)showmenu();printf( 請輸入你的選擇：);scanf(%d,&choice);fflush(stdin);/清除鍵盤緩沖區switch(choice) case 1:printf(請輸入圖的類別（有向圖-1，無向圖-0）:); scanf(%d,&no); printf(請輸入圖中的總頂點數和邊數:); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(請輸入第%d條邊的起點：,i);scanf(%d,&source);printf(請輸入第%d條邊的終點：,i);scanf(%d,&destination);if(source=destination) printf(輸入有誤！n);/出錯：自身循環 else /調用建立鄰接鏈表 Create_l_Graph(source,destination,no); printf(圖創建成功，按任意鍵繼續n); getch(); system(cls); break; case 2:printf(圖的鄰接表如下：n); for(i=1;i=vermax;i+)printf(頂點%d:,i); print_l_graph(&headi);/調用輸出鄰接鏈表數據 printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(請輸入遍歷的起點:); scanf(%d,&source); printf(圖的深度優先遍歷結果為：n); DFS(source); printf(ENDn); system(pause); system(cls); break; case 4:return; default: printf(你的輸入有誤，請從新輸入！n); system(pause); system(cls); (二)提高篇/將一個圖采用鄰接表存儲，并在該存儲方法上進行深度優先遍歷/程序構思：/用戶鍵盤輸入結點與各個邊，再將邊轉成鄰接鏈表。/然后對采用鄰接表表示的圖進行廣度優先遍歷。#include#include #define vertexnum 100 /定義最大可輸入的結點個數#define QueueMax 100typedef struct node /定義圖形的頂點結構 int vertex; /圖中的頂點信息為數字 struct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結點int Visitedvertexnum; /遍歷記錄int Front=-1;int Rear=-1;int QueueQueueMax;int Enqueue(int Vertex) /元素入隊 if (Rear=QueueMax) /隊列已滿 return -1; else Rear+; /隊列尾端指針后移 QueueRear=Vertex; /將值存入隊列中 return 1; int Dequeue() /元素出隊 if (Front=Rear) /隊列已空 return -1; else Front+; /隊頭指針后移 return QueueFront; void BFS(int Vertex)/廣度優先搜索 void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結點聲明 Graph *New; /新結點聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /顯示菜單printf( 歡迎使用圖的操作演示軟件n);printf(t1、創建圖的鄰接表n);printf(t2、圖的輸出n);printf(t3、圖的廣度優先遍歷n);printf(t4、退出程序n);void print_l_graph(Graph *head) /輸出鄰接鏈表的數據 Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(%d,searchP-vertex); searchP=searchP-next; printf(n);void main() int source; /圖中一條邊的起始頂點 int destination; /圖中一條邊的終止頂點 int i,j; int vermax; /定義圖中最大的頂點數 int edgemax; /定義圖中最大的邊數 int choice; int no; while(1)showmenu();printf( 請輸入你的選擇：);scanf(%d,&choice);fflush(stdin);/清除鍵盤緩沖區switch(choice) case 1:printf(請輸入圖的類別（有向圖-1，無向圖-0）:); scanf(%d,&no); printf(請輸入圖中的總頂點數和邊數:); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(請輸入第%d條邊的起點：,i);scanf(%d,&source);printf(請輸入第%d條邊的終點：,i);scanf(%d,&destination);if(source=destination) printf(輸入有誤！n);/出錯：自身循環 else /調用建立鄰接鏈表 Create_l_Graph(source,destination,no); printf(圖創建成功，按任意鍵繼續n); getch(); system(cls); break; case 2:printf(圖的鄰接表如下：n); for(i=1;i=vermax;i+)printf(頂點%d:,i); print_l_graph(&headi);/調用輸出鄰接鏈表數據 printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(請輸入遍歷的起點:); scanf(%d,&source); pri