实验七图.doc

实验七 　 图【实验目的】１、掌握图的邻接矩阵和邻接表表达2、掌握图的深度优先和广度优先搜索措施3、掌握图的最小生成树Ｐrim算法4、掌握图的拓扑排序算法5、掌握图的单源最短途径dijｋsｔｒａ算法实验学时】４－6学时【实验预习】回答如下问题：1、写出图7-１无向图的邻接矩阵表达图7-1 无向图G12、写出图７-2有向图的邻接表表达图7-2　有向图Ｇ２3、写出图7-１的深度优先搜索序列和广度优先搜索序列深度：ABDHEＣＦG广度：ABCFDＥＧH4、写出图7－2的拓扑序列，阐明该有向图与否有环？5、根据图7-3,写出其最小生成树图7-3　 无向带权图Ｇ3６、根据图7-４,求从顶点A到其她顶点的单源最短途径图７-4有向带权图G4【实验内容和规定】1、 编写程序eｘp7＿1.c,实现图的邻接矩阵存储及图的深度优先搜索和广度优先搜索以图7-1的无向图为例,补充完整程序，调试运营并写出运营成果运营成果:（涉及输入数据)exｐ7_1.c参照程序如下：＃iｎcｌuｄｅ＜stdｉo.ｈ>#ｄｅfinｅ Ｎ 2０#define TＲUE 1#dｅfｉｎe FＡＬＳＥ 0ｉｎt vｉsited[Ｎ];ﻩﻩ/*访问标志数组＊／typｅdｅf stｒｕcｔ {　 /*辅助队列的定义*/ 　 　inｔ dａｔａ［N]; 　 ｉnt frｏnt,rear;}qｕｅｕe;ｔｙpedef　strｕcｔ {　ﻩ/＊图的邻接矩阵表达*/ 　 int vexnｕm,arｃnum; 　 char ｖexｓ［N］; 　　 int arcs［Ｎ］[N］；}MＧｒapｈ;void ｃrｅatｅGｒaph(ＭGrａｐｈ *ｇ);　 /*建立一种无向图的邻接矩阵*/vｏid　ｄfs(ｉnt ｉ, MGraph *ｇ)；　　 　 /*从第i个顶点出发深度优先搜索*/vｏid tｄfs(MGｒaｐｈ　*g）； 　 ﻩ/*深度优先搜索整个图*/vｏid bfs（inｔ k, ＭGraｐｈ *ｇ）;　 　 　/*从第ｋ个顶点广度优先搜索*/ｖoiｄ tｂfｓ(ＭGｒaph　*g)；　 　 /*广度优先搜索整个图*／voiｄ　inｉt＿vｉｓit（); 　 　　　 ﻩ/*初始化访问标记数组＊／voiｄ creaｔeGｒａph(ＭGraph *g) { ／*建立一种无向图的邻接矩阵＊/ iｎt i＝０,j,e＝０; 　　 ｃhａr v； g-＞vexnum=0; g－>ａrcnum＝0； 　 printf（"\n输入顶点序列(以#结束):\n"); 　　whiｌｅ ((v＝getchar()）！='#') { 　 　　 g->ｖeｘs[ｉ]＝ｖ; 　 　 　ﻩ／*读入顶点信息*/ 　　 　 i++;　 ｝ 　g－>vexnum=ｉ； 　 　 　 /*顶点数目*/ for (i=0;i<ｇ->veｘnum;i＋+) ﻩ/*邻接矩阵初始化＊/ 　 　 for (j=0;j<ｇ－＞vｅxnum;ｊ++) 　 　　　 g-＞aｒcs［i][ｊ]=0;/*（１）－邻接矩阵元素初始化为0＊/ 　 pｒｉntf("\n输入边的信息（顶点序号，顶点序号),以（-1，-1)结束：\n");　 　　ｓｃanf(＂%ｄ,％d＂,&i，＆j); ﻩ／＊读入边(ｉ,j）*／　　 wｈｉｌe　（i!=-1) { 　 ﻩ／*读入i为－1时结束*/　 g-＞ａrcｓ[i][j]=1; /*（２）-ｉ,j相应边等于1*/ 　 　 g－>arcs[ｊ][i]＝1；　 　 　 e＋+； 　　 scanｆ("%d,%d",&i,&ｊ）; 　 }　 　 g-＞arcnum=e; ／*边数目＊/｝／* ｃｒeaｔeＧｒaph */／*（３)---从第ｉ个顶点出发深度优先搜索，补充完整算法＊/vｏiｄ　dfs（int ｉ,　MGraph *g){ int j; pｒiｎtf（"％c",ｇ->ｖeｘs[i］); 　　 ｖisｉtｅd[i]=1； 　 　foｒ（j=０;j<ｇ->vｅxｎum;j++) 　　　if(g->arｃs［ｉ][j]＝=1&&(！ｖisited[ｊ］）） 　 　 ｄfｓ(j，g）；｝／* dｆs ＊/void tdfｓ(MＧrapｈ ＊g) { /*深度优先搜索整个图*/ int　ｉ; 　prinｔf（"\n从顶点%C开始深度优先搜索序列："，g->vexs[0］); 　 fｏｒ　(i＝0;irear=0; 　 q-＞front＝0; ｐｒintf(＂%c＂，g－>vexs[ｋ]）；　 　 visitｅd［k］＝ＴRUE; 　 q->dａｔa[ｑ->ｒear]=k； 　 q－>ｒｅaｒ=（q－>ｒeaｒ+1)%N; 　 while (q->rear!＝q-＞front) { ﻩ/*当队列不为空，进行搜索*／ 　 　i=ｑ－＞ｄata[q－>front]; q-＞front=(q->ｆrｏnｔ+１)%N;　 　 　ｆor　(j=0；jｖexnum;j++)　 　　 　　if ((g->aｒcs[ｉ][j］==１)&&(!ｖｉsitｅd[j］)） {　 　 　 　pｒiｎtf("％ｃ",g-＞veｘs［j])； 　 　 　 　　 　vｉsiteｄ［ｊ]＝ＴＲＵE; 　　 　 ｑ－>data[ｑ－>ｒear］=j; 　 /*(5)---刚访问过的结点入队*/　 　 q->rear=(q->reａｒ+1)%N; ／*（6)---修改队尾指针*/ 　 }　　 ｝}/*bfs*／voｉd tbfｓ（MGrapｈ *ｇ)　{　 　/*广度优先搜索整个图*/ 　　iｎｔ i; ｐrintf（"＼n从顶点%C开始广度优先搜索序列：",ｇ->ｖexｓ［0］); ｆor　（ｉ=0；ｉ<ｇ->vｅxnuｍ;i++) 　 　　 ｉf (vｉsited[i]！=TRUE） 　　 　 　　 bｆｓ(i,g); ﻩ ﻩﻩ /*从顶点i开始广度优先搜索*/ 　ｐriｎtf（"\ｎ");｝/＊tｂfs*/void inｉt_visit(){ /*初始化访问标记数组*/ 　 int　ｉ; 　foｒ　(i=0;ｉ＜N;i++) 　 visitｅd［i]=FALSE；｝int　mａin（){ 　 ＭGraｐｈ　ｇａ; 　 int ｉ,j;　 prｉntf("********＊**图邻接矩阵存储和图的遍历******＊*＊＊*\n＂）; priｎｔf（"＼n1-输入图的基本信息:\n"）; 　　 creaｔeＧrａph(&gａ); 　pｒinｔf(＂\n2-无向图的邻接矩阵：＼ｎ")；　　　 fｏr （i=0;i<ｇａ．ｖexnuｍ；i++） {　 　　 　ｆｏr (j＝0；j<ｇａ．vｅｘｎum；j＋+) 　 　 ｐｒｉntf（"%3d＂,ｇa.arcs［i][ｊ]); 　 ｐrｉntｆ（＂\n");　　　 }　 prｉｎtｆ(＂\n3-图的遍历：\n"); iｎit_ｖisiｔ(); ／*初始化访问数组*／　 ｔdfs(&ga）； ／＊深度优先搜索图＊/　 　init_visｉt（); 　tbfs(&ga）； 　　/＊广度优先搜索图*／ 　 retｕrn　0；}2、 编写程序ｅxｐ7_２.c,实现图的邻接表存储和拓扑排序算法。

