1、1 實(shí)驗(yàn)題目圖的基本操作2 實(shí)驗(yàn)?zāi)康?)掌握圖的鄰接矩陣、鄰接表的表示方法。2)掌握建立圖的鄰接矩陣的算法。3)掌握建立圖的鄰接表的算法。4)加深對圖的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力3需求分析 (1)編寫圖基本操作函數(shù)。建立圖的鄰接表，鄰接矩陣Create_Graph( LGraph lg. MGraph mg ) 鄰接表表示的圖的遞歸深度優(yōu)先遍歷LDFS( LGraph g, int i )鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷MDFS( MGraph g,int i, int vn )鄰接表表示的圖的廣度優(yōu)先遍歷LBFS( LGraph g, int s, int n )鄰接矩陣表示的圖

2、的廣度優(yōu)先遍歷MBFS(MGraph g, int s, int n )(2)調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作。建立一個圖的鄰接矩陣和圖的鄰接表。采用遞歸深度優(yōu)先遍歷輸出圖的鄰接矩陣采用遞歸深度優(yōu)先遍歷輸出圖的鄰接表。采用圖的廣度優(yōu)先調(diào)歷輸出圖的鄰接表。采用圖的廣度優(yōu)先遍歷輸出圖的鄰接矩陣4概要設(shè)計(jì)（1） ：/*圖的基本操作*/- 鄰接矩陣數(shù)據(jù)類型的定義-/ 最大頂點(diǎn)個數(shù)typedef structchar vexsMAX_VERTEX_NUM;/ 頂點(diǎn)向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 鄰接矩陣 intvexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù)M

3、Graph ;/-鄰接表數(shù)據(jù)類型的定義-typedef struct ArcNodeint adjvex;/ 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc;/ 指向下一條弧的指針 ArcNode;typedef struct VNodechar data;/ 頂點(diǎn)信息ArcNode *firstarc;/ 指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù) LGraph;（2） 本程序主要包含6個函數(shù)： 主函數(shù)

4、main() 建立圖的鄰接矩陣，鄰接表 Create_Graph () 鄰接表表示的圖的遞歸深度優(yōu)先遍歷LDFS () 鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷MDFS () 鄰接表表示的圖的廣度優(yōu)先遍歷LBFS () 鄰接矩陣表示的圖的廣度優(yōu)先遍歷MBFS（）各函數(shù)間調(diào)用關(guān)系如下：mainCreate_Graph ()LDFS ()MDFS ()LBFS ()MBFS（）（3） 主函數(shù)的偽碼main() 定義鄰接矩陣和鄰接表； 建立鄰接矩陣和鄰接表； 鄰接矩陣MDFS深度優(yōu)先遍歷；鄰接矩陣MBFS廣度優(yōu)先遍歷；鄰接表LDFS深度優(yōu)先遍歷；鄰接表LBFS廣度優(yōu)先遍歷5詳細(xì)設(shè)計(jì)/*圖的基本操作*/-

5、鄰接矩陣數(shù)據(jù)類型的定義-/ 最大頂點(diǎn)個數(shù)typedef structchar vexsMAX_VERTEX_NUM;/ 頂點(diǎn)向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 鄰接矩陣 intvexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph ;/-鄰接表數(shù)據(jù)類型的定義-typedef struct ArcNodeint adjvex;/ 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc;/ 指向下一條弧的指針 ArcNode;typedef struct VNodechar data;/ 頂點(diǎn)信息ArcNode *firstar

6、c;/ 指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù) LGraph;int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立圖的鄰接矩陣，鄰接表輸入圖的頂點(diǎn)個數(shù)（字符），構(gòu)造頂點(diǎn)向量輸入圖的任意兩個頂點(diǎn)的弧構(gòu)造鄰接矩陣構(gòu)造鄰接表void LDFS(LGraph *Lg,int i) 鄰接表表示的圖的遞歸深度優(yōu)先遍歷顯示頂點(diǎn)向量，指針指向下一個頂點(diǎn)向量下一個頂點(diǎn)沒有被訪問，繼續(xù)否則 退會上一個

