图的表示和操作邻接矩阵

1、 实验六 图的表示和操作 学号：200908204136 姓名：熊军 日期：第11周一、 实验目的和要求理解图的基本概念，掌握图的邻接矩阵和邻接表储存结构，掌握对图进行插入、删除等操作的实现方法，掌握图的深度优先搜索额广度优先搜索遍历：理解最小生成树的概念，掌握构造最小树的Prim算法和Kruskal算法：掌握求单源最短路径问题的Dijkstra算法。二、 实验内容 1、【实验内容描述】 分别对以邻接矩阵和邻接表存储的图，实现下列操作： （1）求图中的边数。 （2）求有向图中各顶点的入度、出度。 （3*）判断指定的一天路径是否为回路。 2、逻辑结构设计【描述所用逻辑结构，给出逻辑操作接口】 本

2、实验采用的是逻辑设计结构为图结构，图是一种元素之间具有多对多关系的非线性数据结构。图中的每个元素可有多个前驱元素和多个后继元素，任意两个元素都可以相邻。 逻辑操作接口如下：public interface GGraph<E> /图接口 int vertexCount(); /返回顶点数 E get(int i); /返回顶点vi的数据元素 boolean insertVertex(E vertex); /插入一个顶点 boolean insertEdge(int i, int j, int weight); /插入一条权值为weight的边vi,vj boolean removeV

3、ertex(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;pub

4、lic class AdjMatrixGraph<E> protected SeqList<E> vertexlist; protected int adjmatrix; private final int MAX_WEIGHT = Integer.MAX_VALUE; public AdjMatrixGraph(int n) this.vertexlist = new SeqList<E>(n); this.adjmatrix = new intnn; for (int i=0; i<n; i+) for (int j=0; j<n; j+)

5、this.adjmatrixij= (i=j) ? 0 : MAX_WEIGHT; public AdjMatrixGraph(E vertices, Edge edges) this(vertices.length); for (int i=0; i<vertices.length; i+) insertVertex(verticesi); for (int j=0; j<edges.length; j+) insertEdge(edgesj); public AdjMatrixGraph(SeqList<E> list, Edge edges) this(list.

6、length(); this.vertexlist = list; for (int j=0; j<edges.length; j+) insertEdge(edgesj); public int vertexCount() return this.vertexlist.length(); public E get(int i) return this.vertexlist.get(i); public boolean insertVertex(E vertex) return this.vertexlist.add(vertex); public boolean insertEdge(

7、int i, int j, int weight) if (i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j && adjmatrixij=MAX_WEIGHT) this.adjmatrixij=weight; return true; return false; public boolean insertEdge(Edge edge) if (edge!=null) return insertEdge(edge.star

8、t, edge.dest, edge.weight); return false; public String toString() String str= "顶点集合："+vertexlist.toString()+"n" str += "邻接矩阵: n" int n = vertexCount(); for (int i=0; i<n; i+) for(int j=0; j<n; j+) if (adjmatrixij=MAX_WEIGHT) str += " " else str += "

9、; "+adjmatrixij; str += "n" return str; public boolean removeEdge(int i, int j) if (i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j && this.adjmatrixij!=MAX_WEIGHT) this.adjmatrixij=MAX_WEIGHT; return true; return false; p

10、ublic boolean removeVertex(int v) int n=vertexCount(); if (v>=0 && v<n) this.vertexlist.remove(v); for (int i=v; i<n-1; i+) for (int j=0; j<n; j+) this.adjmatrixij = this.adjmatrixi+1j; for (int j=v; j<n-1; j+) for (int i=0; i<n-1; i+) this.adjmatrixij = this.adjmatrixij+1;

11、 return true; return false; public int getFirstNeighbor(int v) return getNextNeighbor(v, -1); public int getNextNeighbor(int v, int w) if (v>=0 && v<vertexCount() && w>=-1 && w<vertexCount() && v!=w) for (int j=w+1; j<vertexCount(); j+) if (adjmatrixvj&

12、gt;0 && adjmatrixvj<MAX_WEIGHT) return j; return -1; public AdjMatrixGraph minSpanTree_prim() Edge mst = new EdgevertexCount()-1; for (int i=0; i<mst.length; i+) msti = new Edge(0, i+1, adjmatrix0i+1); System.out.print("mst数组初值："); for(int j=0; j<mst.length; j+) System.out

13、.print(mstj.toString(); for (int i=0; i<mst.length; i+) int minweight = MAX_WEIGHT; int min = i; for (int j=i; j<mst.length; j+) if (mstj.weight<minweight) minweight = mstj.weight; min = j; Edge temp = msti; msti = mstmin; mstmin = temp; int u = msti.dest; for (int j=i+1; j<mst.length; j

14、+) int v = mstj.dest; if (adjmatrixuv<mstj.weight) mstj.weight = adjmatrixuv; mstj.start = u; System.out.print("nmst数组："); for(int j=0; j<mst.length; j+) System.out.print(mstj.toString(); return new AdjMatrixGraph(this.vertexlist, mst); private String toString(int table) if (table!=n

15、ull && table.length>0) String str="" for(int i=0; i<table.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;

16、 sv = 1; for (int i=0; i<n; i+) disti = this.adjmatrixvi; if (i!=v && disti<MAX_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; i&l

17、t;n; i+) int mindist=MAX_WEIGHT, u=0; for (int j=0; j<n; j+) if (sj=0 && distj<mindist) u = j; mindist = distj; su = 1; for (int j=0; j<n; j+) if(sj=0 && this.adjmatrixuj<MAX_WEIGHT && distu+this.adjmatrixuj<distj) distj = distu + this.adjmatrixuj; pathj = u; S

18、ystem.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

19、) 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;i<vertexCount();i+) for(int j=0;j<vertexCount();j+) if(adjmatrixij!=0&&adjmat

20、rixij!=MAX_WEIGHT) k+; return k; public int inDgree(int j) /计算下标为j的结点的入度 int m=0; if(j>=0&&j<vertexCount() for(int i=0;i<vertexCount();i+) if(adjmatrixij!=0&&adjmatrixij!=MAX_WEIGHT) m+; return m; else return -1; public int outDgree(int i) /计算下标为i的顶点的出度 int m=0; if(i>=0&a

21、mp;&i<vertexCount() for(int j=0;j<vertexCount();j+) if(adjmatrixij!=0&&adjmatrixij!=MAX_WEIGHT) m+; return m; else return -1; public int isEdge(int i,int j) if(i>=0 && i<vertexCount() && j>=0 && j<vertexCount() && i!=j) if(adjmatrixij!=MA

22、X_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","

23、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<String> graph1 = new AdjMatrixGraph<String>(vertices, edges); System.out.println("带权有向图:"+graph1.toString(); System.out.println("图边数为:"+graph1.edgeCount(); System.out.println(); for(int i=0;i<graph1.vertexCount();i+