图的表示和操作(邻接矩阵).doc

实验六 图的表示和操作 学号：200908204136 姓名：熊军 日期：第11周一、 实验目的和要求理解图的基本概念，掌握图的邻接矩阵和邻接表储存结构，掌握对图进行插入、删除等操作的实现方法，掌握图的深度优先搜索额广度优先搜索遍历：理解最小生成树的概念，掌握构造最小树的Prim算法和Kruskal算法：掌握求单源最短路径问题的Dijkstra算法。二、 实验内容 1、【实验内容描述】 分别对以邻接矩阵和邻接表存储的图，实现下列操作： （1）求图中的边数。 （2）求有向图中各顶点的入度、出度。 （3*）判断指定的一天路径是否为回路。 2、逻辑结构设计【描述所用逻辑结构，给出逻辑操作接口】 本实验采用的是逻辑设计结构为图结构，图是一种元素之间具有多对多关系的非线性数据结构。图中的每个元素可有多个前驱元素和多个后继元素，任意两个元素都可以相邻。 逻辑操作接口如下：public interface GGraph /图接口 int vertexCount(); /返回顶点数 E get(int i); /返回顶点vi的数据元素 boolean insertVertex(E vertex); /插入一个顶点 boolean insertEdge(int i, int j, int weight); /插入一条权值为weight的边vi,vj boolean removeVertex(int v); /删除序号为v的顶点及其关联的边 boolean removeEdge(int i, int j); /删除边vi,vj int getFirstNeighbor(int v); /返回顶点v的第一个邻接顶点的序号 int getNextNeighbor(int v, int w); /返回v在w后的下一个邻接顶点的序号 3、存储结构设计【描述物理结构设计，给出基础结构类设计】本实验的存储结构采用的是邻接矩阵表示，图的邻接矩阵是表示图中各顶点之间临街关系的矩阵。逻辑结构类设计如下：package pictrue;import picture .SeqList;public class AdjMatrixGraph protected SeqList vertexlist; protected int adjmatrix; private final int MAX_WEIGHT = Integer.MAX_VALUE; public AdjMatrixGraph(int n) this.vertexlist = new SeqList(n); this.adjmatrix = new intnn; for (int i=0; in; i+) for (int j=0; jn; j+) this.adjmatrixij= (i=j) ? 0 : MAX_WEIGHT; public AdjMatrixGraph(E vertices, Edge edges) this(vertices.length); for (int i=0; ivertices.length; i+) insertVertex(verticesi); for (int j=0; jedges.length; j+) insertEdge(edgesj); public AdjMatrixGraph(SeqList list, Edge edges) this(list.length(); this.vertexlist = list; for (int j=0; j=0 & i=0 & jvertexCount() & i!=j & adjmatrixij=MAX_WEIGHT) this.adjmatrixij=weight; return true; return false; public boolean insertEdge(Edge edge) if (edge!=null) return insertEdge(edge.start, edge.dest, edge.weight); return false; public String toString() String str= 顶点集合：+vertexlist.toString()+n; str += 邻接矩阵: n; int n = vertexCount(); for (int i=0; in; i+) for(int j=0; j=0 & i=0 & j=0 & vn) this.vertexlist.remove(v); for (int i=v; in-1; i+) for (int j=0; jn; j+) this.adjmatrixij = this.adjmatrixi+1j; for (int j=v; jn-1; j+) for (int i=0; i=0 & v=-1 & wvertexCount() & v!=w) for (int j=w+1; j0 & adjmatrixvjMAX_WEIGHT) return j; return -1; public AdjMatrixGraph minSpanTree_prim() Edge mst = new EdgevertexCount()-1; for (int i=0; imst.length; i+) msti = new Edge(0, i+1, adjmatrix0i+1); System.out.print(mst数组初值：); for(int j=0; jmst.length; j+) System.out.print(mstj.toString(); for (int i=0; imst.length; i+) int minweight = MAX_WEIGHT; int min = i; for (int j=i; jmst.length; j+) if (mstj.weightminweight) minweight = mstj.weight; min = j; Edge temp = msti; msti = mstmin; mstmin = temp; int u = msti.dest; for (int j=i+1; jmst.length; j+) int v = mstj.dest; if (adjmatrixuvmstj.weight) mstj.weight = adjmatrixuv; mstj.start = u; System.out.print(nmst数组：); for(int j=0; j0) String str=; for(int i=0; itable.length-1; i+) str += tablei+,; return str+tabletable.length-1+; return null; public void shortestPath(int v) int n = this.vertexCount(); int dist = new intn; int path = new intn; int s = new intn; sv = 1; for (int i=0; in; i+) disti = this.adjmatrixvi; if (i!=v & distiMAX_WEIGHT) pathi = v; else pathi = -1; System.out.print(ns数组+toString(s); System.out.print(tpath数组+toString(path); System.out.print(tdist数组+toString(dist); for (int i=1; in; i+) int mindist=MAX_WEIGHT, u=0; for (int j=0; jn; j+) if (sj=0 & distjmindist) u = j; mindist = distj; su = 1; for (int j=0; jn; j+) if(sj=0 & this.adjmatrixujMAX_WEIGHT & distu+this.adjmatrixujdistj) distj = distu + this.adjmatrixuj; pathj = u; System.out.print(ns数组+toString(s); System.out.print(tpath数组+toString(path); System.out.print(tdist数组+toString(dist); System.out.println(n从顶点+get(v)+到其他顶点的最短路径如下：); int i=v+1; while (i!=v) int j=i; String pathstr=; while (pathj!=-1) pathstr = ,+get(j)+pathstr; j=pathj; pathstr = (+get(v)+pathstr+)，路径长度为+disti; System.out.println(pathstr); i = (i+1)%n; public int edgeCount() /计算边数 int k=0; for(int i=0;ivertexCount();i+) for(int j=0;j=0&jvertexCount() for(int i=0;i=0&ivertexCount() for(int j=0;j=0 & i=0 & jvertexCount() & i!=j) if(adjmatrixij!=MAX_WEIGHT) return adjmatrixij; /若存在边则返回该边权值 else return -2; /若不存在边则返回-2 else return -1; /若输入值越界则返回-1 4、应用设计【给出应用类设计】package pictrue;import java.util.Scanner;public class GraphMatrix /以邻接矩阵建立的带权有向图的应用 public static void main(String args) String vertices=A,B,C,D,E; Edge edges= new Edge(0,1,5), new Edge(0,3,2), new Edge(1,2,7), new Edge(1,0,6), new Edge(2,4,3), new Edge(3,2,8), new Edge(3,4,9) ; AdjMatrixGraph graph1 = new AdjMatrixGraph(vertices, edges); System.out.println(带权有向图:+graph1.toString(); System.out.println(图边数为:+graph1.edgeCount(); System.out.println(); for(int i=0;igraph1.vertexCount();i+) System.out.println(顶点:+graph1.get(i)+ 入度:+graph1.inDgree(i)+ 出度:+graph1.outDgree(i); System.out.println(); Scanner in=new Scanner(System.in); System.out.println(请输入1个大于0小于+vertices.length+的整数值,作为起始顶点); int a=in.nextInt(); System.out.println(请再输入1个大于0小于+vertices.length+的整数值,作为终止顶点); int b=in.nextInt(); int e=graph1.isEdge(a, b); if(e=-1) System.out.println(输入错误); else if(e=-2) System.out.pr