Java实现加权图？

Question

我已经编写了代码，但不知道如何访问图形的权重，或者如何在主方法中打印其边缘，请查看我的代码。请帮忙，实际上我正在尝试实现 Dijkstra ，但我不知道这是否是在图表中包含重量的正确方法。请帮忙尝试解决过去三天的问题。

public class Gr {

public class Node{ 
    public int vertex;
    public  int weight ;

    public int getVertex() {return vertex;}
    public int getWeight() {return weight;}
    public Node(int v , int w){
        vertex=v;
        weight=w;
    }

}
private int numVertices=1 ;
private  int numEdges=0 ;
private Map<Integer,ArrayList<Node>> adjListsMap= new HashMap<>();


public int getNumVertices(){
    return  numVertices;
}

public int addVertex(){
    int v = getNumVertices();
    ArrayList<Node> neighbors = new ArrayList<>();
    adjListsMap.put(v,neighbors);
    numVertices++ ;
    return (numVertices-1);
}

//adding edge
public void addEdge(int u , int v,int w ){
    numEdges++ ;
    if(v<numVertices&&u<numVertices){
        (adjListsMap.get(u)).add( new Node(u,w));
        (adjListsMap.get(v)).add(new Node(u,w));

    }
    else {
        throw new IndexOutOfBoundsException();
    }
}

//getting neighbours

public List<Node> getNeighbors(int v ){
    return new ArrayList<>(adjListsMap.get(v));
}



public static void main(String[] args){
    Gr g = new Gr();


        for(int j=1;j<=3;j++)
            g.addVertex();
        for(int k =1;k<=2;k++)
        {   int u= in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            g.addEdge(u,v,w);
        }


    }

}

Answer 1

第一条注释:通常，Node 是顶点，Edge 是边。您所采用的名称可能会引起很多困惑。

答案:如果您将图表示为邻接列表，那么最好使用Node 和Edge。如果是这种情况，Node 有一个label 和一个Edge 列表。 Edge 具有对目标 Node 的某种引用(在我的示例中，是对 Node 对象的引用)和一个 权重 。

代码示例:

Node.java

public class Node {
  private String label;
  private List<Edge> edges;
}

Edge.java

public class Edge {
  private Node destination;
  private double weight;
}

使用示例

public class Main {
    public static void main(String[] args) {
        // creating the graph A --1.0--> B
        Node n = new Node();
        n.setLabel("A");
        Node b = new Node();
        b.setLabel("B");
        Edge e = new Edge();
        e.setDestination(b);
        e.setWeight(1.0);
        n.addEdge(e);

        // returns the destination Node of the first Edge
        a.getEdges().get(0).getDestination(); 
        // returns the weight of the first Edge
        a.getEdges().get(0).getWeight(); 
    }
}