圖的實驗報告

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

2、def struct ANode /弧的結(jié)點結(jié)構(gòu)類型int adjvex; struct ANode *nextarc; InfoType info; ArcNode;typedef int Vertex;typedef struct Vnode /鄰接表頭結(jié)點的類型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、 列出各個功能模塊的主要功能及輸入輸出參數(shù)void MatToList(MGraph g,ALGraph *&G) 將鄰接矩陣g轉(zhuǎn)換成鄰接表Gvoid DispMat(MGraph g) 輸出鄰接矩陣gvoid DispAdj(ALGraph *G) 輸出鄰接表Gint OutDegree(ALGraph *G,int v) 求圖中每個頂點的出度（三）調(diào)試分析調(diào)試過程中還是出現(xiàn)了一些拼寫錯誤，經(jīng)檢查后都能及時修正。有些

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

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

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

7、LGraph *&G)/將鄰接矩陣g轉(zhuǎn)換成鄰接表Gint i,j,n=g.vexnum;/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)/鄰接矩陣的當前元素不為0 p=(ArcNode *)malloc(sizeof(ArcNode);/創(chuàng)建一個結(jié)點*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)/求圖中每個頂點的出度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); /輸入頂點數(shù)和邊數(shù) scanf(%c,&a); printf(Input Vertex string:); for(i=0;in;i+) scanf(%c,&a); G-vexsi=a; /讀入頂點信息，建立頂點表 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）的頂點序號 G-edgesij

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

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