7、頂點(diǎn)向量的另一個邊void MDFS(MGraph *Mg,int i) 鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷顯示頂點(diǎn)向量，指針指向下一個頂點(diǎn)向量下一個頂點(diǎn)沒有被訪問，繼續(xù)否則 退會上一個頂點(diǎn)向量的另一個邊void LBFS( LGraph *Lg )鄰接表表示的圖的廣度優(yōu)先遍歷 初始化 visited初始化 隊(duì)列沒被訪問過顯示頂點(diǎn)向量入隊(duì)出隊(duì)訪問下一個頂點(diǎn)向量void MBFS(MGraph *Mg )鄰接矩陣表示的圖的廣度優(yōu)先遍歷 初始化 visited初始化 隊(duì)列沒被訪問過顯示頂點(diǎn)向量入隊(duì)出隊(duì)訪問下一個頂點(diǎn)向量/-主函數(shù)-main() 定義鄰接矩陣和鄰接表； 建立鄰接矩陣和鄰接表； 鄰接矩

8、陣MDFS深度優(yōu)先遍歷；鄰接矩陣MBFS廣度優(yōu)先遍歷；鄰接表LDFS深度優(yōu)先遍歷；鄰接表LBFS廣度優(yōu)先遍歷6測試結(jié)果7. 參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)8附錄#include <stdio.h>#include <malloc.h>#include <stddef.h>#include <math.h> #define OK 1#define ERROR 0#define MAX_VERTEX_NUM20/*圖的基本操作*/int visitedMAX_VERTEX_NUM;/ 訪問標(biāo)志數(shù)組/- 鄰接矩陣數(shù)據(jù)類型的定義-/ 最大頂點(diǎn)個數(shù)typedef str

9、uctchar vexsMAX_VERTEX_NUM;/ 頂點(diǎn)向量 intacrsMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 鄰接矩陣 intvexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph ;/-鄰接表數(shù)據(jù)類型的定義-typedef struct ArcNodeint adjvex;/ 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc;/ 指向下一條弧的指針 ArcNode;typedef struct VNodechar data;/ 頂點(diǎn)信息ArcNode *firstarc;/ 指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjLi

10、stMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,arcnum;/ 圖當(dāng)前頂點(diǎn)數(shù)和弧數(shù) LGraph;/_隊(duì)列函數(shù)_typedef struct Queueint arryMAX_VERTEX_NUM;int front,rear;Queue;Queue Q;void InitQueue()/ 隊(duì)列初始化Q.front=Q.rear=0;int QueueEmpty(Queue *Q)/ 清空隊(duì)列if(Q->front=Q->rear)return 1;elsereturn 0;void EnQueue(Queu

11、e *Q,int w)/ 入隊(duì)if(Q->rear+1)%MAX_VERTEX_NUM=Q->front)printf("Error!");elseQ->arryQ->rear=w;Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;int DeQueue(Queue *Q)/ 出隊(duì)int u; if(Q->front=Q->rear)return -1;u=Q->front;Q->front=(Q->front+1)%MAX_VERTEX_NUM;return u;/_隊(duì)列函數(shù)end_/*

12、函數(shù)：Create_Graph*功能：建立圖的鄰接矩陣，鄰接表 *說明：該構(gòu)建的為無向網(wǎng) mg 為鄰接矩陣 ，lg為鄰接表 , 無權(quán)值 */int Locatevex(MGraph *Mg , char v)/ 確定 v 元素在Mg中的位置int i;for(i=0;Mg->vexsi!=v;i+);if(i>Mg->vexnum)/ 輸入的元素不正確則顯示 錯誤printf("ERROR ");return i;/ 返回位置int Create_Graph( MGraph *Mg , LGraph *Lg ) / 建立圖的鄰接矩陣，鄰接表 int i ,

