圖的表示和操作鄰接矩陣

1、 實驗六 圖的表示和操作 學(xué)號：200908204136 姓名：熊軍 日期：第11周一、 實驗?zāi)康暮鸵罄斫鈭D的基本概念，掌握圖的鄰接矩陣和鄰接表儲存結(jié)構(gòu)，掌握對圖進(jìn)行插入、刪除等操作的實現(xiàn)方法，掌握圖的深度優(yōu)先搜索額廣度優(yōu)先搜索遍歷：理解最小生成樹的概念，掌握構(gòu)造最小樹的Prim算法和Kruskal算法：掌握求單源最短路徑問題的Dijkstra算法。二、 實驗內(nèi)容 1、【實驗內(nèi)容描述】 分別對以鄰接矩陣和鄰接表存儲的圖，實現(xiàn)下列操作： （1）求圖中的邊數(shù)。 （2）求有向圖中各頂點的入度、出度。 （3*）判斷指定的一天路徑是否為回路。 2、邏輯結(jié)構(gòu)設(shè)計【描述所用邏輯結(jié)構(gòu)，給出邏輯操作接口】 本

2、實驗采用的是邏輯設(shè)計結(jié)構(gòu)為圖結(jié)構(gòu)，圖是一種元素之間具有多對多關(guān)系的非線性數(shù)據(jù)結(jié)構(gòu)。圖中的每個元素可有多個前驅(qū)元素和多個后繼元素，任意兩個元素都可以相鄰。 邏輯操作接口如下：public interface GGraph<E> /圖接口 int vertexCount(); /返回頂點數(shù) E get(int i); /返回頂點vi的數(shù)據(jù)元素 boolean insertVertex(E vertex); /插入一個頂點 boolean insertEdge(int i, int j, int weight); /插入一條權(quán)值為weight的邊vi,vj boolean removeV

3、ertex(int v); /刪除序號為v的頂點及其關(guān)聯(lián)的邊 boolean removeEdge(int i, int j); /刪除邊vi,vj int getFirstNeighbor(int v); /返回頂點v的第一個鄰接頂點的序號 int getNextNeighbor(int v, int w); /返回v在w后的下一個鄰接頂點的序號 3、存儲結(jié)構(gòu)設(shè)計【描述物理結(jié)構(gòu)設(shè)計，給出基礎(chǔ)結(jié)構(gòu)類設(shè)計】本實驗的存儲結(jié)構(gòu)采用的是鄰接矩陣表示，圖的鄰接矩陣是表示圖中各頂點之間臨街關(guān)系的矩陣。邏輯結(jié)構(gòu)類設(shè)計如下：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數(shù)組初值："); 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數(shù)組："); 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數(shù)組"+toString(s); System.out.print("tpath數(shù)組"+toString(path); System.out.print("tdist數(shù)組"+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數(shù)組"+toString(s); System.out.print("tpath數(shù)組"+toString(path); System.out.print("tdist數(shù)組"+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() /計算邊數(shù) 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) /計算下標(biāo)為j的結(jié)點的入度 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) /計算下標(biāo)為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; /若存在邊則返回該邊權(quán)值 else return -2; /若不存在邊則返回-2 else return -1; /若輸入值越界則返回-1 4、應(yīng)用設(shè)計【給出應(yīng)用類設(shè)計】package pictrue;import java.util.Scanner;public class GraphMatrix /以鄰接矩陣建立的帶權(quán)有向圖的應(yīng)用 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("帶權(quán)有向圖:"+graph1.toString(); System.out.println("圖邊數(shù)為:"+graph1.edgeCount(); System.out.println(); for(int i=0;i<graph1.vertexCount();i+