南通建设信息网站微网站 具有哪方面的优势

当前位置： 首页 > news >正文

南通建设信息网站,微网站 具有哪方面的优势,长沙网站建设260e,2345网址导航是谷歌吗文章目录 前言深度优先搜索理论基础所有可达路径岛屿数量岛屿最大面积孤岛的总面积沉默孤岛Floyd 算法dijkstra#xff08;朴素版#xff09;最小生成树之primkruskal算法 前言 新手小白记录第一次刷代码随想录 1.自用 抽取精简的解题思路 方便复盘 2.代码尽量多加注释 3.记录… 文章目录 前言深度优先搜索理论基础所有可达路径岛屿数量岛屿最大面积孤岛的总面积沉默孤岛Floyd 算法dijkstra朴素版最小生成树之primkruskal算法 前言 新手小白记录第一次刷代码随想录 1.自用 抽取精简的解题思路 方便复盘 2.代码尽量多加注释 3.记录踩坑 4.边刷边记录更有成就感 5.解题思路绝大部分来自代码随想录【仅自用 无商用】 深度优先搜索理论基础 代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果} }所有可达路径 【题目描述】 给定一个有 n 个节点的有向无环图节点编号从 1 到 n。请编写一个函数找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。 【输入描述】 第一行包含两个整数 NM表示图中拥有 N 个节点M 条边 后续 M 行每行包含两个整数 s 和 t表示图中的 s 节点与 t 节点中有一条路径 【输出描述】 输出所有的可达路径路径中所有节点的后面跟一个空格每条路径独占一行存在多条路径路径输出的顺序可任意。 如果不存在任何一条路径则输出 -1。 注意输出的序列中最后一个节点后面没有空格 例如正确的答案是 1 3 5,而不是 1 3 5 5后面没有空格 【输入示例】 5 5 1 3 3 5 1 2 2 4 4 5 【输出示例】 1 3 5 1 2 4 5 邻接矩阵 import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class Main {static ListListInteger result new ArrayList(); // 收集符合条件的路径static ListInteger path new ArrayList(); // 1节点到终点的路径public static void dfs(int[][] graph, int x, int n) {// 当前遍历的节点x 到达节点nif (x n) { // 找到符合条件的一条路径result.add(new ArrayList(path));return;}for (int i 1; i n; i) { // 遍历节点x链接的所有节点if (graph[x][i] 1) { // 找到 x链接的节点path.add(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.remove(path.size() - 1); // 回溯撤销本节点}}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();// 节点编号从1到n所以申请 n1 这么大的数组int[][] graph new int[n 1][n 1];for (int i 0; i m; i) {int s scanner.nextInt();int t scanner.nextInt();// 使用邻接矩阵表示无向图1 表示 s 与 t 是相连的graph[s][t] 1;}path.add(1); // 无论什么路径已经是从1节点出发dfs(graph, 1, n); // 开始遍历// 输出结果if (result.isEmpty()) System.out.println(-1);for (ListInteger pa : result) {for (int i 0; i pa.size() - 1; i) {System.out.print(pa.get(i) );}System.out.println(pa.get(pa.size() - 1));}} }邻接表 import java.util.;public class Main {static ListListInteger res new ArrayList();static ListInteger path new ArrayList();public static void dfs(ListLinkedListInteger graph, int now, int n) {// 终止条件找到一条从1到n的路径if (now n) {res.add(new ArrayList(path));return;}// 遍历当前节点的所有邻接节点for (int i : graph.get(now)) {path.add(i); // 添加当前节点到路径中dfs(graph, i, n); // 递归探索下一节点path.remove(path.size() - 1); // 回溯移除当前节点}}public static void main(String args[]) {Scanner sc new Scanner(System.in);int n sc.nextInt(); // 节点数int m sc.nextInt(); // 边数// 初始化图的邻接表ListLinkedListInteger graph new ArrayList(n 1);for (int i 0; i n; i) {graph.add(new LinkedList());}// 构建图的邻接表int a, b;while (m– 0) {a sc.nextInt();b sc.nextInt();graph.get(a).add(b); // 从a到b的边}// 从节点1开始路径搜索path.add(1); // 初始路径包含节点1dfs(graph, 1, n);// 如果没有路径if (res.isEmpty()) {System.out.println(-1); // 没有路径} else {// 打印所有路径for (ListInteger re : res) {for (int i 0; i re.size() - 1; i) {System.out.print(re.get(i) );}System.out.println(re.get(re.size() - 1)); // 打印路径的最后一个节点}}} } 岛屿数量 给定一个由 1陆地和 0水组成的矩阵你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。 输入描述 第一行包含两个整数 N, M表示矩阵的行数和列数。 后续 N 行每行包含 M 个数字数字为 1 或者 0。 输出描述 输出一个整数表示岛屿的数量。如果不存在岛屿则输出 0。 输入示例 4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 输出示例 3 数据范围 1 N, M 50 深搜版 import java.util.Scanner;public class Main {static int cnt 0; // 用于计数岛屿数量static int direct[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向的移动// 深度优先搜索public static void dfs(int graph[][], int x, int y, boolean visited[][]) {// 遍历四个方向for (int i 0; i 4; i) {int nextX x direct[i][0]; // 下一个位置的x坐标int nextY y direct[i][1]; // 下一个位置的y坐标// 判断是否越界if (nextX 0 || nextY 0 || nextX graph.length || nextY graph[0].length) {continue; // 如果越界跳过}// 如果当前位置是陆地并且未访问过递归搜索if (!visited[nextX][nextY] graph[nextX][nextY] 1) {visited[nextX][nextY] true; // 标记为已访问dfs(graph, nextX, nextY, visited); // 递归搜索}}}public static void main(String[] args) {int n, m, a;Scanner sc new Scanner(System.in);n sc.nextInt(); // 行数m sc.nextInt(); // 列数int[][] graph new int[n][m]; // 地图boolean[][] visited new boolean[n][m]; // 记录每个位置是否已访问// 读取地图for (int i 0; i n; i) {for (int j 0; j m; j) {a sc.nextInt();graph[i][j] a; // 1表示陆地0表示水域}}// 遍历整个图每当找到一个未访问的陆地执行深度优先搜索for (int i 0; i n; i) {for (int j 0; j m; j) {// 找到一个未访问的陆地开始深度优先搜索if (!visited[i][j] graph[i][j] 1) {cnt; // 找到一个岛屿visited[i][j] true; // 标记为已访问dfs(graph, i, j, visited); // 递归搜索整个岛屿}}}// 输出岛屿的数量System.out.println(cnt);} } 另一种写终止条件的写法 public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 终止条件访问过的节点 或者 遇到海水grid[x][y] 0if (visited[x][y] || grid[x][y] 0) {return;}visited[x][y] true; // 标记当前位置为已访问// 遍历四个方向for (int i 0; i 4; i) {int nextX x dir[i][0];int nextY y dir[i][1];// 检查是否越界if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) {continue;}// 递归调用 DFSdfs(grid, visited, nextX, nextY);}}广搜版 不少同学用广搜做这道题目的时候超时了。 这里有一个广搜中很重要的细节根本原因是只要 加入队列就代表 走过就需要标记而不是从队列拿出来的时候再去标记走过。很多同学可能感觉这有区别吗如果从队列拿出节点再去标记这个节点走过就会发生下图所示的结果会导致很多节点重复加入队列。 import java.util.;public class Main {// 定义四个方向的偏移量下、右、上、左public static int[][] dir {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 下右上左// 自定义pair类用于存储坐标static class pair {int first, second;pair(int x, int y) {this.first x;this.second y;}}// BFS遍历函数public static void bfs(int[][] grid, boolean[][] visited, int x, int y) {Queuepair queue new LinkedListpair(); // 定义坐标队列queue.add(new pair(x, y)); // 入队当前坐标visited[x][y] true; // 标记当前位置为已访问while (!queue.isEmpty()) {int curX queue.peek().first; // 获取队列头的X坐标int curY queue.poll().second; // 获取队列头的Y坐标并出队poll是把对头元素出队了// 遍历四个方向for (int i 0; i 4; i) {// 计算下一个坐标int nextX curX dir[i][0];int nextY curY dir[i][1];// 检查越界if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) {continue;}// 如果没有访问过并且该点是陆地值为1则入队if (!visited[nextX][nextY] grid[nextX][nextY] 1) {queue.add(new pair(nextX, nextY));visited[nextX][nextY] true; // 标记为已访问}}}}public static void main(String[] args) {Scanner sc new Scanner(System.in);// 输入网格的行数和列数int m sc.nextInt();int n sc.nextInt();int[][] grid new int[m][n];boolean[][] visited new boolean[m][n];int ans 0;// 输入网格的每个值0为水域1为陆地for (int i 0; i m; i) {for (int j 0; j n; j) {grid[i][j] sc.nextInt();}}// 遍历网格查找所有的岛屿for (int i 0; i m; i) {for (int j 0; j n; j) {// 如果该点是陆地并且未访问过则说明发现一个新的岛屿if (!visited[i][j] grid[i][j] 1) {ans; // 岛屿数量加一bfs(grid, visited, i, j); // 通过BFS将该岛屿所有的陆地标记为已访问}}}// 输出岛屿数量System.out.println(ans);} } 岛屿最大面积 题目描述 给定一个由 1陆地和 0水组成的矩阵计算岛屿的最大面积。岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿由水平方向或垂直方向上相邻的陆地连接而成并且四周都是水域。你可以假设矩阵外均被水包围。 输入描述 第一行包含两个整数 N, M表示矩阵的行数和列数。后续 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。 输出描述 输出一个整数表示岛屿的最大面积。如果不存在岛屿则输出 0。 输入示例 4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 输出示例 4 写在前面 count是类成员变量如果不加 static它们将被视为实例变量只有通过实例化 Main 类才能访问它们。bfs 方法是静态方法它可以直接通过类名 Main.bfs() 调用。如果不将其设为 static它就需要依赖于一个 Main 类的实例来调用。如果不加 static访问count 以及调用 bfs 会出现问题因为count 是实例变量而 bfs 是静态方法。静态方法只能访问静态变量和静态方法。即使你没有实例化 Main 类你也希望在 main 方法中访问它们这就要求count 也必须是静态的。 dfs 写法一dfs只处理下一个节点即在主函数遇到岛屿就计数为1dfs处理接下来的相邻陆地 import java.util.;public class Main {// 定义四个方向的偏移量右、下、左、上public static int[][] dir {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};static int count; // 记录每次DFS访问的陆地数量// 深度优先搜索 (DFS) 函数public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {for (int i 0; i 4; i) {int nextX x dir[i][0];int nextY y dir[i][1];// 检查越界if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) {continue;}// 如果该位置没有访问过且是陆地则继续DFSif (!visited[nextX][nextY] grid[nextX][nextY] 1) {visited[nextX][nextY] true;count; // 增加当前岛屿的陆地数量dfs(grid, visited, nextX, nextY); // 递归访问相邻的陆地}}}public static void main(String[] args) {Scanner sc new Scanner(System.in);// 输入网格的行数n和列数mint n sc.nextInt();int m sc.nextInt();// 创建网格并填充输入数据int[][] grid new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {grid[i][j] sc.nextInt();}}// 创建一个visited数组用来标记访问过的位置boolean[][] visited new boolean[n][m];int result 0; // 最终记录最大岛屿面积// 遍历每一个格子for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果当前格子是陆地并且未被访问过进行DFSif (!visited[i][j] grid[i][j] 1) {count 1; // 这里遇到陆地了先计数1visited[i][j] true;dfs(grid, visited, i, j); // 递归访问与当前陆地相连的陆地result Math.max(result, count); // 更新最大岛屿面积}}}// 输出结果System.out.println(result);} }写法二dfs处理当前节点即在主函数遇到岛屿就计数为0dfs处理接下来的全部陆地 // 版本二 import java.util.Scanner;public class Main {// 定义四个方向的偏移量右、下、左、上public static int[][] dir {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};static int count; // 记录每次DFS访问的陆地数量// 深度优先搜索 (DFS) 函数public static void dfs(int[][] grid, boolean[][] visited, int x, int y) {// 终止条件访问过的节点 或者 遇到海水if (visited[x][y] || grid[x][y] 0) return;visited[x][y] true; // 标记当前位置为已访问count; // 每访问到一个陆地计数1// 遍历四个方向for (int i 0; i 4; i) {int nextX x dir[i][0];int nextY y dir[i][1];// 检查越界if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) {continue;}// 递归调用 DFSdfs(grid, visited, nextX, nextY);}}public static void main(String[] args) {Scanner sc new Scanner(System.in);// 输入网格的行数n和列数mint n sc.nextInt();int m sc.nextInt();// 创建网格并填充输入数据int[][] grid new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {grid[i][j] sc.nextInt();}}// 创建一个visited数组用来标记访问过的位置boolean[][] visited new boolean[n][m];int result 0; // 最终记录最大岛屿面积// 遍历每一个格子for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果当前格子是陆地并且未被访问过进行DFSif (!visited[i][j] grid[i][j] 1) {count 0; // 遇到陆地时先计数为0进入DFS后开始从1计数dfs(grid, visited, i, j); // 递归访问与当前陆地相连的陆地result Math.max(result, count); // 更新最大岛屿面积}}}// 输出结果System.out.println(result);} } 大家通过注释可以发现两种写法版本一在主函数遇到陆地就计数为1接下来的相邻陆地都在dfs中计算。 版本二 在主函数遇到陆地 计数为0也就是不计数陆地数量都去dfs里做计算。 bfs的代码省略 孤岛的总面积 目描述 给定一个由 1陆地和 0水组成的矩阵岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。 现在你需要计算所有孤岛的总面积岛屿面积的计算方式为组成岛屿的陆地的总数。 输入描述 第一行包含两个整数 N, M表示矩阵的行数和列数。之后 N 行每行包含 M 个数字数字为 1 或者 0。 输出描述 输出一个整数表示所有孤岛的总面积如果不存在孤岛则输出 0。 输入示例 4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 输出示例 沉默孤岛 思路 本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。 Floyd 算法 【题目描述】 小明喜欢去公园散步公园内布置了许多的景点相互之间通过小路连接小明希望在观看景点的同时能够节省体力走最短的路径。 给定一个公园景点图图中有 N 个景点编号为 1 到 N以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。 小明有 Q 个观景计划每个计划都有一个起点 start 和一个终点 end表示他想从景点 start 前往景点 end。由于小明希望节省体力他想知道每个观景计划中从起点到终点的最短路径长度。 请你帮助小明计算出每个观景计划的最短路径长度。 【输入描述】 第一行包含两个整数 N, M, 分别表示景点的数量和道路的数量。 接下来的 M 行每行包含三个整数 u, v, w表示景点 u 和景点 v 之间有一条长度为 w 的双向道路。 接下里的一行包含一个整数 Q表示观景计划的数量。 接下来的 Q 行每行包含两个整数 start, end表示一个观景计划的起点和终点。 【输出描述】 对于每个观景计划输出一行表示从起点到终点的最短路径长度。如果两个景点之间不存在路径则输出 -1。 【输入示例】 7 3 1 2 4 2 5 6 3 6 8 2 1 2 2 3 【输出示例】 4 -1 【提示信息】 从 1 到 2 的路径长度为 42 到 3 之间并没有道路。 1 N, M, Q 1000. 思路 Floyd算法核心思想是动态规划。 例如我们再求节点1 到 节点9 的最短距离用二维数组来表示即grid[1][9]如果最短距离是10 那就是 grid[1][9] 10。 那 节点1 到 节点9 的最短距离 是不是可以由 节点1 到节点5的最短距离 节点5到节点9的最短距离组成呢 即 grid[1][9] grid[1][5] grid[5][9] 节点1 到节点5的最短距离 是不是可以有 节点1 到 节点3的最短距离 节点3 到 节点5 的最短距离组成呢 即 grid[1][5] grid[1][3] grid[3][5] 以此类推节点1 到 节点3的最短距离 可以由更小的区间组成。那么这样我们是不是就找到了子问题推导求出整体最优方案的递归关系呢。 节点1 到 节点9 的最短距离 可以由 节点1 到节点5的最短距离 节点5到节点9的最短距离组成 也可以有 节点1 到节点7的最短距离 节点7 到节点9的最短距离的距离组成。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); // 顶点数int m sc.nextInt(); // 边数// 初始化距离矩阵最大值设置为10005final int INF 10005;int[][] grid new int[n 1][n 1];// 初始化 grid 数组for (int i 1; i n; i) {for (int j 1; j n; j) {if (i ! j) {grid[i][j] INF;}}}// 输入边信息for (int i 0; i m; i) {int p1 sc.nextInt();int p2 sc.nextInt();int val sc.nextInt();grid[p1][p2] val;grid[p2][p1] val; // 双向图}// Floyd-Warshall 算法//注意k要放在最外层for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (grid[i][k] grid[k][j] grid[i][j]) {grid[i][j] grid[i][k] grid[k][j];}}}}// 输出查询结果int z sc.nextInt(); // 查询次数while (z– 0) {int start sc.nextInt();int end sc.nextInt();if (grid[start][end] INF) {System.out.println(-1);} else {System.out.println(grid[start][end]);}}sc.close(); // 关闭Scanner} } dijkstra朴素版 【题目描述】 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。 小明的起点是第一个车站终点是最后一个车站。然而途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素如天气变化等不同这些因素都会影响每条路径的通行时间。 小明希望能选择一条花费时间最少的路线以确保他能够尽快到达目的地。 【输入描述】 第一行包含两个正整数第一个正整数 N 表示一共有 N 个公共汽车站第二个正整数 M 表示有 M 条公路。 接下来为 M 行每行包括三个整数S、E 和 V代表了从 S 车站可以单向直达 E 车站并且需要花费 V 单位的时间。 【输出描述】 输出一个整数代表小明从起点到终点所花费的最小时间。 思路 第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组minDist数组 用来记录 每一个节点距离源点的最小距离。示例中节点编号是从1开始所以为了让大家看的不晕minDist数组下标我也从 1 开始计数下标0 就不使用了这样 下标和节点标号就可以对应上了避免大家搞混 模拟过程 0、初始化 minDist数组数值初始化为int最大值。 这里在强点一下 minDist数组的含义记录所有节点到源点的最短路径那么初始化的时候就应该初始为最大值这样才能在后续出现最短路径的时候及时更新。 源点节点1 到自己的距离为0所以 minDist[1] 0 此时所有节点都没有被访问过所以 visited数组都为0 模拟过程 以下为dijkstra 三部曲 1.1 第一次模拟 1、选源点到哪个节点近且该节点未被访问过 源点距离源点最近距离为0且未被访问。 2、该最近节点被标记访问过 标记源点访问过 3、更新非访问节点到源点的距离即更新minDist数组 如图 更新 minDist数组即源点节点1 到 节点2 和 节点3的距离。 源点到节点2的最短距离为1小于原minDist[2]的数值max更新minDist[2] 1 源点到节点3的最短距离为4小于原minDist[3]的数值max更新minDist[3] 4 1.2 第二次模拟 1、选源点到哪个节点近且该节点未被访问过 未访问过的节点中源点到节点2距离最近选节点2 2、该最近节点被标记访问过 节点2被标记访问过 3、更新非访问节点到源点的距离即更新minDist数组 如图 更新 minDist数组即源点节点1 到 节点6 、 节点3 和 节点4的距离。 以后的过程以此类推 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);// 输入节点数 n 和边数 mint n sc.nextInt();int m sc.nextInt();// 定义一个邻接矩阵初始化为一个很大的数final int INF Integer.MAX_VALUE;int[][] grid new int[n 1][n 1];// 初始化 grid 为 INF表示没有直接路径for (int i 1; i n; i) {for (int j 1; j n; j) {if (i ! j) {grid[i][j] INF;}}}// 输入边的信息for (int i 0; i m; i) {int p1 sc.nextInt();int p2 sc.nextInt();int val sc.nextInt();grid[p1][p2] val;}// 设置起点和终点int start 1;int end n;// 存储从源点到每个节点的最短距离int[] minDist new int[n 1];// 记录顶点是否被访问过boolean[] visited new boolean[n 1];// 初始化最短距离数组起始点到自身的距离为0其他为INFfor (int i 1; i n; i) {minDist[i] INF;}minDist[start] 0;// 遍历所有节点执行Dijkstra算法for (int i 1; i n; i) {int minVal INF;int cur -1;// 选择距离起点最近且未访问过的节点for (int v 1; v n; v) {if (!visited[v] minDist[v] minVal) {minVal minDist[v];cur v;}}// 如果当前节点无法访问则跳出循环即剩下的节点不可达if (cur -1) break;visited[cur] true; // 标记该节点已被访问// 更新非访问节点到源点的最短距离for (int v 1; v n; v) {if (!visited[v] grid[cur][v] ! INF minDist[cur] grid[cur][v] minDist[v]) {minDist[v] minDist[cur] grid[cur][v];}}}// 输出结果如果终点不可达输出 -1if (minDist[end] INF) {System.out.println(-1);} else {System.out.println(minDist[end]);}sc.close(); // 关闭Scanner} }最小生成树之prim 卡码网53.寻宝 题目描述 在世界的某个区域有一些分散的神秘岛屿每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路方便运输。 不同岛屿之间路途距离不同国王希望你可以规划建公路的方案如何可以以最短的总公路距离将 所有岛屿联通起来。 给定一张地图其中包括了所有的岛屿以及它们之间的距离。以最小化公路建设长度确保可以链接到所有岛屿。 输入描述 第一行包含两个整数V 和 EV代表顶点数E代表边数 。顶点编号是从1到V。例如V2一个有两个顶点分别是1和2。 接下来共有 E 行每行三个整数 v1v2 和 valv1 和 v2 为边的起点和终点val代表边的权值。 输出描述 输出联通所有岛屿的最小路径总距离 输入示例 7 11 1 2 1 1 3 1 1 5 2 2 6 1 2 4 2 2 3 2 3 4 1 4 5 1 5 6 2 5 7 1 6 7 1 输出示例 6 思路 第一步选距离生成树最近节点 第二步最近节点加入生成树 第三步更新非生成树节点到生成树的距离即更新minDist数组 minDist数组用来记录 每一个节点距离最小生成树的最近距离。 示例中节点编号是从1开始minDist数组下标也从 1 开始计数。
初始状态 minDist 数组 里的数值初始化为 最大数因为本题 节点距离不会超过 10000所以 初始化最大数为 10001就可以。 现在 还没有最小生成树默认每个节点距离最小生成树是最大的这样后面我们在比较的时候发现更近的距离才能更新到 minDist 数组上。
模拟过程只模拟两轮 第一轮 1、prim三部曲第一步选距离生成树最近节点 选择距离最小生成树最近的节点加入到最小生成树刚开始还没有最小生成树所以随便选一个节点加入就好因为每一个节点一定会在最小生成树里所以随便选一个就好那我们选择节点1 符合遍历数组的习惯第一个遍历的也是节点1 2、prim三部曲第二步最近节点加入生成树 此时 节点1 已经算最小生成树的节点。 3、prim三部曲第三步更新非生成树节点到生成树的距离即更新minDist数组 注意图中我标记了 minDist数组里更新的权值是哪两个节点之间的权值例如 minDist[2] 1 这个 1 是 节点1 与 节点2 之间的连线清楚这一点对最后我们记录 最小生成树的权值总和很重要。 第二轮 1、prim三部曲第一步选距离生成树最近节点 选取一个距离 最小生成树节点1 最近的非生成树里的节点节点235 距离 最小生成树节点1 最近选节点 2其实选 节点3或者节点2都可以距离一样的加入最小生成树。 2、prim三部曲第二步最近节点加入生成树 此时 节点1 和 节点2已经是最小生成树的节点。 3、prim三部曲第三步更新非生成树节点到生成树的距离即更新minDist数组 接下来我们要更新节点距离最小生成树的距离如图
import java.util.;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int v scanner.nextInt();int e scanner.nextInt();// 初始化邻接矩阵所有值初始化为一个大值表示无穷大int[][] grid new int[v 1][v 1];for (int i 1; i v; i) {Arrays.fill(grid[i], 10001);}// 读取边的信息并填充邻接矩阵for (int i 0; i e; i) {int x scanner.nextInt();int y scanner.nextInt();int k scanner.nextInt();grid[x][y] k;grid[y][x] k;}// 所有节点到最小生成树的最小距离int[] minDist new int[v 1];Arrays.fill(minDist, 10001);// 记录节点是否在树里boolean[] isInTree new boolean[v 1];// Prim算法主循环 只需要循环v-1次建立v-1条边for (int i 1; i v; i) {int cur -1;// 用于记录距离生成树最近的节点int minVal Integer.MAX_VALUE; // 记录最短距离// 选择距离生成树最近的节点for (int j 1; j v; j) {// 如果这个点不在生成树里面且它的距离小于当前最小值if (!isInTree[j] minDist[j] minVal) {minVal minDist[j];cur j;}}// 将最近的节点加入生成树isInTree[cur] true;// 更新非生成树节点到生成树的距离for (int j 1; j v; j) {//当前cur节点比较if (!isInTree[j] grid[cur][j] minDist[j]) {minDist[j] grid[cur][j];}}}// 统计结果int result 0;for (int i 2; i v; i) {result minDist[i];// 从2开始跳过起始节点}System.out.println(result);scanner.close();} } kruskal算法 题目同上题找最小生成树。 思路 prim 算法是维护节点的集合而 Kruskal 是维护边的集合。边的权值排序因为要优先选最小的边加入到生成树里遍历排序后的边 如果边首尾的两个节点在同一个集合说明如果连上这条边图中会出现环如果边首尾的两个节点不在同一个集合加入到最小生成树并把两个节点加入同一个集合
模拟 排序后的边顺序为(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6) 表示节点1 与 节点2 之间的边。权值相同的边先后顺序无所谓。 开始从头遍历排序后的边。 选边(1,2)节点1 和 节点2 不在同一个集合所以生成树可以添加边(1,2)并将 节点1节点2 放在同一个集合。 选边(4,5)节点4 和 节点 5 不在同一个集合生成树可以添加边(4,5) 并将节点4节点5 放到同一个集合。
在上面的讲解中看图的话 大家知道如何判断 两个节点 是否在同一个集合是否有绿色的线连在一起以及如何把两个节点加入集合就在图中把两个节点连上 但在代码中如果将两个节点加入同一个集合又如何判断两个节点是否在同一个集合呢 用并查集
import java.util.*;class Edge {int l, r, val;Edge(int l, int r, int val) {this.l l;this.r r;this.val val;} } public class Main {private static int n 10001;private static int[] father new int[n];// 并查集初始化public static void init() {for (int i 0; i n; i) {father[i] i;}}// 并查集的查找操作public static int find(int u) {if (u father[u]) return u;return father[u] find(father[u]);}public static void join(int u, int v) {u find(u);v find(v);if (u v) return;father[v] u;}public static void main(String[] args) {Scanner scanner new Scanner(System.in);int v scanner.nextInt();int e scanner.nextInt();ListEdge edges new ArrayList();int result_val 0;for (int i 0; i e; i) {int v1 scanner.nextInt();int v2 scanner.nextInt();int val scanner.nextInt();edges.add(new Edge(v1, v2, val));}//对边进行排序edges.sort(Comparator.comparingInt(edge - edge.val));// 并查集初始化init();// 从头开始遍历边for (Edge edge : edges) {int x find(edge.l);int y find(edge.r);if (x ! y) {result_val edge.val;join(x, y);}}System.out.println(result_val);scanner.close();} }