《数据结构程序设计实验报告-陈》由会员分享，可在线阅读，更多相关《数据结构程序设计实验报告-陈（32页珍藏版）》请在金锄头文库上搜索。
1、 数据结构课程设计实验报告题 目 图的基本操作及应用 学 院 商学院 专 业 信息管理与信息系统 班 级 信息 101 学 号 201052275125 学生姓名 陈蒋昊 同组成员 楼炜 江舟 张垚跃 曹伟明 费泽融 杨钰琨指导教师 刘小晶 编写日期 2012 年 6 月 29 日 一、 问题描述：图的基本操作及应用主要解决的问题包括，图的建立，图的存储结构，图的遍历（广度和深度优先搜索算法）和一些图的应用，如最小生成树，最短路径，关键路径等。本课程设计解决图的基本操作问题，此外还添加图的应用举例，最小生成树和最短路径。二、 问题分析：我所负责的是图的广度遍历。所以我先假设给定图 G 的初态是
2、所有顶点均未曾访问过。在 G 中任选一顶点 v 为初始出发点 (源点)，首先访问出发点 v，并将其标记为已访问过，输入队列中；然后访问 v 的任意一个邻接点 w1、w2 、。然后再按此顺序访问w1、w2、的各个还未被访问过的邻接点。重复上述过程，直到图中所有的点都被访问过为止。也就是说广度优先遍历是一种分层的搜索过程，每向前走一步就可能访问一批定点。并且该遍历不是一个递归的过程。三、 数据结构描述：图的存储结构我这次选择的是邻接矩阵，用来表示顶点之间的相邻关系。四、 算法设计:我负责的是图问题中的深度遍历。W n 是否被访问在已建好的图中输入数据输出广度遍历顺序结束开始广度优先遍历队列将输入队
3、列并输出找出 v 的所有邻接点w 1 、 w 2 w n 。YN2、具体算法package javaapplication1;/用于实现广度优先搜索的队列类class Queueprivate 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 rem
4、ove()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 Queu
5、e theQueue;public Graph() vertexList=new VertexMAX_VERTS;adjMat=new intMAX_VERTSMAX_VERTS;nVerts=0;for (int j = 0; j );public void showGraphyMatrix()for(int i=0;i);public void showGraphyMatrix()for(int i=0;i size)throw new Exception(参数错误！);for(int j = size; j i; j-)listArrayj = listArrayj-1;listArra
6、yi = 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)throw new Exception(参数错误！);return listArrayi;public int size()return size;public boolean isEmpty()return siz
7、e = 0;public int MoreDataDelete(SeqList L, Object x) throws Exceptionint i, j;int tag = 0;for(i = 0; i 的权值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, vert
8、ex);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 v
9、ertices.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(参数
10、v 越界出错！);for(int col = 0; col 0 & edgevcol = vertices.size | v2 = vertices.size)throw new Exception(参数 v1 或 v2 越界出错！ );for(int col = v2 + 1; col 0 & edgev1col = vexNum)throw new Exception(第+v+个顶点不存在！);return vexsv;public int firstAdjVex(int v) throws Exception if (v = vexNum)throw new Exception(第+v+
11、个顶点不存在！);for (int j = 0; j = vexNum)throw new Exception(第+v+个顶点不存在！);for (int j = w + 1; j base) Object obj = elementDatatop - 1; elementDatatop- = null; return obj; else throw new ArrayIndexOutOfBoundsException(stack is null); public String toString() String str = ; for (int i = 0; i 0) System.out.
12、print(g.getValue(pathj);j = pathj;System.out.println(-最短长度为： + distancei); catch (Exception ex) ex.printStackTrace();break;case 5:ArcNode an1 = new ArcNode(3, 2, 2, null);ArcNode an2 = new ArcNode(2, 3, 1, an1);/v2ArcNode an3 = new ArcNode(5, 3, 4, null);ArcNode an4 = new ArcNode(4, 2, 3, an3);/v3Ar
13、cNode an5 = new ArcNode(4, 4, 5, null);ArcNode an6 = new ArcNode(6, 3, 6, an5);/v4ArcNode an7 = new ArcNode(6, 2, 7, null);/v5ArcNode an8 = new ArcNode(6, 1, 8, null);/定义一个图HeadNode n1 = new HeadNode(v1, an2);HeadNode n2 = new HeadNode(v2, an4);HeadNode n3 = new HeadNode(v3, an6);HeadNode n4 = new H
14、eadNode(v4, an7);HeadNode n5 = new HeadNode(v5, an8);HeadNode n6 = new HeadNode(v6, null);HeadNode hns = new HeadNoden1, n2, n3, n4, n5, n6;Stack s = new Stack();Stack t = new Stack();int inDegree = new inthns.length;for (i = 0; i ) * vej等于从源点到顶点 vj 的最长路径的长度 */int ve = new inthns.length;for (i = 0; i vlj - n.data) vli = vlj - n.data;private static void toplogicalOrder(HeadNode hns, Stack s, int inDegree, Stack t, int ve) throws Exception /求每个节点的入度 for (int i = 0; i vej) vej = ve