13、 j , k ;char v1 , v2 ;ArcNode *q,*p;printf("輸入圖的頂點(diǎn)數(shù)和弧數(shù): "); scanf("%d %d",&Mg->vexnum,&Mg->arcnum);getchar();Lg->vexnum=Mg->vexnum;/ 鄰接表的頂點(diǎn)數(shù)和弧數(shù) Lg->arcnum=Mg->arcnum;for(i=0;i<Mg->vexnum;i+)/ 構(gòu)造頂點(diǎn)向量 printf("請輸入一個圖的頂點(diǎn)(字符):");scanf("%c

14、" , &Mg->vexsi);getchar();Lg->verticesi.data=Mg->vexsi; / 賦值Lg->verticesi.firstarc=NULL;/ 指向第一條依附該頂點(diǎn)的弧的指針 為空 for(i=0;i<Mg->vexnum;i+)/ 初始化鄰接矩陣for(j=0;j<Mg->vexnum;j+)Mg->acrsij=0 ;for(k=0;k<Mg->arcnum;k+)/ 構(gòu)造鄰接矩陣和鄰接表printf("請輸入一條邊連接的2個頂點(diǎn)：");scanf(&

15、quot;%c %c",&v1,&v2);getchar();i=Locatevex(Mg,v1);/ 確定 v1 在Mg 中的位置j=Locatevex(Mg,v2);/ 確定 v2 在Mg 中的位置Mg->acrsji=Mg->acrsij=1;/ 置v1,v2的對稱弧v2,v1p=(ArcNode *)malloc(sizeof(ArcNode); p->adjvex=i;/ 確認(rèn)頂點(diǎn)位置p->nextarc=Lg->verticesj.firstarc;/ 指向下一條弧的指針Lg->verticesj.firstarc=p;

16、/ 賦值q=(ArcNode *)malloc(sizeof(ArcNode); q->adjvex=j;/ 確認(rèn)頂點(diǎn)位置 q->nextarc=Lg->verticesi.firstarc;/ 指向下一條弧的指針Lg->verticesi.firstarc=q;/ 賦值return OK ; /*函數(shù)：LDFS*功能：鄰接表表示的圖的遞歸深度優(yōu)先遍歷*說明：*/int LAdjVex(LGraph *Lg,int k)/ 位置 ArcNode *p;for(p=Lg->verticesk.firstarc;p!=NULL;p=p->nextarc)if(!

17、visitedp->adjvex)return p->adjvex;return -1;void LDFS(LGraph *Lg,int i) int k;visitedi=OK;printf("%c",Lg->verticesi.data);for(k=LAdjVex(Lg,i);k>=0;k=LAdjVex(Lg,k)if(!visitedk)LDFS(Lg,k);/*函數(shù)：MDFS*功能：鄰接矩陣表示的圖的遞歸深度優(yōu)先遍歷*說明：*/int AdjVes(MGraph *Mg,int k)/ 位置 int i;for(i=0;i<Mg-&

18、gt;vexnum;i+)if(Mg->acrski&&(!visitedi)return i;return -1;void MDFS(MGraph *Mg,int i)/ 遞歸深度優(yōu)先遍歷int k;visitedi=1;/ 訪問標(biāo)志數(shù)組某位 置 1printf("%c",Mg->vexsi);/ 顯示for(k=AdjVes(Mg,i);k>=0;k=AdjVes(Mg,k)if(!visitedk)MDFS(Mg,k);/ 遞歸/*函數(shù)：LBFS*功能：鄰接表表示的圖的廣度優(yōu)先遍歷 *說明：*/void LBFS( LGraph *L

19、g )int i,u,w;for(i=0;i<Lg->vexnum;+i)/ 初始化 visitedvisitedi=0;InitQueue();/ 初始化 隊(duì)列for(i=0;i<Lg->vexnum;+i)if(!visitedi)/ 沒被訪問過visitedi=1;printf("%c",Lg->verticesi.data);EnQueue(&Q,i);/ 入隊(duì)while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出隊(duì)for(w=LAdjVex(Lg,u);w>=0;w=LAdjVex(

20、Lg,u)if(!visitedw)/ 沒被訪問過visitedw=1;printf("%c",Lg->verticesw.data);EnQueue(&Q,w);/ 入隊(duì)/*函數(shù)：MBFS*功能：鄰接矩陣表示的圖的廣度優(yōu)先遍歷*說明：*/void MBFS(MGraph *Mg )int i,w,u;for(i=0;i<Mg->vexnum;i+)/ 初始化 visitedvisitedi=0; InitQueue();/ 初始化隊(duì)列for(i=0;i<Mg->vexnum;+i)if(!visitedi)/ 沒被訪問過visited

21、i=1;printf("%c",Mg->vexsi);/ 顯示EnQueue(&Q,i);/ 入隊(duì)while(!QueueEmpty(&Q)u=DeQueue(&Q);/ 出隊(duì)for(w=AdjVes(Mg,u);w>=0;w=AdjVes(Mg,u) if(!visitedw)/ 沒被訪問過visitedw=1;printf("%c",Mg->vexsw); / 顯示EnQueue(&Q,w);/ 入隊(duì)/*主函數(shù)*/void main()int i ;MGraph Mg;LGraph Lg;Create_Graph( &Mg, &Lg);printf(&