图实训.docVIP

数学与计算机学院 实 验 报 告 实验名称 图应用 指导教师 周立章 实验类型 □验证 √综合 实验学时 2+10 实验日期 实验时间 实验编号 分组号 实验地点 实验目的和要求 1．掌握图的基本存储方法：邻接矩阵和邻接表。 2．掌握有关图的基本操作算法并能用高级语言实现。 3．掌握图的的深度优先有哪些信誉好的足球投注网站遍历和广度优先有哪些信誉好的足球投注网站遍历算法。 4．掌握图的最小生成树的两种算法。 实验要求：（1）理解图顶点和边的存储方法：邻接矩阵和邻接表；（2）理解图的遍历算法，掌握其应用；（3）应用图的遍历算法判断图是否连通和两顶点间是否存在路径。 二、实验环境(实验设备) 硬件: 微型计算机P5 软件: Windows XP+Microsoft Visual C++ 6.0 三、实验原理及内容 实验题目: 建立无向网的邻接表存储结构：要求：… 求出无向网中各顶点的度，并输出。 判断给定的无向网是否是通连网？ 写一算法连通分量的个数并输出各连通分量的顶点集答：连通的无向网： 非连通无向网： 5.邻接表中相关操作： 假如无向网G，则 1）判断顶点i是否有度的语句是： 答： p=Vertices[i].adj; while(p!=NULL) { d[i]++; p=p-next; } if(d[i]==0) cout顶点i+1无度！endl; else cout顶点i+1有度，且度为：d[i]endl; 2）求取顶点i的第一个边结点的语句是： 答： p=Vertices[i].adj; 3）如何计算顶点i的度？ 答： p=Vertices[i].adj; while(p!=NULL) { d[i]++; p=p-next; } 6．写出无向网G的邻接表存储算法 答： void AdjTWGraph::CreatG(int n,int e) { int vi,vj; DistT w; numE=e; numV=n; cout\n 输入顶点信息:; for(int i=0;inumV;i++) { cout\ni+1:; cinVertices[i].data; } for(i=0;inumE;i++) { cout\n 输入边的信息（Vi，Vj，W）:; cinvivjw; if(vi1||vinumV||vj1||vjnumV) cout\n 定点越界endl; Edge *p=new Edge; p-dest=vj-1; p-weight=w; p-next=NULL; if(Vertices[vi-1].adj==NULL) Vertices[vi-1].adj=p; else { Edge *curr=Vertices[vi-1].adj,*pre=NULL; while(curr!=NULLcurr-destvj-1) { pre=curr; curr=curr-next; } if(pre==NULL) { p-next=Vertices[vi-1].adj; Vertices[vi-1].adj=p; } else { p-next=pre-next; pre-next=p; } } Edge *q=new Edge; q-dest=vi-1; q-weight=w; q-next=NULL; if(Vertices[vj-1].adj==NULL) Vertices[vj-1].adj=q; else { Edge *curr=Vertices[vj-1].adj,*pre=NULL; while(curr!=NULLcurr-destvi-1) { pre=curr; curr=curr-next; } if(pre==NULL) { q-next=Vertices[vj-1].adj; Vertices[vj-1].adj=q; } else { q-next=pre-next; pre-next=q; } } } } 7．写出输出无向网邻接表算法。 答： void AdjTWGraph::PrintG() { Edge *curr; for(int i=0;inumV;i++) { cout顶点：i