图中的最小权重环

给定一个拥有 V 个节点（编号从 0 到 V-1）和 E 条边的 无向、加权 图。这些边由二维数组 INLINECODE997c8aeb 表示，其中每个元素 INLINECODE710923a1 表示节点 INLINECODEc586f74e 和 INLINECODE9ba3efeb 之间有一条权重为 w 的边。此外，所有边的权重均为正整数。我们的任务是 找出该图中权重最小的环。

注意：图中的 环（Cycle） 是指一条起点和终点相同且不重复任何边或顶点（除了起点/终点）的路径。
最小权重环 是指在所有可能的环中，边的权重总和最小 的那个。
示例：

> 输入： V = 5, edges = [[0, 1, 2], [1, 2, 2], [1, 3, 1], [1, 4, 1], [0, 4, 3], [2, 3, 4]]

> !3

> 输出： 6

> 解释：

> !4

> 权重最小的环是 INLINECODEdb55d2e6，其总权重为 INLINECODEb5b5f390(2 + 1 + 3)

尝试练习

目录

• [朴素方法] 找出所有环的权重
• [推荐方法] : 使用 Dijkstra 算法 – O(E * (V + E) log V) 时间复杂度和 O(V+E) 空间复杂度

[朴素方法] 找出所有环的权重

> 我们可以使用深度优先搜索（DFS）来寻找图中的所有环，在探索每个环的过程中，记录其总权重。最后，我们更新并维护在所有这些环中找到的最小权重。

C++


CODEBLOCK_76f5f54d


Java

`

//Driver Code Starts
import java.util.*;

public class Solution {

    // 构建邻接表
    static ArrayList<ArrayList> constructAdj(int V, int[][] edges) {
        ArrayList<ArrayList> adj = new ArrayList();
        for (int i = 0; i < V; i++) adj.add(new ArrayList());

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj.get(u).add(new int[]{v, w});
            adj.get(v).add(new int[]{u, w});
        }
        return adj;
//Driver Code Ends

    }
   
    static int minCycle;
    // 使用DFS探索环并跟踪它们的权重
    static void dfs(int u, int parent,ArrayList<ArrayList> adj,
                    boolean[] visited, ArrayList path,
                    ArrayList weights,int currWeight) {

        visited[u] = true;
        path.add(u);

        for (int[] edge : adj.get(u)) {
            int v = edge[0];