实现Graph - Java

Question

这个程序的目标是在不使用任何库的情况下用JAVA实现图形。这不是家庭作业，只是一些练习。我正在尝试实现一个单向加权图，稍后可以将其作为参数传递给Kruskal算法或Prim算法，以实现最小生成树。由于我是数据结构的新手，我很难弄清楚如何去实现一个图。邻接矩阵/列表是我想要避免的东西，我可以继续使用以下方法：

/**
 * Graph.java: This is the main file.
 */ 
public class Graph {

    public static void main(String[] args)
    {
        Node n1 = new Node("A");
        Node n2 = new Node("B");
        Node n3 = new Node("C");
        Node n4 = new Node("D");
        Node n5 = new Node("E");
        Node n6 = new Node("F");

        Edges e1 = new Edges(n1, n2, 5);
        Edges e2 = new Edges(n1, n3, 3);
        Edges e3 = new Edges(n2, n4, 5);
        Edges e4 = new Edges(n2, n5, 2);
        Edges e5 = new Edges(n3, n6, 7);
    }
}


/**
 * Node.java class used to represent vertices
 */
public class Node {
    private String name;
    public Node(String name)
    {
        this.name = name;
    }
}

/**
 * Edges.java class used to represent edges.
 */
public class Edges {
    private int weight;
    private Node sNode;
    private Node dNode;
    public Edges(Node sNode, Node dNode, int weight)
    {
        this.sNode = sNode;
        this.dNode = dNode;
        this.weight = weight;
    }
}

Answer 1

就我个人而言，我会将边附加到节点上。我意识到它使边的数量翻了一番(因为它们在你的例子中是双向的)，但它使得遍历节点的速度更快，因为你不必遍历你的边来寻找下一步可以去的地方。我知道你提到过你对邻接表不感兴趣，但在大多数情况下，这似乎是一种更好的性能方法，尽管我相信你有自己的理由。因此，我无论如何都要发布代码，这样其他人就可以看到它了。

(故意不使用get/set以保持代码简洁)

public class Node {
    private String name;
    private List<Edge> neighbors;

    public Node(String name) {
        this.name = name;
    }

    public void AddUndirectedEdge(Node destination, int weight) {
        neighbors.Add(new Edge(destination, weight));
        destination.neighbors.Add(new Edge(this, weight));
    }

    private static class Edge {
        public Node destination;
        public int weight;

        public Edge(Node destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
    }
}