試驗四圖的操作及應用講解

1、實驗四圖的操作及應用實驗課程名：數(shù)據(jù)結(jié)構(gòu)與算法 一、實驗目的及要求1、理解圖的基本概念及術(shù)語。2、掌握圖的兩種存儲結(jié)構(gòu) （鄰接矩陣和鄰接表）的表示方法。）的算法思想、步3、熟練掌握圖的兩種遍歷（深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷 驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列。、實驗內(nèi)容任務一：卞造如圖1所示的圖的鄰接矩陣存儲結(jié)構(gòu)和鄰接表存儲結(jié)構(gòu)。圖1解答：(1)源代碼：#include#include #include #define INFINITY 1000#define MAX_VERTEX_NUM 20#define OK 1#define STARTS、*,、typede

2、f enumDG,DN,UDG,UDN GraphKind;typedef int EType;typedef int InfoType;typedef int VertexType;typedef struct ArcCell/define structure MGraphEType adj;InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX VERTEX NUM;AdjMatrix arcs;int vexnum,arcnum;GraphKind kind

3、;MGraph;int CreatUDN(MGraph &G)CreatUDN() sub-functionint IncInfo,i,j,k,v1,v2,w;coutendlG.vexnum;/input the number of vexcoutG.arcnum;/input the number of arccoutIncInfo;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=INFINITY;/initial G.arcsij.adjG.=NULL;/initial G.cout

