《武汉纺织大学《数据结构》实验报告3.doc》由会员分享，可在线阅读，更多相关《武汉纺织大学《数据结构》实验报告3.doc（23页珍藏版）》请在三一文库上搜索。
1、武汉纺织大学数据结构实验报告班级： 管工类 专业 班 姓名： 序号： 实验时间： 2014 年 5 月 16 日 指导教师： 实验三：图的基本操作与应用一、实验目的： 1、掌握图的几种主要存储方法及基本操作2、掌握图的两种遍历方法3、掌握利用普里姆算法和克鲁斯卡尔算法求取最小生成树的方法4、掌握求取AOE网关键路径的方法，以实现项目时间管理二、实验内容：1、编写程序，输出图的邻接矩阵，输出两种遍历序列，并求出最小生成树。 实验步骤： 、在Java语言编辑环境中新建程序，输入顶点集合和边集合，构造一个图7-15所示的带权图，可参考书本225页示例程序； 、对该带权图，进行插入顶点、插入边、删除顶
2、点、删除边操作，并输出操作后的邻接矩阵，可参考书本226-228页示例程序； 、输出从顶点A开始的深度优先遍历和广度优先遍历的序列，可参考书本238、240页示例程序； 、输出运用普里姆算法求出的最小生成树，可参考书本245页示例程序。2、设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。实验步骤： 、在Java语言编辑环境中新建程序，输入如下图所示的AOE网； 、按照关键路径求取步骤，求出各个顶点的最早开始时间和最迟开始时间； 、求出各个活动的最早开始时间和最迟开始时间； 、找出该AOE网的关键路径，并计算出该项目的完成时间。关键路径相关时间知识点： 设活动ai由弧(即从
3、顶点j到k)表示，其持续时间记为dut(),则： e(i)=ve(j) l(i)=vl(k)-dut()求ve(i)和vl(j)分两步： （1）.从ve(1)=0开始向前递推ve(j)=Maxve(i)+dut()T, 2=j=n ，其中，T是所有以j为弧头的弧的集合。（2）.从vl(n)=ve(n)开始向后递推vl(i)=Minvl(j)-dut() S,1=i=n-1，其中，S是所有以i为弧尾的弧的集合。求关键路径的算法： 、输入e条弧，建立AOE网的存储结构； 、从起始点出发，令ve0=0，按拓扑顺序求其余各顶点的最早发生时间vei(1=i=i=0)； 、根据各顶点的ve和vl值，求每条
4、弧s的最早开始时间e(s)和最迟开始时间l(s)。若某弧满足条件e(s)=l(s)，则为关键活动。三、操作步骤：Test1代码：Graph1.javapackage Frist;public class Graph1 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, 0, 5), new Edge(1, 2, 7), new Edge(1, 3, 6),new Edge(2, 1,
5、7), new Edge(2, 3, 8), new Edge(2, 4, 3),new Edge(3, 0, 2), new Edge(3, 1, 6), new Edge(3, 2, 8),new Edge(3, 4, 9), new Edge(4, 2, 3), new Edge(4, 3, 9) ;AdjMatrixGraph graph = new AdjMatrixGraph(vertices,edges);System.out.println(带权无向图, + graph.toString();System.out.println(插入顶点F,插入边(A,F,20),删除顶点C,
6、删除边(D,E);int i = graph.insertVertex(F);graph.insertEdge(0, i, 20);graph.insertEdge(i, 0, 20);graph.removeVertex(2);graph.removeEdge(2, 3);graph.removeEdge(3, 2);System.out.println(graph.toString();AdjMatrixGraph graph1 = new AdjMatrixGraph(vertices,edges);System.out.print(深度优先遍历序列为：);graph1.DFSTrave
7、rse(0);System.out.print(广度优先遍历序列为：);graph1.BFSTraverse(0);AdjMatrixGraph graph2 = new AdjMatrixGraph(vertices,edges);System.out.print(带权无向图, + graph2.toString();graph2.minSpanTree_prim();LList.javapackage Frist;public interface LList boolean isEmpty();int length();T get(int i);void set(int i, T x);v
8、oid insert(int i, T x);T remove(int i);void removeAll();QQueue.javapackage Frist;public interface QQueue boolean isEmpty();void enqueue(T x);T dequeue();SeqList.javapackage Frist;public class SeqList implements LList private Object element;private int len;public SeqList(int size) this.element = new
9、Objectsize;this.len = 0;public SeqList() this(64);public boolean isEmpty() return this.len = 0;public int length() return this.len;public T get(int i) if (i = 0 & i = 0 & i 0)str += this.element0.toString();for (int i = 1; i this.len; i+)str += , + this.elementi.toString();return str + );public void
10、 insert(int i, T x) if (x = null)return;if (this.len = element.length) Object temp = this.element;this.element = new Objecttemp.length * 2;for (int j = 0; j temp.length; i+)this.elementi = tempj;if (i this.len)i = this.len;for (int j = this.len - 1; j = i; j-)this.elementj + 1 = this.elementj;this.e
11、lementi = x;this.len+;public void append(T x) insert(this.len, x);public T remove(int i) if (this.len = 0 | i = this.len)return null;T old = (T) this.elementi;for (int j = i; j this.len - 1; j+)this.elementj = this.elementj + 1;this.elementthis.len - 1 = null;this.len-;return old;public void removeA
12、ll() this.len = 0;SeqQueue.javapackage Frist;public class SeqQueue implements QQueue private Object element;private int front, rear;public SeqQueue(int length) if (length 64)length = 64;this.element = new ObjectMath.abs(length);this.front = this.rear = 0;public SeqQueue() this(64);public boolean isE
13、mpty() return this.front = this.rear;public void enqueue(T x) if (x = null)return;if (this.front = (this.rear + 1) % this.element.length) Object temp = this.element;this.element = new Objecttemp.length * 2;int i = this.front, j = 0;while (i != this.rear) this.elementj = tempi;i = (i + 1) % temp.leng
14、th;j+;this.front = 0;this.rear = j;this.elementthis.rear = x;this.rear = (this.rear + 1) % this.element.length;public T dequeue() if (isEmpty()return null;T temp = (T) this.elementthis.front;this.front = (this.front + 1) % this.element.length;return temp;public String toString() String str = (;if (!
15、isEmpty() str += this.elementthis.front.toString();int i = (this.front + 1) % this.element.length;while (i != this.rear) str += , + this.element.length;return str + );GGraph.javapackage Frist;public interface GGraph public static final int MAX_WEIGHT = 99999;int vertexCount();T get(int i);int getWei
16、ght(int i, int j);int insertVertex(T x);void insertEdge(int i, int j, int weight);void removeEdge(int i, int j);void removeVertex(int i);int getNextNeighbor(int i, int j);void DFSTraverse(int i);void BFSTraverse(int i);AbstractGraph.javapackage Frist;public abstract class AbstractGraph implements GG
17、raph public abstract int vertexCount();public abstract T get(int i);public abstract int getNextNeighbor(int i, int j);public void DFSTraverse(int i) boolean visited = new booleanthis.vertexCount();int j = i;do if (!visitedj) System.out.print();this.depthfs(j, visited);System.out.print();j = (j + 1)
18、% this.vertexCount(); while (j != i);System.out.println();private void depthfs(int i, boolean visited) System.out.print(this.get(i) + );visitedi = true;int j = this.getNextNeighbor(i, -1);while (j != -1) if (!visitedj)depthfs(j, visited);j = this.getNextNeighbor(i, j);public void BFSTraverse(int i)
19、boolean visited = new booleanthis.vertexCount();int j = i;do if (!visitedj) System.out.print();breadthfs(j, visited);System.out.print();j = (j + 1) % this.vertexCount(); while (j != i);System.out.println();private void breadthfs(int i, boolean visited) System.out.print(this.get(i) + );visitedi = tru
20、e;SeqQueue que = new SeqQueue(this.vertexCount();que.enqueue(new Integer(i);while (!que.isEmpty() i = que.dequeue().intValue();int j = this.getNextNeighbor(i, -1);while (j != -1) if (!visitedj) System.out.print(this.get(j) + );visitedj = true;que.enqueue(new Integer(j);j = this.getNextNeighbor(i, j)
21、;public abstract int getWeight(int i, int j);public void minSpanTree_prim() Edge mst = new EdgevertexCount() - 1;for (int i = 0; i mst.length; i+)msti = new Edge(0, i + 1, this.getWeight(0, i + 1);for (int i = 0; i mst.length; i+) int minweight = MAX_WEIGHT;int min = i;for (int j = i; j mst.length;
22、j+)if (mstj.weight minweight) minweight = mstj.weight;min = j;Edge temp = msti;msti = mstmin;mstmin = temp;int tv = msti.dest;for (int j = i + 1; j mst.length; j+) int v = mstj.dest;if (this.getWeight(tv, v) mstj.weight) msti.weight = this.getWeight(tv, v);mstj.start = tv;System.out.print(n最小生成树边的集合
23、:);int mincost = 0;for (int i = 0; i mst.length - 1; i+) System.out.print(msti + );mincost += msti.weight;System.out.print(,最小代价为 + mincost);AdjMatrixGraph.javapackage Frist;public class AdjMatrixGraph extends AbstractGraph protected SeqList vertexlist;protected int adjmatrix;private final int MAX_W
24、EIGHT = 99999;public AdjMatrixGraph(int size) size = size 10 ? 10 : size;this.vertexlist = new SeqList(size);this.adjmatrix = new intsizesize;for (int i = 0; i size; i+)for (int j = 0; j size; j+)this.adjmatrixij = (i = j) ? 0 : MAX_WEIGHT;public AdjMatrixGraph(T vertices, Edge edges) this(vertices.
25、length);if (vertices = null)return;for (int i = 0; i vertices.length; i+)insertVertex(verticesi);if (edges != null)for (int j = 0; j 0 & i = 0 & j this.adjmatrix.length) int temp = adjmatrix, i, j;this.adjmatrix = new inttemp.length * 2temp.length * 2;for (i = 0; i temp.length; i+) for (j = 0; j tem
26、p.length; j+)this.adjmatrixij = tempij;for (j = temp.length; j temp.length * 2; j+)this.adjmatrixij = MAX_WEIGHT;for (i = temp.length; i temp.length * 2; i+)for (j = 0; j temp.length * 2; j+)this.adjmatrixij = (i = j) ? 0 : MAX_WEIGHT;return this.vertexlist.length() - 1;public int vertexCount() retu
27、rn this.vertexlist.length();public T get(int i) return this.vertexlist.get(i);public int getWeight(int i, int j) return this.adjmatrixij;public String toString() String str = 顶点集合： + this.vertexlist.toString() + n邻接矩阵： n;int n = this.vertexCount();for (int i = 0; i n; i+) for (int j = 0; j = 0 & i =
28、 0 & j vertexCount()& i != j)this.adjmatrixij = MAX_WEIGHT;public void removeVertex(int i) int n = this.vertexCount();if (i n)return;this.vertexlist.remove(i);for (int j = 0; j i; j+)for (int k = i + 1; k n; k+)this.adjmatrixjk - 1 = this.adjmatrixjk;for (int j = i + 1; j n; j+)for (int k = 0; k i;
29、k+)this.adjmatrixj - 1k = adjmatrixjk;for (int j = i + 1; j n; j+)for (int k = i + 1; k = 0 & i = -1 & j n & i != j)for (int k = j + 1; k 0& this.adjmatrixik MAX_WEIGHT)return k;return -1;Edge.javapackage Frist;public class Edge implements Comparable public int start, dest, weight;public Edge(int st
30、art, int dest, int weight) super();this.start = start;this.dest = dest;this.weight = weight;public String toString() return ( + start + , + dest + , + weight + );public int compareTo(Edge e) if (this.start != e.start)return this.start = e.start;return this.dest = e.dest;运行结果:Test2代码;GraphT2.javapack
31、age Second;public class GraphT2 public static void main(String args) Graph graph = new Graph(9); graph.add(1); graph.add(2); graph.add(3); graph.add(4); graph.add(5); graph.add(6); graph.add(7); graph.add(8); graph.add(9); graph.addEdge(0, 1, 6); graph.addEdge(0, 2, 4); graph.addEdge(0, 3, 5); graph
32、.addEdge(1, 4, 1); graph.addEdge(2, 4, 1); graph.addEdge(3, 5, 2); graph.addEdge(4, 6, 9); graph.addEdge(4, 7, 7); graph.addEdge(5, 7, 4); graph.addEdge(6, 8, 2); graph.addEdge(7, 8, 4); if (graph.topo() graph.calculate(); int e = graph.getE(); int l = graph.getL(); int key = graph.getKey(); int ve
33、= graph.getVE(); int vl = graph.getVl(); System.out.println(事件的最早发生时间：); for (int w = 0; w ve.length; w+) System.out.print(vew + ); System.out.println(); System.out.println(事件的最晚发生时间：); for (int w = 0; w vl.length; w+) System.out.print(vlw + ); System.out.println(); System.out.println(活动的最早发生时间：); f
34、or (int w = 0; w e.length; w+) System.out.print(ew + ); System.out.println(); System.out.println(活动的最迟发生时间：); for (int w = 0; w l.length; w+) System.out.print(lw + ); System.out.println(); System.out.println(关键活动有：); for (int w = 0; w graph.getKNum(); w+) System.out.print(keyw + ); System.out.println(); Graph.javapackage Second;public class Graph private Vertex vertexs;private Link adjTab;private int pos = -1;private Stack stack;pr