网站用户后台是怎么做的,首页网站怎么做的,许昌网站开发,电子商务网站建设规划教案大家好#xff0c;我是晴天学长#xff0c;树和dfs的结合#xff0c;其邻接表的存图方法也很重要。需要的小伙伴可以关注支持一下哦#xff01;后续会继续更新的。#x1f4aa;#x1f4aa;#x1f4aa; 1) .串门 2) .算法思路
串门#xff08;怎么存图很关键#xf…大家好我是晴天学长树和dfs的结合其邻接表的存图方法也很重要。需要的小伙伴可以关注支持一下哦后续会继续更新的。 1) .串门 2) .算法思路
串门怎么存图很关键 用双链表存 1.找到最长的那段路树的最长直径 2.答案总和*2-最长那段路。
1.接受数据 2.建立标记数组存图 3.从1开始找最大路径并更新最大路径的点 4.从最大路径的点开始出发再找最大路径 5.答案 3.算法步骤
1.读取输入的节点数量 n。 2.创建一个布尔数组 vis用于记录节点的访问状态。 3.初始化变量 total 为节点数量 n。 4.将 n 减 1并创建一个链表列表 list用于存储图的边关系。 5.循环 n 次读取边的起点 u、终点 v 和权重 w。 6.将路径和增加 w w。 7.在 list 中的起点 u 处添加边的信息 [v, w]。 8.在 list 中的终点 v 处添加边的信息 [u, w]。 9.调用 dfs 方法进行第一次深度优先搜索参数为起点 1访问状态数组 vis 和初始路径和 0。 10.重置访问状态数组 vis 为初始状态最大路径和 maxsum 为 0。 11.调用 dfs 方法进行第二次深度优先搜索参数为节点编号 nodeindex访问状态数组 vis 和初始路径和 0。 12.计算最终结果输出 totalsum - maxsum。 4. 代码实例
package LanQiaoTest.DFS;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;public class 串门 {static ListListint[] list new ArrayList();static long maxsum 0;static int nodeindex 0;static long totalsum 0;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();boolean[] vis new boolean[n 10];int total n ;n--;//建立链表for (int i 0; i n 10; i) {list.add(new ArrayList());}//接受数据,存图树while (n 0) {int u scanner.nextInt();int v scanner.nextInt();int w scanner.nextInt();//添加路径和totalsum w w;// 两个路径都可以走list.get(u).add(new int[]{v, w});list.get(v).add(new int[]{u, w});n--;}//开始第一次的dfsdfs(1, vis, 0);//第一次结束开始第二次vis new boolean[total 10];maxsum 0;// 开始找第二次dfs(nodeindex, vis, 0);System.out.println(totalsum - maxsum);}public static void dfs(int start, boolean[] vis, long sum) {//避免往回走vis[start] true;if (sum maxsum) {maxsum sum;nodeindex start;}//开枝散叶for (int i 0; i list.get(start).size(); i) {int[] temp list.get(start).get(i);//没有标记,就走下去if (!vis[temp[0]]) {dfs(temp[0], vis, sumtemp[1]);}}//也可以不回溯因为跟随着的是返回结果不会在重复的走下去了回溯也行。vis[start]false;}
} 4.总结
图树的正确遍历。dfs回溯 试题链接
