Java：如何表示图形？ [英] Java: how to represent graphs?

问题描述

我正在实施一些算法来教我自己关于图形以及如何使用它们。你会推荐什么是在Java中做到这一点的最佳方式？我在想这样的事情：

  public class Vertex {
 
 private ArrayList< Vertex> outnodes; //邻接列表。如果我想支持边缘权重，这将是一个哈希映射。 
 
 //操作outnodes的方法
} 
 
 public class图{
 private ArrayList< Vertex>节点; 
 //图上的算法
} 
  

但我基本上只是做了这个。还有更好的方法吗？

另外，我希望它能够支持变体，比如有向图，加权边，多图等等。

解决方案

每个节点都是唯一命名的，并且知道它与谁连接。连接列表允许节点连接到任意数量的其他节点。

  public class Node {
公共字符串名称; 
 public List< Edge>连接; 
} 
  

每个连接都是定向的，有一个开始和结束，并且是加权的。

  public class Edge {
 public Node start; 
公共节点结束; 
公共双重重量; 
} 
  

图形只是您的节点集合。而不是 List< Node> 考虑 Map< String，Node> 来快速查找名称。 b
$ b

  public class Graph {
 List< Node>节点; 
} 
  

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:

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.

解决方案

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.

public class Graph {
    List<Node> nodes;
}

这篇关于Java：如何表示图形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！