哈尔滨公司做网站,google下载官网,404 wordpress,朋友圈网站广告怎么做一、前言#xff1a; 这是怀化学院的#xff1a;Java数据结构中的一道难度偏难的一道编程题(此方法为博主自己研究#xff0c;问题基本解决#xff0c;若有bug欢迎下方评论提出意见#xff0c;我会第一时间改进代码#xff0c;谢谢#xff01;) 后面其他编程题只要我写完… 一、前言 这是怀化学院的Java数据结构中的一道难度偏难的一道编程题(此方法为博主自己研究问题基本解决若有bug欢迎下方评论提出意见我会第一时间改进代码谢谢) 后面其他编程题只要我写完并成功实现会陆续更新记得三连哈哈! 所有答案供参考不是标准答案是博主自己研究的写法。(这一个题书上也有现成的代码重要的是理解它的算法原理!) 二、题目如下(注意题目有一个要求(难点之一)若一个顶点有两个邻接顶点那么下一个访问顶点的顺序要按照A - Z 的字典顺序访问) (第 2 题) 图的广度优先搜索(难度系数100) 图的广度优先搜索 描述 图的广度优先搜索类似于树的按层次遍历即从某个结点开始先访问该结点然后访问该结点的所有邻接点再依次访问各邻接点的邻接点。如此进行下去直到所有的结点都访问为止。在该题中假定所有的结点以“A”--“Z”中的若干字符表示且要求结点的访问顺序要求根据由“A”至“Z”的字典顺序进行访问。例如有如下图 如果要求从H开始进行广度优先搜索则搜索结果为H-A-E-K-U. 输入 输入只包含一个测试用例第一行为一个自然数n表示顶点的个数第二行为n个大写字母构成的字符串表示顶点接下来是为一个n*n大小的矩阵表示图的邻接关系。数字为0表示不邻接否则为相应的边的长度。 最后一行为一个字符表示要求进行广度优先搜索的起始顶点。 输出 用一行输出广度优先搜索结果起始点为给定的顶点各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”---“Z”的字典顺序。 样例输入 5 HUEAK 0 0 2 3 0 0 0 0 7 4 2 0 0 0 0 3 7 0 0 1 0 4 0 1 0 H 样例输出 H A E K U 三、代码实现(代码的做题原理全部在代码注释中若还有疑问也可以翻书) 补充这里我用到的就是队列去实现广度优先算法因为队列先进先出先进队列的先访问然后再相邻的顶点后进去后访问依次下来就实现成功 (1)我创建了最基本的图类里面有它的很多成员变量与成员的操作方法。(所以代码会很长但是解释了基本原理。实际上的图的广度优先遍历算法就只有一个方法在里面)
package com.fs.graph;import java.util.ArrayList;
import java.util.Collections; //用到工具类Collections
import java.util.LinkedList; //要用到LinkedListed是实现类
import java.util.Queue; //要用到队列接口导包public class Graph_01 {//为了安全性全部用private修饰封装要使用或者赋值只能使用构造方法或者getter、setter方法private ArrayListString arrayList; //这里我用这个ArrayList集合来代替数组去存储输入的每个顶点,并设置集合里面存储的元素是String类型的private int[][] matrix; //这个二维数组用来存储输入的矩阵表示各个顶点相邻边的关系private int vertex; //用来表示顶点的实际个数private int maxVertex; //用来表示顶点的最大数量private boolean[] visit; //用来判断每个顶点是否被访问过public Graph_01(int vertex){this.maxVertex10; //默认设置最大顶点个数为10this.arrayList new ArrayList();this.vertexvertex;}public ArrayListString getArrayList() {return arrayList;}//定位顶点的位置public int indexOfVex(String v){for(int i0;ivertex;i){if(arrayList.get(i).equals(v)){return i; //找到该顶点在集合中的位置}}return -1; //否则返回-1表示没找到该顶点}//传入包含所有顶点的字符串public void insertVer(String vertex01) throws VertexException{if(vertex01.length()maxVertex){throw new VertexException (超出最大顶点数!);}//存入顶点for(int i0;ivertex;i){String str vertex01.charAt(i);arrayList.add(str);}}//存入顶点间边的邻接关系矩阵public void addEdge(int [][] matrix01){this.matrixmatrix01;}//实现图的广度优先搜索算法public String broadFirstSearch(int v) throws VertexException{if(v0||vmaxVertex){//如果这个顶点不在集合中抛出异常throw new VertexException(该顶点不存在);}visit new boolean[vertex]; //初始化判断顶点是否被访问数组StringBuilder sb new StringBuilder(); //用这个方便字符串的添加和删除因为不会产生多余的对象造成内存浪费还有这个没有实现线程安全功能效率更高//队列接口是继承Collection接口它的实现类就有LinkedList类QueueInteger queue new LinkedList(); //说明里面操作时的元素类型是整型的queue.offer(v); //先把第一个访问的顶点进入队列中visit[v]true; //并标记该顶点的访问状态为true,表示访问过//只要队列没空就是所有的顶点还未访问完while(!queue.isEmpty()){ //判断队列是否为空vqueue.poll(); //进队列后登记完访问状态然后出队列sb.append(arrayList.get(v) ); //将遍历完的顶点加入字符串缓冲区ArrayListString arrayList01 new ArrayList();for(int ivertex-1;i0;i--) {//邻接关系矩阵某一行中只要有不为0的值那就是属于v顶点的这一行还有另外有顶点与它有关系//而且要没被访问过或者不是大于整型的最大值(表示无穷无边的关系)if ((matrix[v][i] ! 0) (!visit[i]) (matrix[v][i] ! Integer.MAX_VALUE)) {arrayList01.add(arrayList.get(i)); //将所有满足有关系的顶点全部放在一个集合里.为了满足题目要按照字典顺序访问才这么写的}}//先把某个顶点所有的邻接顶点按照字典顺序排好序Collections.sort(arrayList01);//为了满足条件就需要字典顺序在前的顶点先入队列先出队先被访问。而字典顺序在后的顶点后入队列后出队列后被访问(这样就实现了题目要求)for(int j0;jarrayList01.size();j){//先从字典排序在前的顶点开始操作String strarrayList01.get(j); //获取该顶点int indexindexOfVex(str); //再找到该顶点在之前顶点集合的位置queue.offer(index); //最后把该顶点的入队visit[indexOfVex(str)]true; //并设置已经访问过}}//用问号表达式如果满足前面的就输出问号后面的,否则就是输出nullreturn sb.length()0?sb.substring(0,sb.length()):null; //用这个substring()方法可以将StingBuilder里的字符串缓冲区里的字符串转换成String类型的}
}
//自定义异常类(考试可以不写没做要求)
class VertexException extends Exception{public VertexException(){super();}public VertexException(String message){super(message);}
}
(2)根据题目要求输入创建了测试类
package com.fs.graph;import java.util.Scanner;public class Test_Graph_01 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); //代表顶点个数String vertex sc.next(); //代表的所有顶点的字符串Graph_01 graph new Graph_01(n);try {graph.insertVer(vertex); //输入由各个顶点构成的字符串}catch (VertexException e){e.printStackTrace();return;}int [][] matrix01 new int[n][n];for(int i0;in;i){for(int j0;jn;j){matrix01[i][j]sc.nextInt();}}graph.addEdge(matrix01); //传入邻接关系矩阵String v sc.next(); //传入从某一个指定的顶点去遍历图try{String path graph.broadFirstSearch(graph.indexOfVex(v)); //先传入起始遍历顶点再定位其位置最后调用广度优先算法System.out.print(path); //输出最终遍历结果}catch (VertexException e){e.printStackTrace();}}
}
四、不同情况的代码测试运行结果
1首先是题目中的测试输入样例(最好手打输入测试直接复制可能格式问题导致报错) 2自己测试的输入样例 (测试7个顶点)
1.图展示(手写比较随意字有点丑哈哈) 2.也就是测试输入样例为
(1.)从H顶点开始遍历图(提示最好不要直接复制我的输入样例最好用手跟着打。因为复制完格式有点问题就会报错) 7 HAEBKUD 0 3 2 1 0 0 0 3 0 0 0 1 7 0 2 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 4 0 0 7 0 0 4 0 0 0 0 0 1 0 0 0 H 代码运行后输出的遍历结果 (2.)从D顶点开始遍历图(提示最好不要直接复制我的输入样例最好用手跟着打。因为复制完格式有点问题就会报错) 7 HAEBKUD 0 3 2 1 0 0 0 3 0 0 0 1 7 0 2 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 4 0 0 7 0 0 4 0 0 0 0 0 1 0 0 0 D 代码运行后输出的遍历结果
