1

我想实现一些图形算法，这就是我创建一种图形框架的原因。到目前为止，我使用以下类非常容易地实现了有向图；

class Vertex {
    String id;
    String name;
}


class Edge {
    String id;
    Vertex source;
    Vertex destination;
    int weight;
}

class Graph {
     List<Vertex> vertexes;
     List<Edge> edges; }

在测试它时，我创建：

Edge edge = new Edge(id, source_node, destination_node, weight)

这在有向图中非常好。但是在无向图中；我必须这样写；假设我们有 2 个节点，它们是 A，B，它们之间的权重是 10。所以由于无向图的结构，我必须放置两条边；

Edge e1 = new Edge(id1, A, B, 10)
Edge e2 = new Edge(id2, B, A, 10)

这种类型的边缘创建既低效又详尽。

因此，我如何修改我的代码，以便我不必在两个节点之间放置两条边以用于无向图。将无向图类型也集成到我的代码中的最佳方法是什么？

谢谢你的时间。

4

5 回答 5

3

我最近遇到了一个有趣的 Java API，称为Tinkerpop的Blueprints，您可以使用它，或者查看一些关于如何实现自己的图形框架的想法。

我正在开发一个使用 JSON 的图形框架。这是由于图形的可变性。图论中的算法倾向于将数据添加到其他算法使用的图中。因此，试图具体描述图形本身就存在缺陷。

于 2013-03-15T00:36:15.950 回答
1

我将不同意现有的答案...

通常，在代码中表示图形时，出于效率原因，您不希望将边存储为一个大列表，甚​​至根本不希望存储为对象。您通常需要使用邻接矩阵（用于相对密集的图）或邻接列表（用于相对稀疏的图）。这使您可以轻松查找顶点的邻居，这主要是您在图形算法中使用的。因此，在实现中，您通常只需要一个索引数组或Vertex对象集或列表。

在无向图中，您将添加边(i,j)以及(j,i)数据结构。在有向图中，您只需添加其中一个。

于 2013-02-11T18:21:29.233 回答
1

自然的解决方案是使边缘的方向成为一个属性。创建一个枚举：

public enum EdgeType {
     Undirected,
     From1to2,
     From2to1,
     Cyclic
}

然后为您的 Edge 类添加一个属性：

public EdgeType enumEdgeType;

在进行遍历和其他操作时，您可以使用 switch 语句来处理 4 种不同的情况。我的经验是这种方法是最简单和最有效的。

于 2013-02-11T17:25:46.813 回答
0

I will have to disagree with the answer concerning blueprint. There is a lot hype around this library and except the nice feature of graph implementation abstraction, there is absolutely nothing implemented in the graph algorithm (furnace) package, rendering the complicated stack totally useless.

When I mean nothing is implemented, that is really nothing (take a look here), and the repo hasn't been updated since a while, so you can consider it dead. If you want to use a

My 2 cents, use a seasoned graph framework : Jgrapht. I use it for several research projects, there are 20 standards (and some non trivials) graph algorithms implemented. So you don't need to reinvent the wheel. It also supports a heavy load of graph types.

Avoid hype, go for working solutions.

于 2013-03-30T12:53:23.333 回答
0

根据您要实现的图形算法，您将需要不同的图形表示，因此您必须能够使用其中的几种。大多数算法使用邻域列表，而在您的代码中使用边缘列表。

你真的不应该担心边缘的创建。大多数情况下，与实际算法相比，它可以忽略不计。现在，根据您尝试执行的操作，您可能只需要其中一个边缘，但大多数时候，拥有两个边缘是非常好的和理智的。

于 2013-02-11T12:43:51.230 回答