Java：如何表示图形？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1737627/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java: how to represent graphs?
提问by Nick Heiner
I'm implementing some algorithms to teach myself about graphs and how to work with them. What would you recommend is the best way to do that in Java? I was thinking something like this:
我正在实施一些算法来自学图形以及如何使用它们。你会推荐什么是在 Java 中做到这一点的最佳方法？我在想这样的事情：
public class Vertex {
private ArrayList<Vertex> outnodes; //Adjacency list. if I wanted to support edge weight, this would be a hash map.
//methods to manipulate outnodes
}
public class Graph {
private ArrayList<Vertex> nodes;
//algorithms on graphs
}
But I basically just made this up. Is there a better way?
但我基本上只是编造了这个。有没有更好的办法？
Also, I want it to be able to support variations on vanilla graphs like digraphs, weighted edges, multigraphs, etc.
此外，我希望它能够支持普通图的变化，如有向图、加权边、多重图等。
回答by Roland Ewald
If you need weighted edges and multigraphs, you might want to add another class Edge.
如果您需要加权边和多重图，您可能需要添加另一个类Edge。
I would also recommend using genericsto allow specifying which sub-class of Vertex and Edge are currently used. For example:
我还建议使用泛型来指定当前使用的 Vertex 和 Edge 的子类。例如：
public class Graph<V extends Vertex> {
List<V> vertices;
...
}
When it comes to implementing graph algorithms, you could also define interfacesfor your graph classes on which the algorithms can operate, so that you can play around with different implementations of the actual graph representation. For example, simple graphs that are well-connected might be better implemented by an adjacency matrix, sparser graphs might be represented by adjacency lists- it all depends...
在实现图算法时，您还可以为算法可以在其上运行的图类定义接口，以便您可以尝试实际图表示的不同实现。例如，连接良好的简单图可能通过邻接矩阵更好地实现，稀疏图可能由邻接列表表示- 这一切都取决于......
BTW Building such structures efficiently can be quite challenging, so maybe you could give us some more details on what kind of job you would want to use them for? For more complex tasks I would suggest you have a look at the various Java graph libraries, to get some inspiration.
顺便说一句，有效地构建这样的结构可能非常具有挑战性，所以也许您可以提供更多关于您希望将它们用于什么样的工作的详细信息？对于更复杂的任务，我建议您查看各种 Java 图形库，以获得一些灵感。
回答by Jeff Storey
Take a look at the http://jung.sourceforge.net/doc/index.htmlgraph library. You can still practice implementing your own algorithms (maybe breadth-first or depth-first search to start), but you don't need to worry about creating the graph structure.
查看http://jung.sourceforge.net/doc/index.html图形库。您仍然可以练习实现自己的算法（也许可以从广度优先或深度优先搜索开始），但您无需担心创建图形结构。
回答by sinuhepop
Time ago I had the same problem and did my own implementation. What I suggest you is to implement another class: Edge. Then, a Vertex will have a List of Edge.
前段时间我遇到了同样的问题，并做了我自己的实现。我建议你实现另一个类：Edge。然后，一个顶点将有一个边列表。
public class Edge {
private Node a, b;
private directionEnum direction; // AB, BA or both
private int weight;
...
}
It worked for me. But maybe is so simple. There is this library that maybe can help you if you look into its code: http://jgrapht.sourceforge.net/
它对我有用。但也许就是这么简单。如果你查看它的代码，这个库可能可以帮助你：http: //jgrapht.sourceforge.net/
回答by duffymo
I'd recommend graphvizhighly when you get to the point where you want to render your graphs.
当您到达要渲染图形的地步时，我强烈推荐graphviz。
And its companions: take a look at Laszlo Szathmary's GraphViz class, along with notugly.xls.
以及它的同伴：看看Laszlo Szathmary 的 GraphViz 类，以及notugly.xls。
回答by GeoffDS
Even at the time of this question, over 3 years ago, Sage(which is completely free) existed and was pretty good at graph theory. But, in 2012 it is about the best graph theory tool there is. Thus, Sage already has a huge amount of graph theory material built in, including other free and open source stuff that is out there. So, simply messing around with various things to learn more is easy as no programming is required.
甚至在 3 年前提出这个问题的时候，Sage（完全免费）就已经存在并且非常擅长图论。但是，在 2012 年，它是最好的图论工具。因此，Sage 已经内置了大量图论材料，包括其他免费和开源的东西。因此，无需编程，只需搞砸各种事情即可轻松学习更多知识。
And, if you are interested in the programming part as well, first Sage is open source so you can see any code that already exists. And, second, you can re-program any function you want if you really want to practice, or you can be the first to program something that does not already exist. In the latter case, you can even submit that new functionality and make Sage better for all other users.
而且，如果您也对编程部分感兴趣，首先 Sage 是开源的，因此您可以看到任何已经存在的代码。其次，如果您真的想练习，您可以重新编写您想要的任何功能，或者您可以成为第一个编写尚不存在的东西的人。在后一种情况下，您甚至可以提交新功能并使 Sage 更好地供所有其他用户使用。
At this time, this answer may not be that useful to the OP (since it has been 3 years), but hopefully it is useful to any one else who sees this question in the future.
目前，这个答案对 OP 来说可能不是那么有用（因为它已经 3 年了），但希望它对将来看到这个问题的任何其他人都有用。
回答by andrewkshim
Why not keep things simple and use an adjacency matrixor an adjacency list?
回答by rai.skumar
回答by Arselan Sunni Ashaari Bessaad
class Graph<E> {
private List<Vertex<E>> vertices;
private static class Vertex<E> {
E elem;
List<Vertex<E>> neighbors;
}
}
回答by Mustafa
class Vertex {
private String name;
private int score; // for path algos
private boolean visited; // for path algos
List<Edge> connections;
}
class Edge {
private String vertex1Name; // same as Vertex.name
private String vertex2Name;
private int length;
}
class Graph {
private List<Edge> edges;
}
回答by bhspencer
Each node is named uniquely and knows who it is connected to. The List of connections allows for a Node to be connected to an arbitrary number of other nodes.
每个节点都被唯一命名并且知道它连接到谁。连接列表允许一个节点连接到任意数量的其他节点。
public class Node {
public String name;
public List<Edge> connections;
}
Each connection is directed, has a start and an end, and is weighted.
每个连接都是有方向的，有起点和终点，并被加权。
public class Edge {
public Node start;
public Node end;
public double weight;
}
A graph is just your collection of nodes. Instead of List<Node>consider Map<String, Node>for fast lookup by name.
图只是您的节点集合。而不是List<Node>考虑Map<String, Node>按名称进行快速查找。
public class Graph {
List<Node> nodes;
}
