图的存储

数据结构课程设计《图的存储》专业：****************班级：****学号：***********姓名：*******任课教师：*******图的存储一、问题描述以图的邻接矩阵方式创建一个有向图，根据此存储结构，求图的邻接表存储结构，并输出邻接表。基本要求：（1）定义图的邻接矩阵、邻接表的存储结构；（2）按照图的邻接矩阵结构创建图；（3）根据图的邻接矩阵存储，求图的邻接表存储；（4）设计邻接矩阵与邻接表的形式；（5）输入：图的顶点与边可以初始化方式读入，也可以键盘以交互方式读入或从文件读入；（6）输出：图的邻接矩阵和图的邻接表。二、数据结构设计根据题干及要求，需要实现图的逻辑结构，而且题中也要求了图的存储结构，邻接矩阵和邻接表的存储结构。再有，为方便起见，设计邻接矩阵中顶点为简单的String类型，而在邻接表中的顶点结点类中设计顶点也为String类型。邻接矩阵中存储的是图的顶点之间邻接的信息，用二维数组即可以表示。而邻接表中存储的是顶点与其他顶点还有边的信息，所以采用一维数组中存放链式表数据。具体实现需要定义两个类，顶点和边的类。其中，顶点类为链表表头，由它指向其他顶点，边类为顶点的后继，存放有顶点在顶点数组的下标、顶点信息、后继组成。也就是说，邻接矩阵图是根据每个顶点的邻接关系来创建二维数组；而邻接表是根据每个顶点与其他顶点的关系来创建一个链表，集合这些链表放在一个一维数组中。三、算法设计该题主要涉及的有邻接矩阵图类，邻接表图类，邻接矩阵转邻接表方法，主方法等。先从第一步开始，用邻接矩阵图法建一个有向图。邻接矩阵图类MG类：首先，统一变量为public，这是为了方便调试、测试类调用等。定义几个关键变量，如publicfinalstaticintINFINITY=Integer.MAX_VALUE;publicintvexnum,arcnum;publicString[]vexs;publicint[][]arcs;其中，INFINITY是定义二维数组初始化无穷大的变量。后面分别定义了定点数、边数、顶点数组、二维数组（矩阵）。其次，两个构造方法，一个传递空，一个传递这些变量。再写一个locatevex顶点定位的方法，定位顶点在顶点数组中的位置或者说是其下标。用一个for语句来实现：下面就是重点了，创建邻接矩阵存储的有向图。这里我选择用键盘以交互方式读入信息。输入顶点数、边数和输入具体的各个顶点，创建顶点数组和二维数组，其中要初始化二维数组，如：//邻接矩阵arcs=newint[vexnum][vexnum];//初始化邻接矩阵for(inti=0;ivexnum;i++)for(intj=0;jvexnum;j++)arcs[i][j]=INFINITY;接下来，开始创建邻接矩阵。这里，要根据自己画的图进行输入。最好将图，图的邻接矩阵，邻接表先准备好，然后进行输入信息。创建邻接矩阵的算法为：如：//创建邻接矩阵for(intk=0;karcnum;k++){intv=locatevex(in.next());intu=locatevex(in.next());arcs[v][u]=in.nextInt();}这里，要输入的是：{（顶点1）+（顶点1的邻接点1）+（该两点所形成边的权值）}因此，for语句中用arcnum边数来限制循环，而又用locatevex方法来查找定位输入顶点在顶点数组中的位置，得其下标就可以正确将信息输入了。最后，是print输出邻接矩阵的方法，其中因为需要输出二维数组，所以用了两个for的嵌套来实现的，而且，为了输出效果美观，将初始化打印为“*”。邻接表AG类（包括VNode类，ANode类）：定义一个顶点结点类VNode类，拥有一个数据域和一个后继（该后继为Anode类型，为了方便指向弧边）。弧边结点类ANode类，拥有一个位置定位，一个权值，一个后继。其他的这里就不做详细叙述了。接下来是有向图的邻接表存储结构的类AG类。先定义变量vexnum顶点数，arcnum边数，还定义了一个顶点结点类的一维数组，存储表头。接下来是构造方法，然后是顶点定位方法如：下面一个是在图中头插法插入边的方法addarc，其中的参数为，待插入边的两个顶点的位置下标v，u和边的权值value。首先创建一个边结点类的对象，付给其有向边被指向点的下标和其权值，然后，把有向边出发点在顶点数组中的后继指向该边的后继，这样一个边结点已经付好了值，然后将该边直接放在顶点数组该点的后继上。具体如下：//图中插入边结点publicvoidaddarc(intv,intu,intvalue){ANodearc=newANode(u,value);arc.nextarc=vexs[v].firstarc;vexs[v].firstarc=arc;arcnum++;}接下来是重点，创建邻接表存储的有向图。还是一样，输入图的顶点数，边数，然后就是输入图的各个顶点，输入各个边的两个顶点及其权值。输入顶点数和图的各个顶点之后，就会创建一个VNode类的数组，而输入各个边的两个顶点及其权值时，就会用到addarc插入边方法。新建图时，先给定顶点，然后给定边及其权值，这时用的就是插入边的方法。如：//创建有向图publicvoidcreatDN(){Scannerin=newScanner(System.in);System.out.println(请分别输入图的顶点数、图的边数：);vexnum=in.nextInt();arcnum=in.nextInt();vexs=newVNode[vexnum];System.out.println(请分别输入图的各个顶点：);for(inti=0;ivexnum;i++)vexs[i]=newVNode(in.next());System.out.println(请输入各个边的两个顶点及其权值：);for(intk=0;karcnum;k++){intv=locatevex(in.next());intu=locatevex(in.next());intvalue=in.nextInt();addarc(v,u,value);}}接下来是输出邻接表的方法print。这里用一个for语句遍历顶点结点类数组，再用一个内置while语句来遍历每一个链表的每一个元素。//输出邻接表publicvoidprint(){for(inti=0;ivexnum;i++){System.out.print(+vexs[i].data+);ANodep=vexs[i].firstarc;while(p!=null){System.out.print(→(+vexs[p.adjvex].data.toString()+,+p.value+));p=p.nextarc;}System.out.println();}}测试类test类：测试类包括两部分，一个是主方法，一个是矩阵转表的方法。首先先说明由邻接矩阵存储形式的图转创建邻接表存储形式的图这个方法。该方法的思路是直接按照邻接表方式创建图，不过这时不是重新输入数据，而是把已经创建好的邻接矩阵图的数据信息传入到其中。不过，我们需要根据矩阵图的信息转换成邻接表所需要的信息。具体实现如下：在测试类中定义一个静态static的AG返回型的方法，传入MGmap，这其中map为在主方法中创建的对象，也就是矩阵图。在方法中创建邻接表图的对象，先把矩阵图的顶点数传进去，然后再将边数传进去，如：AGag=newAG();ag.vexnum=map.vexnum;ag.vexs=newVNode[map.vexs.length];接下来把每个顶点传进去，如：for(inti=0;imap.vexs.length;i++)ag.vexs[i]=newVNode(map.vexs[i]);再把各个边的两个顶点及其权值传进去，用两个for。第一个for遍历顶点数组，第二个for遍历邻接矩阵，找到下一个邻接点，并输入该边的权值。最后再用邻接表类中的插入边方法，插入进去。如：for(inti=0;imap.vexnum;i++){for(intj=0;jmap.vexnum;j++)if(map.arcs[i][j]!=map.INFINITY)ag.addarc(i,j,map.arcs[i][j]);}该方法的返回值为创建的AG的对象，也就是邻接表图。最后，说一下主方法。具体思路是：第一步，创建邻接矩阵存储的有向图，直接新创建MG的对象即可。调用MG中的createDN创建图方法，这样图就创建好了，然后调用MG中的print方法将该图的邻接矩阵输出。第二步，创建邻接表存储的图的对象，这时，可以直接调用测试类中的creatAG方法，把上面的邻接矩阵图的数据传入就行了。最后，输出该图的邻接表。具体实现如：//主方法publicstaticvoidmain(String[]args){//创建邻接矩阵图MGmap=newMG();map.createDN();System.out.println(输出该图的邻接矩阵形式为:);//输出该图的邻接矩阵形式map.print();System.out.println(输出该图的邻接表形式为:);//由邻接矩阵图转创邻接表图AGag=creatAG(map);//输出该图的邻接表形式ag.print();}四、测试及结果设计模型如下图：该图的邻接矩阵：ABCA*34B**5C*5*该图的邻接表：下面是测试结果如图：543A2(C)51(B)3ΛB2(C)5ΛC1(B)5Λ综上测试数据，该程序基本无误。五、调试情况总结需要注意各种数据的类型，数据的输入等。附1：程序使用说明（可选）该程序实现的功能为：用邻接矩阵法创建一个带权值的有向图并输出该图的邻接矩阵，并且输出改图的邻接表。该程序的使用事项：1.需要按要求输入信息，顶点均为字符串类型，2.最好事先做好预期的模型与数据，再进行输入验证。附2：源程序清单这里只给出测试类：publicclasstest{//主方法publicstaticvoidmain(String[]args){//创建邻接矩阵图MGmap=newMG();map.createDN();System.out.println(输出该图的邻接矩阵形式为:);//输出该图的邻接矩阵形式map.print();System.out.println(输出该图的邻接表形式为:);//由邻接矩阵图转创邻接表图AGag=creatAG(map);//输出该图的邻接表形式ag.print();}//由邻接矩阵存储形式的图转创建邻接表存储形式的图publicstaticAGcreatAG(MGmap){AGag=newAG();ag.vexnum=map.vexnum;ag.vexs=newVNode[map.vexs.length];for(inti=0;imap.vexs.length;i++)ag.vexs[i]=newVNode(map.vexs[i]);for(inti=0;imap.vexnum;i++){for(intj=0;jmap.vexnum;j++)if(map.arcs[i][j]!=map.INFINITY)ag.addarc(i,j,map.arcs[i][j]);}returnag;}}