以图7-2的有向图为例，补充完整程序，调试运营并写出运营成果运营成果:(涉及输入数据)exp７_2.c程序代码参照如下：#inｃｌｕde#iｎclude#defiｎｅ N 20／*图的邻接表：邻接链表结点*/tyｐｅdef　struct EdgeNodｅ{　 　int aｄｊvex; 　 　／*顶点序号*/ 　 ｓtrucｔ ＥdｇeNoｄe ＊ｎext; ／*下一种结点的指针*／} EdgeNodｅ;/*图的邻接表：邻接表*／tyｐedeｆ strｕcｔ VNode{　 　cｈar　datａ; 　 　/*顶点信息*/ int ind;　 　 ／*顶点入度*/　　 ｓtruct EdgeＮodｅ *link；　 /＊指向邻接链表指针*/} ＶNode;typｅdeｆ ｓtrｕct　AＬgｒapｈ｛ 　 /*图的邻接表＊/ ｉｎt vexnuｍ,ａｒcnｕm；　 　 /*顶点数、弧数*／　　 　VNodｅ adjlist[N]；}ALGｒaph;voiｄ ｃreateＧrａpｈ_list（AＬGrapｈ *g); /＊建立有向图的邻接表*/ｖｏiｄ topＳort(ALＧraph *g）; 　 　　 　 　／*拓扑排序*//*建立有向图的邻接表*/voiｄ cｒeateＧrａｐｈ_list(ALGｒapｈ *ｇ）{　 iｎt i,j,ｅ; cｈar ｖ;　　　　EｄｇeNodｅ *ｓ; i=0; 　e=0； ｐrintf("\n输入顶点序列(以#结束):\n")； 　 ｗhｉle((v=gｅｔｃｈar())！＝'＃＇) 　 ｛　 ｇ->adjlｉｓt［i].datａ＝v; 　 　 /＊读入顶点信息*／　 g->adｊｌist[i].ｌiｎk=NULL; 　　 g->aｄjliｓｔ［i］.ind＝0； 　 　 i＋＋; }　 　g->ｖexnum＝ｉ； /＊建立邻接链表*/ 　　prｉｎtf(＂\n请输入弧的信息(顶点序号,顶点序号)，以(-１,-１）结束:\n"）; 　sｃanf（＂%ｄ,%d＂,&i,&j); whｉle(i!=-１） ｛　 　 　s=(struct EdgｅNodｅ*)malloｃ(sizeｏf(EｄgeNodｅ))； 　 　 　s->adjvex=j; 。