圖的實(shí)驗(yàn)報(bào)告

1、.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告題目： 圖 一、實(shí)現(xiàn)圖的鄰接矩陣和鄰接表存儲(chǔ) （一）需求分析對(duì)于下圖所示的有向圖G，編寫一個(gè)程序完成如下功能：1 建立G的鄰接矩陣并輸出之2 由G的鄰接矩陣產(chǎn)生鄰接表并輸出之3 再由2的鄰接表產(chǎn)生對(duì)應(yīng)的鄰接矩陣并輸出之（二）系統(tǒng)設(shè)計(jì)1、 本程序中用到的所有抽象數(shù)據(jù)類型的定義；typedef struct int no;InfoType info; VertexType;/頂點(diǎn)類型typedef struct /圖的定義 int edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV; MGraph;/圖的鄰接矩陣類型type

2、def struct ANode /弧的結(jié)點(diǎn)結(jié)構(gòu)類型int adjvex; struct ANode *nextarc; InfoType info; ArcNode;typedef int Vertex;typedef struct Vnode /鄰接表頭結(jié)點(diǎn)的類型Vertex data; ArcNode *firstarc; /指向第一條弧 VNode;typedef VNode AdjListMAXV;/AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表int n,e; ALGraph; /圖的鄰接表類型2、 主程序的流程以及各程序模塊之間

3、的層次調(diào)用關(guān)系，函數(shù)的調(diào)用關(guān)系圖：Main() DispAdj(G);輸出鄰接表GDispMat(g);輸出鄰接矩陣gMatToList(g,G);將鄰接矩陣g轉(zhuǎn)換成鄰接表G3、 列出各個(gè)功能模塊的主要功能及輸入輸出參數(shù)void MatToList(MGraph g,ALGraph *&G) 將鄰接矩陣g轉(zhuǎn)換成鄰接表Gvoid DispMat(MGraph g) 輸出鄰接矩陣gvoid DispAdj(ALGraph *G) 輸出鄰接表Gint OutDegree(ALGraph *G,int v) 求圖中每個(gè)頂點(diǎn)的出度（三）調(diào)試分析調(diào)試過程中還是出現(xiàn)了一些拼寫錯(cuò)誤，經(jīng)檢查后都能及時(shí)修正。有些

4、是語(yǔ)法設(shè)計(jì)上的小錯(cuò)誤，比如一些參變量的初始值設(shè)置錯(cuò)誤，使得程序調(diào)試出錯(cuò)。在小組討論分析后糾正了這些結(jié)果，并盡量改進(jìn)了算法的性能，減小時(shí)間復(fù)雜度。 將鄰接矩陣g轉(zhuǎn)換成鄰接表G，輸出鄰接矩陣g，輸出鄰接表G的算法時(shí)間復(fù)雜度都是O(n2)。 通過這次實(shí)驗(yàn)，對(duì)圖的存儲(chǔ)方法有了更深刻的印象。（四）測(cè)試結(jié)果測(cè)試結(jié)果：（1） 有向圖G的鄰接矩陣為 0 1 0 4 0 0 9 2 3 5 8 0 0 0 6 0（2） 圖G的鄰接矩陣轉(zhuǎn)換成的鄰接表為： 0:1 3 1:2 3 2:0 1 2 3:2（5） 用戶手冊(cè) 不需要輸入?yún)?shù)（6） 附錄源程序#include#include#defineMAXV 100/

5、最大頂點(diǎn)個(gè)數(shù)#define INF 32767 /INF表示typedef int InfoType;typedef struct int no;/頂點(diǎn)編號(hào)InfoType info;/頂點(diǎn)其他信息 VertexType;/頂點(diǎn)類型typedef struct /圖的定義 int edgesMAXVMAXV; /鄰接矩陣 int vexnum,arcnum; /頂點(diǎn)數(shù)，弧數(shù)VertexType vexsMAXV;/存放頂點(diǎn)信息 MGraph;/圖的鄰接矩陣類型typedef struct ANode /弧的結(jié)點(diǎn)結(jié)構(gòu)類型int adjvex; /該弧的終點(diǎn)位置 struct ANode *nex

