1

我正在实施一些算法来自学图表以及如何使用它们。你会推荐什么是在 Java 中做到这一点的最佳方法？

我只是想问你是否可以为有向图和加权有向图的简短非常简单的类定义提供简短的帮助？

我查看了网络，但我不想要它的实现，只是类的简短定义......你认为最好的数据结构是什么？相邻列表？

对于无向图，我将其定义如下：

public interface Graph { 
  Collection vertices();  // returns a collection of all the 
        //   Vertex objects in the graph 
  Collection edges();  // returns a collection of all the 
     //   Edge objects in the graph 
  Collection incidentEdges(Vertex v); // returns a collection of  
       //   Edges incident to v 
  boolean isAdjacent(Vertex v, Vertex w); // return true if v and     
}                 //   w are adjacent 

public class Vertex { 
  public boolean visited;  // initially false for all vertices 
} 

public class Edge { 
  Vertex v1, v2;     // undirected edge 
  Vertex opposite(Vertex v); // given a vertex return the one 
}          // at the other end of this edge
4

2 回答 2

1

这是一个简单的实现（这对于许多基本用例来说应该足够好了）：

public class Graph { 
  public List<Node> nodes = new ArrayList<Node>();
}                

public class Node{
  public List<Node> neighbors = new ArrayList<Node>();
 //here you can add stuff like "public boolean visited;", if your algorithm requires it
}

（这只是一个例子——有很多方法可以实现图结构）。

于 2013-02-17T14:22:35.890 回答
0

要使用的数据结构取决于您的代码的目的......列表通常做得很好，但如果图形高度连接（大多数节点连接到大多数节点），那么列表很麻烦，并且通常首选某种矩阵。

例如，要使用矩阵，请保留节点向量，然后使用整数的二维向量来引用节点。

另外，为了制作一个轻量级的类，你不必为节点声明一个类：你可以提供添加节点和边的函数，你可以用整数来识别这些元素。

如果您计划对它们进行子类化（例如，在执行显示图形的 GUI 时可能很有用），则拥有 Node 或 Edge 类可能是合适的，但如果您需要某些算法的图形，则使用整数识别节点/边会更快，并且更简单。

于 2013-02-17T14:41:46.153 回答