数据结构程序设计实验报告-陈.doc

数据结构课程设计实验报告题 目 图的基本操作及应用 学 院 商学院 专 业 信息管理与信息系统 班 级 信息101 学 号 201052275125 学生姓名 陈蒋昊 同组成员 楼炜 江舟 张垚跃 曹伟明 费泽融 杨钰琨指导教师 刘小晶 编写日期 2012年6月29日 一、 问题描述： 图的基本操作及应用主要解决的问题包括，图的建立，图的存储结构，图的遍历（广度和深度优先搜索算法）和一些图的应用，如最小生成树，最短路径，关键路径等。本课程设计解决图的基本操作问题，此外还添加图的应用举例，最小生成树和最短路径。二、 问题分析：我所负责的是图的广度遍历。所以我先假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，首先访问出发点v，并将其标记为已访问过，输入队列中；然后访问v的任意一个邻接点w1、w2、。然后再按此顺序访问w1、w2、的各个还未被访问过的邻接点。重复上述过程，直到图中所有的点都被访问过为止。也就是说广度优先遍历是一种分层的搜索过程，每向前走一步就可能访问一批定点。并且该遍历不是一个递归的过程。三、 数据结构描述：图的存储结构我这次选择的是邻接矩阵，用来表示顶点之间的相邻关系。四、 算法设计:我负责的是图问题中的深度遍历。2、具体算法package javaapplication1;/用于实现广度优先搜索的队列类class Queue private final int SIZE=20; private int queArray; private int front; private int rear; public Queue() queArray=new intSIZE; front=0; rear=-1; public void insert(int j) if(rear=SIZE-1) rear=-1; queArray+rear=j; public int remove() int temp=queArrayfront+; if(front=SIZE) front=0; return temp; public boolean isEmpty() return (rear+1=front)|(front+SIZE-1=rear); package javaapplication1;/图类class Graph private final int MAX_VERTS=20; private Vertex vertexList; private int adjMat; private int nVerts; private StackX theStack; private Queue theQueue; public Graph() vertexList=new VertexMAX_VERTS; adjMat=new intMAX_VERTSMAX_VERTS; nVerts=0; for (int j = 0; j MAX_VERTS; j+) for (int k = 0; k ); public void showGraphyMatrix() for(int i=0;i5;i+) for(int j=0;j5;j+) System.out.print(adjMatij); System.out.println(); /得到与v顶点邻接且未访问过的顶点标号 public int getAdjUnvisitedVertex(int v) for (int j = 0; j nVerts; j+) if(adjMatvj=1&vertexListj.wasVisited=false) return j; return -1; /广度优先搜索 public void bfs() vertexList0.wasVisited=true; displayVertex(0); theQueue.insert(0); int v2; while(!theQueue.isEmpty() int v1=theQueue.remove(); while(v2=getAdjUnvisitedVertex(v1)!=-1) vertexListv2.wasVisited=true; displayVertex(v2); theQueue.insert(v2); for (int j = 0; j nVerts; j+) vertexListj.wasVisited=false; package javaapplication1;/TEST类import java.util.Scanner;public class TEST public final static int INFINITY = Integer.MAX_VALUE; static final int maxVertices = 100; static Character a = new Character(A), new Character(B), new Character(C), new Character(D), new Character(E), new Character(F), new Character(G), new Character(H); public static void createGraph(AdjMWGraph g, Object v, int n, RowColWeight rc, int e) throws Exception for (int i = 0; i n; i+) g.insertVertex(vi); for (int k = 0; k e; k+) g.insertEdge(rck.row, rck.col, rck.weight); public static void main(String args) throws Exception Scanner sc = new Scanner(System.in); Graph b = new Graph(); AdjMWGraph g = new AdjMWGraph(maxVertices); while (true) System.out.println( 0-建图1-深度优先遍历2-广度优先遍历3-最小生成树4-图的的最短路径5-关键路径 6-退出); System.out.print(请输入选择(0-6):); int i = sc.nextInt(); switch (i) case 0: b.addVertex(a); b.addVertex(b); b.addVertex(c); b.addVertex(d); b.addVertex(e); b.addEdge(0, 1); b.addEdge(0, 2); b.addEdge(0, 3); b.addEdge(1, 4); b.addEdge(2, 3); b.addEdge(2, 4); System.out.println(邻接矩阵为:); b.showGraphyMatrix(); break; case 2: System.out.println(广度优先遍历:); b.bfs(); System.out.println(End); break;五、详细程序清单：package javaapplication1;/顶点类class Vertex public char label; public boolean wasVisited; public Vertex(char lab) label=lab; wasVisited=false; /深度遍历使用的栈package javaapplication1;class StackX private final int SIZE=20; private int st; private int top; public StackX() st=new intSIZE; top=-1; public void push(int j) st+top=j; public int pop() return sttop-; public int peek() return sttop; public boolean isEmpty() return top=-1; package javaapplication1;/用于实现广度优先搜索的队列类class Queue private final int SIZE=20; private int queArray; private int front; private int rear; public Queue() queArray=new intSIZE; front=0; rear=-1; public void insert(int j) if(rear=SIZE-1) rear=-1; queArray+rear=j; public int remove() int temp=queArrayfront+; if(front=SIZE) front=0; return temp; public boolean isEmpty() return (rear+1=front)|(front+SIZE-1=rear); package javaapplication1;/图类class Graph private final int MAX_VERTS=20; private Vertex vertexList; private int adjMat; private int nVerts; private StackX theStack; private Queue theQueue; public Graph() vertexList=new VertexMAX_VERTS; adjMat=new intMAX_VERTSMAX_VERTS; nVerts=0; for (int j = 0; j MAX_VERTS; j+) for (int k = 0; k ); public void showGraphyMatrix() for(int i=0;i5;i+) for(int j=0;j5;j+) System.out.print(adjMatij); System.out.println(); /得到与v顶点邻接且未访问过的顶点标号 public int getAdjUnvisitedVertex(int v) for (int j = 0; j nVerts; j+) if(adjMatvj=1&vertexListj.wasVisited=false) return j; return -1; /深度优先搜索使用栈 public void dfs() vertexList1.wasVisited=true; displayVertex(1); theStack.push(1); while(!theStack.isEmpty() int v=getAdjUnvisitedVertex(theStack.peek(); if(v=-1) theStack.pop(); else vertexListv.wasVisited=true; displayVertex(v); theStack.push(v); for(int j=0;jnVerts;j+) vertexListj.wasVisited=false; /广度优先搜索 public void bfs() vertexList0.wasVisited=true; displayVertex(0); theQueue.insert(0); int v2; while(!theQueue.isEmpty() int v1=theQueue.remove(); while(v2=getAdjUnvisitedVertex(v1)!=-1) vertexListv2.wasVisited=true; displayVertex(v2); theQueue.insert(v2); for (int j = 0; j nVerts; j+) vertexListj.wasVisited=false; package javaapplication1;/线性表接口public interface List public void insert(int i,Object obj) throws Exception; public Object delete(int i) throws Exception; public Object getData(int i) throws Exception; public int size(); public boolean isEmpty();package javaapplication1;/顺序表类class SeqList implements Listfinal int defaultSize = 10;int maxSize;int size;Object listArray;public SeqList()initiate(defaultSize); public SeqList(int size)initiate(size);private void initiate(int sz)maxSize = sz;size = 0;listArray = new Objectsz;public void insert(int i,Object obj) throws Exceptionif (size = maxSize) throw new Exception(顺序表已满无法插入！);if (i size)throw new Exception(参数错误！);for(int j = size; j i; j-)listArrayj = listArrayj-1;listArrayi = obj;size+; public Object delete(int i) throws Exceptionif(size = 0)throw new Exception(顺序表已空无法删除！);if (i size-1)throw new Exception(参数错误！);Object it = listArrayi;for(int j = i; j size-1; j+)listArrayj = listArrayj+1; size-;return it;public Object getData(int i) throws Exceptionif(i = size)throw new Exception(参数错误！);return listArrayi;public int size()return size;public boolean isEmpty()return size = 0;public int MoreDataDelete(SeqList L, Object x) throws Exceptionint i, j;int tag = 0;for(i = 0; i L.size; i+)if(x.equals(L.getData(i)L.delete(i);i -;tag = 1;return tag;package javaapplication1;public class RowColWeightint row;int col;int weight;public RowColWeight(int r, int c, int w)row = r;col = c;weight = w;public static void createGraph(AdjMWGraph g, Object v, int n, RowColWeight rc, int e) throws Exceptionfor(int i = 0; i n; i +)g.insertVertex(vi);for(int k = 0; k e; k +)g.insertEdge(rck.row, rck.col, rck.weight);package javaapplication1;public class Dijkstrastatic final int maxWeight = 9999;public static void dijkstra(AdjMWGraph g, int v0, int distance, int path) throws Exceptionint n = g.getNumOfVertices();int s = new intn;int minDis, u = 0;for(int i = 0; i n; i +)distancei = g.getWeight(v0, i);si = 0;if(i != v0 & distancei maxWeight)pathi = v0;elsepathi = -1;sv0 = 1;for(int i = 1; i n; i +)minDis = maxWeight;for(int j = 0; j n; j +)if(sj = 0 & distancej minDis)u = j;minDis = distancej;if(minDis = maxWeight) return;su = 1;for(int j = 0; j n; j +)if(sj = 0 & g.getWeight(u, j) maxWeight & distanceu + g.getWeight(u, j) distancej)distancej = distanceu + g.getWeight(u, j);pathj = u;package javaapplication1;public class AdjMWGraphstatic final int maxWeight = 10000;private SeqList vertices; /存储结点的顺序表private int edge;/存储边的二维数组private int numOfEdges;/边的个数public AdjMWGraph(int maxV)/构造函数，maxV为结点个数vertices = new SeqList(maxV);edge = new intmaxVmaxV;for(int i = 0; i maxV; i +)for(int j = 0; j maxV; j +)if(i = j)edgeij = 0;elseedgeij = maxWeight;numOfEdges = 0;public int getNumOfVertices()/返回结点个数return vertices.size;public int getNumOfEdges()/返回边的个数return numOfEdges; public Object getValue(int v) throws Exception/返回结点v的数据元素return vertices.getData(v);public int getWeight(int v1, int v2) throws Exception/返回边的权值if(v1 = vertices.size | v2 = vertices.size)throw new Exception(参数v1或v2越界出错！);return edgev1v2;public void insertVertex(Object vertex) throws Exception/插入结点vertices.insert(vertices.size, vertex);public void insertEdge(int v1, int v2, int weight) throws Exception/插入边，权值为weightif(v1 = vertices.size | v2 = vertices.size)throw new Exception(参数v1或v2越界出错！);edgev1v2 = weight; /置边的权值numOfEdges +;/边的个数加1public void deleteEdge(int v1, int v2) throws Exception/删除边if(v1 vertices.size | v2 vertices.size)throw new Exception(参数v1或v2越界出错！);if(edgev1v2 = maxWeight | v1 = v2)throw new Exception(该边不存在！);edgev1v2 = maxWeight;/置边的权值为无穷大numOfEdges -;/边的个数减1public int getFirstNeighbor(int v) throws Exception/取结点v的第一个邻接结点。若存在返回该结点的下标序号，否则返回-1if(v = vertices.size)throw new Exception(参数v越界出错！);for(int col = 0; col 0 & edgevcol maxWeight)return col;return - 1;public int getNextNeighbor(int v1, int v2) throws Exception/取结点v1的邻接结点v2后的邻接结点/若存在返回该结点的下标序号，否则返回-1if(v1 = vertices.size | v2 = vertices.size)throw new Exception(参数v1或v2越界出错！);for(int col = v2 + 1; col 0 & edgev1col maxWeight)return col;return - 1;package javaapplication1;import java.util.Scanner;interface IGraph void createGraph(); int getVexNum(); int getArcNum(); Object getVex(int v)throws Exception; int locateVex(Object vex); int firstAdjVex(int v)throws Exception; int nextAdjVex(int v,int w)throws Exception;enum GraphKindUDG,DG,UDN,DNpublic class MGraph implements IGraph public final static int INFINITY = Integer.MAX_VALUE;private GraphKind kind;private int vexNum, arcNum;private Object vexs;private int arcs;public MGraph() this(null, 0, 0, null, null);public MGraph(GraphKind kind, int vexNum, int arcNum, Object vexs,int arcs) this.kind = kind;this.vexNum = vexNum;this.arcNum = arcNum;this.vexs = vexs;this.arcs = arcs;public void createGraph() Scanner sc = new Scanner(System.in);System.out.println(请输入图的类型：);GraphKind kind = GraphKind.valueOf(sc.next();switch (kind) case UDG:createUDG();return;case DG:createDG();return;case UDN:createUDN();return;case DN:createDN();return;private void createUDG() ;private void createDG() ;private void createUDN() Scanner sc = new Scanner(System.in);System.out.println(请分别输入图的顶点数、图的边数：);vexNum = sc.nextInt();arcNum = sc.nextInt();vexs = new ObjectvexNum;System.out.println(请分别输入图的各个顶点：);for (int v = 0; v vexNum; v+)vexsv = sc.next();arcs = new intvexNumvexNum;for (int v = 0; v vexNum; v+)for (int u = 0; u vexNum; u+)arcsvu = INFINITY;System.out.println(请输入各个边是我两个顶点及其权值：);for (int k = 0; k arcNum; k+) int v = locateVex(sc.next();int u = locateVex(sc.next();arcsvu = arcsuv = sc.nextInt();private void createDN() Scanner sc = new Scanner(System.in);System.out.println(请分别输入图的顶点数、图的边数：);vexNum = sc.nextInt();arcNum = sc.nextInt();vexs = new ObjectvexNum;System.out.println(请分别输入图的各个顶点：);for (int v = 0; v vexNum; v+)vexsv = sc.next();arcs = new intvexNumvexNum;for (int v = 0; v vexNum; v+)for (int u = 0; u vexNum; u+)arcsvu = INFINITY;System.out.println(请输入各个边的两个顶点及其权值:);for (int k = 0; k arcNum; k+) int v = locateVex(sc.next();int u = locateVex(sc.next();arcsvu = sc.nextInt();public int getVexNum() return vexNum;public int getArcNum() return arcNum;public int locateVex(Object vex) for (int v = 0; v vexNum; v+)if (vexsv.equals(vex)return v;return -1;public Object getVex(int v) throws Exception if (v = vexNum)throw new Exception(第+v+个顶点不存在！);return vexsv;public int firstAdjVex(int v) throws Exception if (v = vexNum)throw new Exception(第+v+个顶点不存在！);for (int j = 0; j vexNum; j+)if (arcsvj != 0 & arcsvj INFINITY)return j;return -1;public int nextAdjVex(int v, int w) throws Exception if (v = vexNum)throw new Exception(第+v+个顶点不存在！);for (int j = w + 1; j vexNum; j+)if (arcsvj != 0 & arcsvj INFINITY)return j;return -1;public GraphKind getKind() return kind; public void setArcNum(int arcNum) this.arcNum = arcNum; public void setA