向 Graph 添加新边并检查总重量是否减少

Question

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

给定一个具有 N 个节点和 N-1 个加权双向边的图，算法必须响应如果新边 'q' 允许减少图的整体权重，则为 YES，否则为 NO。

边'q'满足这个条件如果有边'e'使得可以将 'e' 替换为 'q'，保持图形连接并降低其整体权重。

我用邻接表实现了图：

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);
}
}

边缘class:

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;
}
...

和图表 class:

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

Given a Graph with N nodes and N-1 weighted bidirectional edges,

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

the algorithm must respond YES if a new edge 'q' allows to reduce the overall weight of the graph, NO otherwise.

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

The edge 'q' satisfies this condition if there is an edge 'e' such that it is possible to replace 'e' with 'q' leaving the graph connected and decreasing its overall weight.

只有从s到t（或t到s)其权重大于新边q的权重。如果有多个这样的边，可以替换其中任何一个。

向 Graph 添加新边并检查总重量是否减少

Add new edge to Graph and check if total weight is reduced

java

algorithm

graph

graph-algorithm