时间戳

首页 > 解决方案 > 将新边添加到 Graph 并检查总权重是否减少

java - 将新边添加到 Graph 并检查总权重是否减少

问题描述

我是 Graphs 的新手，我正在尝试用 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);
   }
}

有没有可以用来解决问题的算法？

标签： javaalgorithmgraphgraph-algorithm

解决方案

给定一个具有 N 个节点和 N-1 个加权双向边的图，

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

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

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

如果存在边“e”，则边“q”满足此条件，从而可以用“q”替换“e”，从而使图形保持连接并降低其整体权重。

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

推荐阅读