java 使用地图绘制图形

Using a Map for a Graph

提问by Ethan

Hi I'm going about implementing a Graph data structure for a course (the graph isn't part of the requirement, I've chosen to use it to approach the problem) and my first thought was to implement it using an adjacency list, because that requires less memory, and I don't expect to have that many edges in my graph.

嗨，我要为一门课程实现图形数据结构（图形不是要求的一部分，我选择使用它来解决问题），我的第一个想法是使用邻接列表来实现它，因为这需要更少的内存，而且我不希望我的图中有那么多边。

But then it occurred to me. I can implement an adjacency list Graph data structure using a Map (HashMapto be specific). Instead of the list of vertices I'll have a Map of vertices, which then hold a short list of edges to vertices.

但后来我想到了。我可以使用 Map （HashMap具体来说）实现邻接表 Graph 数据结构。而不是顶点列表，我将有一个顶点映射，然后保存一个短的顶点边列表。

This seems to be the way to go for me. But I was wondering if anyone can see any drawbacks that a student such as I might have missed in using a HashMapfor this? (unfortunately I recall being very tired whilst we were going over HashMaps...so my knowledge of them is less than all the other data structures I know of.) So I want to be sure.

这似乎是我要走的路。但是我想知道是否有人可以看到像我这样的学生在使用 a 时可能会遗漏的任何缺点HashMap？（不幸的是，我记得在我们复习HashMap的时候很累……所以我对它们的了解比我知道的所有其他数据结构都要少。）所以我想确定一下。

By the way I'm using Java.

顺便说一下，我正在使用 Java。

回答by arshajii

The two primary ways of representing a graph are:

表示图形的两种主要方式是：

• with the adjacency list (as you mentioned)
• with the adjacency matrix

• 与邻接列表（如你所提到的）
• 与邻接矩阵

Since you will not have too many edges (i.e. the adjacency matrix representing your graph would be sparse), I think your decision to use the list instead of the matrix is a good one since, as you said, it will indeed take up less space since no space is wasted to represent the absent edges. Furthermore, the Mapapproach seems to be logical, as you can map each Nodeof your graph to the list of Nodes to which it is connected. Another alternative would be to have each Nodeobject contain, as a data field, the list of nodes to which it is connected. I think either of these approaches could work well. I've summed it up below.

由于您不会有太多边（即表示您的图形的邻接矩阵将是稀疏的），我认为您决定使用列表而不是矩阵是一个很好的决定，因为正如您所说，它确实会占用更少的空间因为没有空间被浪费来表示缺失的边缘。此外，该Map方法似乎是合乎逻辑的，因为您可以将每个Node图形映射Node到它所连接的s列表。另一种选择是让每个Node对象包含它所连接的节点列表作为数据字段。我认为这两种方法中的任何一种都可以很好地工作。我总结如下。

First approach(maintain the map):

第一种方法（维护地图）：

Map<Node, Node[]> graph = new HashMap<Node, Node[]>();

Second approach(data built into Nodeclass):

第二种方法（数据内置到Node类中）：

public class Node {
    private Node[] adjacentNodes;
    public Node(Node[] nodes) { adjacentNodes = nodes; }
    public Node[] adjacentNodes() { return adjacentNodes; }
}

回答by adelbertc

Graphs are traditionally represented either via an adjacency list or an adjacency matrix (there are other ways that are optimized for certain graph formats, such as if the node id's are labeled sequentially and/or you know the number of nodes/edges ahead of time, but I won't get into that).

图传统上通过邻接列表或邻接矩阵表示（还有其他方法针对某些图格式进行了优化，例如如果节点 id 是按顺序标记的和/或您提前知道节点/边的数量，但我不会涉及）。

Picking between an adjacency list and an adjacency matrix depends on your needs. Clearly, an adjacency matrix will take up more space than an adjacency list (matrix will always take (# of nodes)^2 whereas a list will take (# of nodes + # of edges), but if your graph is "small" then it doesn't really make a difference.

在邻接列表和邻接矩阵之间进行选择取决于您的需要。显然，邻接矩阵将比邻接列表占用更多的空间（矩阵将始终采用（节点数）^ 2 而列表将采用（节点数 + 边数），但如果您的图是“小”那么这并没有什么区别。

Another concern is how many edges you have (is your graph sparse or dense)? You can find the density of your graph by taking the # of edges you have and dividing it by:

另一个问题是你有多少条边（你的图是稀疏还是密集）？您可以通过获取您拥有的边数并将其除以来找到图形的密度：

n(n-1) / 2

n(n-1) / 2

Where "n" is the number of nodes of the graph. The above equation finds the total # of possible edges in an "n" node UNDIRECTED graph. If the graph is directed, remove the " / 2".

其中“n”是图的节点数。上面的等式在“n”节点 UNDIRECTED 图中找到可能的边总数。如果图形是有向的，请删除“/2”。

Something else to think of is if efficient edge membership is important. An adjacency list can detect edge membership easily (O(1)) since it's just an array lookup - for an adjacency list if the "list" is stored as something other than a HashSetit will be much slower since you will have to look through the entire edgelist. Or maybe you keep the edgelist's sorted and you can just do a binary search, but then edge insertion takes longer. Maybe your graph is very sparse, and adjacency matrix is using too much memory, so you have to use an adjacency list. Lot's of things to think about.

还需要考虑的是，有效的边缘成员资格是否很重要。邻接列表可以轻松检测边缘成员资格（O（1）），因为它只是一个数组查找 - 对于邻接列表，如果“列表”存储为除 a 以外的其他内容，HashSet它会慢得多，因为您将不得不查看整个边缘列表。或者也许您保持边缘列表的排序并且您可以只进行二分搜索，但是边缘插入需要更长的时间。也许你的图很稀疏，邻接矩阵使用了太多内存，所以你必须使用邻接表。很多事情要考虑。

There's a lot more concerns that may relate to your project, I just list a few.

可能与您的项目有关的问题还有很多，我仅列出一些。

In general, assuming your graph isn't very complex or "big" (in the sense of millions of nodes), a HashMapwhere the key is the node ID and the value is a Setor some other collection of node ID's indicating neighbors of the key node is fine, I've done this for 400,000+ node graphs on an 8gb machine. A HashMapbased implementation will probably be easiest to implement.

一般来说，假设你的图不是很复杂或“大”（在数百万个节点的意义上），aHashMap其中键是节点 ID，值是一个Set或其他一些节点 ID 的集合，指示键的邻居节点很好，我已经在 8gb 机器上为 400,000 多个节点图做了这个。一个HashMap基于实现可能会是最容易实现的。