向图形添加新边并检查总权重是否减少

Question

我是图的新手，我正试图在Java解决这个问题：

给定一个具有N个节点和N-1条带权的双向边的图，如果一条新边q允许减少图的总权重，算法必须响应是，否则不允许。

如果存在边“e”，则边“q”满足这个条件，使得可以用“q”替换“e”，从而使图连通并减小其总权重。

我用邻接列表实现了图：

public class Vertex {
private final int element;
private final Set<Edge> edges; // Collection of edges to neighbors

public Vertex(int element) {
    this.element = element;
    edges = new HashSet<>();
}

public int getElement() {
    return element;
}

public boolean addEdge(Edge edge) {
    return edges.add(edge);
}

public List<Edge> getEdges() {
    return new ArrayList<>(edges);
}
}

边缘类：

public class Edge {
   private Vertex to;
private int weight;

public Edge(Vertex to, int weight) {
    super();
    this.to = to;
    this.weight = weight;
}

public Vertex getTo() {
    return to;
}
...

和图形类：

public class Graph {
   private final Set<Vertex> vertices; // Collection of all vertices

   public Graph() {
       vertices = new HashSet<>();
   }

   public List<Vertex> getVertices() {
       return new ArrayList<>(vertices);
   }

   public boolean addVertex(Vertex vertex) {
       return vertices.add(vertex);
   }
}

有没有一个算法我可以用来解决问题？

Answer 1

给定一个具有N个结点和N-1条加权双向边的图,

那么该图就是一棵树。（假设图是连通的。）树的一个有用的性质是，对于树中的任意两个节点s和t，它们之间存在单个唯一（简单）路径。

如果新边“q”允许减少图的整体权重，算法必须响应“是”，否则不允许。

在树中的两个节点（例如，s和t）之间添加一条新边会创建一个循环。移除这个新循环中的任何边将创建一个同样是树的新（连通）图。

如果存在边“e”，则边“q”满足这个条件，使得可以用“q”替换“e”，从而使图连通并减小其总权重。

只有在从s到t（或t到s）的路径中存在一条或多条边，其权重大于新边Q的权重时，才能满足该条件。如果存在多个这样的边缘，则可以替换其中的任何一个。