.實驗項目名稱： 圖的遍歷 一、實驗目的 應用所學的知識分析問題、解決問題，學會用建立圖并對其進行遍歷，提高實際編程能力及程序調試能力。二、實驗內容 問題描述：建立有向圖，并用深度優先搜索和廣度優先搜素。輸入圖中節點的個數和邊的個數，能夠打印出用鄰接表或鄰接矩陣表示的圖的儲存結構。三、實驗儀器與設備 計算機，Code:Blocks。四、實驗原理 用鄰接表存儲一個圖，遞歸方法深度搜索和用隊列進行廣度搜索，并輸出遍歷的結果。5、 實驗程序及結果#define INFINITY 10000 /*無窮大*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef struct ArCellint adj; ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct char name20; infotype;typedef struct infotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;int LocateVex(MGraph *G,char* v) int c = -1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-)=0) c=i; break;return c;MGraph * CreatUDN(MGraph *G)/初始化圖，接受用戶輸入int i,j,k,w;char v120,v220;printf(請輸入圖的頂點數,弧數:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(結點名字:n);for(i=0;ivexnum;i+)printf(No.%d:,i+1);scanf(%s,G-);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(請輸入一條邊依附的兩個頂點和權值:n);for(k=0;karcnum;k+)printf(第%d條邊:n,k+1); printf(起始結點:);scanf(%s,v1); printf(結束結點:);scanf(%s,v2); /printf(邊的權值:); /scanf(%d,&w);i=LocateVex(G,v1); j=LocateVex(G,v2);if(i=0&j=0)/G-arcsij.adj=w;G-arcsji=G-arcsij;return G;int FirstAdjVex(MGraph *G,int v)int i;if(v=0 & vvexnum) /v合理for(i=0;ivexnum;i+)if(G-arcsvi.adj!=INFINITY)return i;return -1;void VisitFunc(MGraph *G,int v)printf(%s ,G-);int NextAdjVex(MGraph *G,int v,int w)int k;if(v=0 & vvexnum & w=0 & wvexnum)/v,w合理for( k=w+1;kvexnum;k+)if(G-arcsvk.adj!=INFINITY)return k;return -1;int visitedMAX;void DFS(MGraph *G,int v)/從第v個頂點出發遞歸地深度優先遍歷圖Gint w;visitedv=1;VisitFunc(G,v);/訪問第v個結點for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);printf(%d ,G-arcsvw);void DFSTraverse(MGraph *G,char *s)/深度優先遍歷int v,k;for(v=0;vvexnum;v+)visitedv=0;k=LocateVex(G,s);if(k=0&kvexnum)for(v=k;v=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;vvexnum;v+)if(!visitedv)DFS(G,v);typedef struct Qnodeint vexnum;struct Qnode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue *Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(0);Q-front-next=NULL;return 1;void EnQueue(LinkQueue *Q,int a )QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-vexnum=a;p-next=NULL;Q-rear-next=p;Q-rear=p;int DeQueue(LinkQueue *Q,int *v) QueuePtr p;if(Q-front=Q-rear)printf(結點不存在!n);exit(0);p=Q-front-next;*v=p-vexnum;Q-front-next=p-next;if(Q-rear=p)Q-front=Q-rear;return *v;int QueueEmpty(LinkQueue *Q)if(Q-rear=Q-front)return 0;return 1;int VisitedMAX;void BFSTraverse(MGraph *G,char *str)/廣度優先遍歷int w,u,v,k;LinkQueue Q,q;for(v=0;vvexnum;v+) Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v=0;v-)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入隊while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出隊for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);for(v=k+1;vvexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入隊while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出隊for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);void main()MGraph *G,b;char v10;G=CreatUDN(&b);printf(請輸入起始結點名稱:);scanf(%s,v);printf(n深度優先遍歷:n);DFSTraverse(G,v);printf(n廣度優先遍歷:n);BFSTraverse(G,v);getch();6、 實驗總結實驗要求輸入圖中節點的個數和邊的個數，能夠打印出用鄰接表或鄰接矩陣表示的圖的儲存結構。在設計中其中用鄰接表表示的節點的值只能是數字，但用鄰接矩陣表示的節點的值可以是字母。但用鄰接表形式要相對簡單一些。深度優先采取的遞歸思想。首先，將從起點，沿某條邊，順勢遍歷下去，直到不能繼續遍歷下去。這時，又從起點的另一結點開始，遍歷下去。如