4、V2),For example:(V1=1,V2=3),(V1=2,V2=4)”endl;for(k=0;kG.arcnum;+k)/input arc(v1,v2)coutendlPlease input the k+1th arcs v1 (0v1v1;/input v1coutPlease input the k+1th arcs v2 (0v2v2;/input v2coutPlease input the ”k+1w;/input weight i=v1;j=v2;while(iG.vexnum|jG.vexnum)/if (v1,v2) illegal,againcoutPleas

5、e input the k+1th arcs v1 (0v1v1;coutPlease input the k+1th arcs v2 (0v1v2;coutPlease input the k+1w;i=v1;j=v2; /while end i-;j-;G.arcsij.adj=G.arcsji.adj=w;/weightcoutG.arcsi+1j+1.adj=G.arcsj+1i+ 1.adj=wendl;if(IncInfo)coutPlease input the k+1*G.; /for end return (OK); CreatUDN() endvoid

6、 Gprintf(MGraph G) / 打印鄰接矩陣cout鄰接矩陣數(shù)組為：n;for(int i=0;iG.vexnum;i+) for(int k=0;kG.vexnum;k+) coutG.arcsik.adjt; coutendl;/* 鄰接表*/typedef struct ArcNode/define structure ALGraph int adjvex;struct ArcNode *nextarc;InfoType *info;ArcNode;typedef struct VNode(VertexType data;ArcNode *firstarc;VNode,AdjL

7、istMAX_VERTEX_NUM;typedef struct (AdjList vertices;int vexnum,arcnum;int kind;ALGraph;int CreateDG(ALGraph &G)CreateDG() subfunction (int IncInfo,i,j,k,v1,v2,w;coutendlG.vexnum;/input the number of vexcoutG.arcnum;/input the numbe of arccoutIncInfo;/if no information, input 0for(i=0;iG.vexnum;+i) (G

8、.verticesi.data=i; /initial G.verticesi.dataG.verticesi.firstarc=NULL;/initial G.verticesi.firstarc coutV2),For example:(V1=1,V2=3),(V1=2,V2=4)”endl;for(k=0;kG.arcnum;+k)/input arc(v1,v2) (coutendlPlease input the k+1th arcs v1 (0v1v1;coutPlease input the k+1th arcs v2 (0v2v2;i=v1;j=v2;while(iG.vexn

9、um|jG.vexnum) /if (v1,v2) illegal (coutendlPlease input the k+1th arcs v1 (0v1v1;coutPlease input the k+1th arcs v2 (0v2v2;i=v1;j=v2; /while end i-;j-;ArcNode *p;p=(ArcNode *)malloc(sizeof(ArcNode);/allocate memoryif(!p)coutadjvex=j; /assign p-adjvex p-nextarc=G.verticesi.firstarc; p-info=NULL;G.ver

10、ticesi.firstarc=p;if(IncInfo)cout*(p-info); /input information /for endreturn (OK); /CreateDG() endint main()MGraph MG;ALGraph AG;int a=-1;while(a!=0)coutSTARTSSTARTSendl;cout(1)鄰接矩陣(無向網(wǎng))t(2) 鄰接表(有向圖)t(3) 退出 endl;couta;switch(a)CreatUDN(MG);Gprintf(MG);break;CreateDG(AG);break;a=0;break;default:cout

11、選擇錯誤 nV2), For exanqle: (Vl=l, V2=3), (Vl=2, V2=4).Please input the 1th arcs vl (0vlG, vexnunO : 1Please input the 1th arcs v2 (0v2G.vexnuirO :2Please input the 1th arc? s weight 二EG. arcs 1 2- adj=G. arcs 2 1. adj =3Flease input the 2th arcs vl (071G. vexnunO : 1Please input the 2th arc1s v2 (0v2G,

12、 veKnunO :2Please input the 2th arc1 s weight ：63. arcsl 2. adj=G. arcs2 1. adj-6Please input the 3th arc s vl (0vlG. vexnuirO ： 1.Please input the Sth arc5 s v2 (0v2G* vexnuirO : 3Flease input the Sth arc1s weight :2G.arcstl 3,adj=G, arcs31, adj=2Please input the 4th arc? s vl (0vlG. vexnum) :2Plea

13、se input the 4th arc? s v2 C0v2G. vexnunO :三please input the 4th arc s weight ：3j. arcs2 3. &dj=G. arcs3 2j. adj=3FIpifp i r ir riciseii G. dii. j _2F： f*f i r ric.i2u irFid4三巳iiG,2二匚三三ricicc ir iiFiease ir ,一河w ，ri t 11 Flmmma irF： F4FF _i r ?G“ MT，二三一三Please ir Pl F4FF i rF1e?iee _ir G. di = _4F：口

14、可ff i rF p：i：-p irT-Kt trip 5i-：i Hi：；叮：i- 1 .C-. -pT-niji1 : ?.Ti :t t：-in F.-t-iErfUniim :Fii?ntliiuHtn.jI/lYuijA : uhHBUHHhT-i ：t t：-in F-tn ir：叮：J1TmiE ：5f. L；tLjijril.ii1.一二工七工：1LUJ：4i：.uttht.七二：JU七工UCL：匚unit the -A di iveid.t : 4：t:lJ.t?ji-；Lt?i.-ii 1 TCL，匚mil二L：七ipi：t thp 1十？ 臼丁J：噌葉一t ：弓專 Lit

15、tE二”.二 1且二L d，； ：I 1 iHXnl-CL1：4T-l：tt?lAf-1HI：，T.I(.-PT：-LlOl： Hpijt t：-iP ri-r -i ,-ir.-叫f i 汁 t 1 1i；-i：t t/iA 匕：；：t廣一一 I 1 w 1， G.二工門wi ：、G. arcs 5 挎王陣) 1000E62tloooiIOCiOF10001春搽 國爭存儲:6 adj=G* arcs6 5. adj-1 救組為：)2100010001000LOGO3100061000S1000645LOGO6100010001)4IODO10001LOGO5111000“無向向:* * (2

16、；鄰接靠潘總酋)+* *方式:2(3)運行結(jié)運用數(shù)組上 任務二：用， 遍歷和廣度。，果分析：弓鏈表的結(jié)合來實現(xiàn)鄰接表的存儲結(jié)構(gòu)創(chuàng)建一個如圖2所示的圖a,分別打印出這兩個圖的深度優(yōu)先亡先遍歷的結(jié)點信息序列。(b)圖 2解答：(1)源代碼：#include#include#includeusing namespace std;#define ERROR 1#define MAX_VERTEX_NUM 100typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;string info;ArcNode;typedef struct VNode

17、char date;ArcNode * firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum; /當前圖的 vexnum頂點數(shù)和 arcnum 弧數(shù)int kind;ALGraph;int LocateVex(ALGraph &G,char &v1)int i;for(i=0;i=G.vexnum)return ERROR;elsereturn 0;void CreateDG(ALGraph &G)ArcNode *p,*q;char v1,v2;char v;int i,j,

18、k,n;cout請輸入圖的頂點數(shù)和弧數(shù)：G.vexnum;cinG.arcnum;cout請輸入頂點：endl;for(i=0;iv;G.verticesi.date=v;G.verticesi.firstarc=NULL;cout請輸入弧尾和弧頭：;for(k=0;kv1;cinv2;i=LocateVex(G,v1);j=LocateVex(G,v2);if(G.verticesi.firstarc=NULL)(p=(ArcNode *)new ArcNode;G.verticesi.firstarc=p;q=G.verticesi.firstarc;else(q=G.verticesi.

19、firstarc;for(n=0;nnextarc)(if(!q-nextarc) break;p=(ArcNode *)new ArcNode;q-nextarc=p;q=q-nextarc;q-adjvex=j;q-nextarc=NULL;coutadjvex;if(visitedi=false)n=i;return n;int NextAdjVex(ALGraph &G,int v)int i;int n=-1;ArcNode *p;p=G.verticesv.firstarc;for(i=p-adjvex;iadjvex;if(visitedi=false)n=i;break;els

20、ep=p-nextarc;return n;void VisitFuc(ALGraph &G,int v)coutG.verticesv.date=0;w=NextAdjVex(G,v) if(!visitedw) DFS(G,w);10)void DFSTraverse(ALGraph &G)(int v;for(v=0;vG.vexnum;v+)visitedv=false;cout 深度優(yōu)先搜索：endl;for(v=0;vG.vexnum;v+)(if(!visitedv)DFS(G,v);)/ 廣度優(yōu)先遍歷/void BFSTraverse(ALGraph &G)(int v;int w;queue q; /STL隊歹!Jfor(v=0;vG.vexnum;v+)visitedv=false;/ InitQueue(Q);cout 廣度優(yōu)先搜索：;for(v=0;v=0;w=NextAdjVex(G,v) if(!visitedw)(visitedw=true;VisitFuc(G,w);q.push(w)