实现图-Java [英] Implementing Graph - Java

问题描述

该程序的目标是在不使用任何库的情况下在JAVA中实现图形.这不是家庭作业，只是一些练习.我正在尝试实现单向加权图，以后可以将其作为参数传递给Kruskal或Prim的算法，以实现最小生成树.由于我是数据结构的新手，因此我很难确定如何实现图形.邻接矩阵/列表是我要避免的事情，我可以采用以下方法继续进行吗:

The objective of this program to implement a graph in JAVA without using any libraries. This is not a homework assignment, just some practice. I am trying to implement a unidirected weighted graph which can be later passed in as a parameter to a Kruskal's or a Prim's algorithm to implement Minimum Spanning Tree. Since I am new to datastructures, I am having a hard time to figure how to go about implementing a graph. Adjacency Matrix/List is something I would want to avoid, can I go forward with the following approach:

/**
 * 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;
    }
}

推荐答案

我个人将边缘附加到节点上.我意识到它使边缘的数量增加了一倍(因为在您的情况下它们是双向的)，但是它使遍历节点的速度大大提高，因为您不必遍历边缘即可找到下一步可以去的地方.我知道您提到您对邻接表不感兴趣，但是就性能而言，在大多数情况下，这似乎是一种更好的方法，尽管我确定您有理由.所以无论如何我都会发布代码，以便其他人可以找到它.

Personally I would keep the edges attached to the nodes. I realize it doubles the number of edges (because they are bidirectional in your case) but it makes traversing nodes a lot faster because you don't have to iterate through your edges to find where you can go next. I realize you mentioned you're not interested in adjacency lists but it seems like a better approach in most cases in terms of performance, although I'm sure you have your reasons. So I'm posting the code anyway, just so it's there for others.

(没有获取/设置目的是为了使代码简洁)

(no get/set on purpose to keep the code succinct)

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

这篇关于实现图-Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！