6、tarc; /指向下一條弧的指針 InfoType info; /該弧的相關(guān)信息,這里用于存放權(quán)值 ArcNode;typedef int Vertex;typedef struct Vnode /鄰接表頭結(jié)點(diǎn)的類型Vertex data; /頂點(diǎn)信息 ArcNode *firstarc; /指向第一條弧 VNode;typedef VNode AdjListMAXV;/AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中頂點(diǎn)數(shù)n和邊數(shù)e ALGraph; /圖的鄰接表類型void MatToList(MGraph g,A

7、LGraph *&G)/將鄰接矩陣g轉(zhuǎn)換成鄰接表Gint i,j,n=g.vexnum;/n為頂點(diǎn)數(shù)ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=NULL;for (i=0;i=0;j-)if (g.edgesij!=0)/鄰接矩陣的當(dāng)前元素不為0 p=(ArcNode *)malloc(sizeof(ArcNode);/創(chuàng)建一個(gè)結(jié)點(diǎn)*pp-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc;/將*p鏈到鏈表后G-adjlisti.

8、firstarc=p;G-n=n;G-e=g.arcnum;void DispMat(MGraph g)/輸出鄰接矩陣gint i,j;for (i=0;ig.vexnum;i+)for (j=0;jg.vexnum;j+)if (g.edgesij=INF)printf(%3s,);elseprintf(%3d,g.edgesij);printf(n);void DispAdj(ALGraph *G)/輸出鄰接表Gint i;ArcNode *p;for (i=0;in;i+)p=G-adjlisti.firstarc;if (p!=NULL) printf(%3d: ,i);while (

9、p!=NULL)printf(%3d,p-adjvex);p=p-nextarc;printf(n);int OutDegree(ALGraph *G,int v)/求圖中每個(gè)頂點(diǎn)的出度ArcNode *p;int n=0;p=G-adjlistv.firstarc;while(p!=NULL) n+;p=p-nextarc;return n;void main()int i,j;MGraph g,g1;ALGraph *G;int AMAXV4=0,1,0,4,0,0,9,2,3,5,8,0,0,0,6,0,;g.vexnum=4;g.arcnum=8;for (i=0;ig.vexnum;

10、i+)for (j=0;jn,&G-e); /輸入頂點(diǎn)數(shù)和邊數(shù) scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表 for(i=0;in;i+)for(j=0;jn;j+) G-edgesij=0; /初始化鄰接矩陣 printf(Input edges,Creat Adjacency Matrixn); for(k=0;ke;k+) /讀入e條邊，建立鄰接矩陣 scanf(%d%d,&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào) G-edgesij

11、=1; G-edgesji=1; /若為無向圖，矩陣為對(duì)稱矩陣；若建立有向圖，去掉該條語(yǔ)句 typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;void DFSM(MGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf(%c,G-vexsi); /訪問頂點(diǎn)Vi visitedi=TRUE; /置已訪問標(biāo)志 for(j=0;jn;j+) /依次搜索Vi的鄰接點(diǎn)if(G-edgesij=1 & ! visitedj) DFSM(G,j); /（Vi，Vj

12、）E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)void DFS(MGraph *G) int i; for(i=0;in;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;in;i+)if(!visitedi) /Vi未訪問過 DFSM(G,i); /以Vi為源點(diǎn)開始DFS搜索void BFS(MGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定義隊(duì)列 for(i=0;in;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;in;i+)cqi=-1; /隊(duì)列初始化 printf(%c,G-vexsk); /訪問源點(diǎn)Vk visitedk=TRUE; cqr=k; /Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-1) /隊(duì)非空則執(zhí)行 i=cqf; f=f+1; /Vf出隊(duì) for(j=0;jn;j+) /依次Vi的鄰接點(diǎn)Vj if(G-edgesij=1 & !visitedj) /Vj未訪問 printf(%c,G-vexsj); /訪問Vj visitedj=TRUE; r=r+1; cqr=j; /訪問過Vj入隊(duì) void main() int i; MG