java - 我可以用什么方式在 Java 中表示加权的有向图？

Question

我需要一种方法，它可以通过对邻接进行操作来遍历图形，返回路径的总权重。我不确定如何在“public double getPathWeight(List path)”方法中增加权重。另外，我可能觉得我的 public void addEdge 方法可能包含一些错误，所以如果我也能得到一些关于该方法的指示，它会帮助我极大地完成我的图表。我的图形是根据通用 VertexType 参数编写的。我正在对邻接表数据结构进行操作。

import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.Map;
import java.util.Set;
import java.util.List;

public class Graph<VertexType> {
private Map<VertexType, TreeMap<VertexType, Double>> adjacency;

public Graph()
{
    adjacency = new java.util.HashMap<>();
}

public void addEdge(VertexType v1, VertexType v2, double weight)
{
    Set <VertexType> set = new HashSet<VertexType>(); 

    if(adjacency.get(v1)!=null)
    {
        set = (Set<VertexType>) adjacency.get(v1); 
        set.add(v2); 
        adjacency.put(v1,(TreeMap<VertexType, Double>) set); 
    }
    else //adds edge if adjacency is null
    {
        set.add(v2); 
        adjacency.put(v1,(TreeMap<VertexType, Double>) set); 
    }
}


public Set<VertexType> getVertices()
{
    return adjacency.keySet();
}

public void dumpGraph()
{
    for (Map.Entry<VertexType,TreeMap<VertexType,Double>> entry :
             adjacency.entrySet())
    {
        System.out.println(entry.getKey() + " -> " + 
entry.getValue());
    }
}


public double getPathWeight(List<VertexType> path) throws 
GraphPathException
{

       //need help with this method

    }

}

Answer 1

为简单起见，我希望您思考一些事情:

• 为什么要介绍 Set在你的addEdge方法？没有它你能完成添加边缘的任务吗？

• 如何计算路径的权重？考虑简单地迭代 getPathWeight 的参数中给出的节点/顶点。并在您的 adjacency 中查找.

我认为这很简单，您只需要知道如何获得 2 个给定顶点之间的边的权重(但首先您需要从 adjacency 中检查该边是否确实存在，或者 path 给出的列表不正确，在这种情况下可能会抛出异常)。

实际代码看起来像这样，但我建议您先自己思考并尝试编写代码，然后再进一步阅读。 :)(我想如果你能决定图表的数据结构——即 Map<VertexType, Map<VertexType, Double>> ，我觉得它已经足够好了，那么你可以轻松地自己用正确的代码填充 getPathWeight 方法)

你可以拥有这种简单的 addEdge实现:

public void addEdge(VertexType v1, VertexType v2, double weight) {
    adjacency.computeIfAbsent(v1, v -> new HashMap<>()).put(v2,weight);
}

getPathWeight 的简单实现:

public double getPathWeight(List<VertexType> path) throws GraphPathException {
    VertexType previousVertex = path.get(0);

    double resultWeight = 0.0;
    for (int i = 1; i < path.size(); i++) {
        VertexType currentVertex = path.get(i);
        Map<VertexType, Double> adjacencyForPreviousVertex = adjacency.get(previousVertex);
        if (adjacencyForPreviousVertex == null) {
            throw new GraphPathException("Vertex " + previousVertex + " don't exist in graph");
        }
        Double currentEdgeWeight = adjacencyForPreviousVertex.get(currentVertex);
        if (currentEdgeWeight == null) {
            throw new GraphPathException(currentVertex + "Vertex don't exist as an adjacent Vertex of " + previousVertex);
        }
        resultWeight += currentEdgeWeight;
        previousVertex = currentVertex;
    }
    return resultWeight;
}