从数组创建链接的数据结构

Question

我是链接数据结构的新手，想知道如何创建一个无向图，当给定2个点从2d数组和点之间没有确定的权重。我到处找了都找不到我要找的东西。

例子:

int[][] points = { { 0, 1 },{ 0, 2 },{ 1, 2 },{ 1, 3 },{ 3, 4 } };

拉长后应该是这样的。

      0
      |
    -------
    |     |
    1-----2
    |
    3-----4 

编辑

我还希望能够找到从0到4的最短路径，并且至少遍历一次每个点，同时计算沿途的每次移动。有一种可能，你可能不得不向后移动。在上面的例子中，从0到4的最短路径是(0-2)(2-1)(1-3)(3-4)，计数为4步。

Answer 1

表示图形有两种基本方法。

邻接矩阵和邻接表。您可以在wikiepdia中阅读邻接矩阵:http://en.wikipedia.org/wiki/Adjacency_matrix

要实现邻接表，您需要为每个节点创建一个列表，并将每个节点所连接的所有节点放入列表中。

这里有更多关于图表示的内容:http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29表示

Answer 2

1. 创建一个类Node，它包含一个相邻节点的列表
2. 遍历points数组中的节点。为您找到的每个节点创建一个Node对象(可能最好在开始时将它们保存在Map中)。
3. 再次迭代并填充每个节点的相邻节点列表。

考虑这个类Node:

public class Node {
    private int id;
    private List<Node> adjacentNodes = new ArrayList<Node>();
    public List<Node> getAdjacentNodes() {
        return adjacentNodes;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
}

这个方法创建了一个所有节点的集合，它们被链接在一起:

 private static Collection<Node> createGraphNodes(int[][] pointsMatrix) {
    Map<Integer, Node> nodes = new HashMap<Integer, Node>();
    for(int[] points: pointsMatrix) {
        for(int point: points) {
            if(nodes.containsKey(Integer.valueOf(point))) {
                continue;
            }
            Node node = new Node();
            node.setId(point);
            nodes.put(point, node);
        }
    }
    for(int[] points: pointsMatrix) {
        int nodeId1 = points[0];
        int nodeId2 = points[1];
        Node node1 = nodes.get(Integer.valueOf(nodeId1));
        Node node2 = nodes.get(Integer.valueOf(nodeId2));
        node1.getAdjacentNodes().add(node2);
        node2.getAdjacentNodes().add(node1);
    }
    return nodes.values();

Answer 3

表示图的最简单方法是使用邻接矩阵，这是一个二维布尔矩阵，其中行和列表示图中的节点，如果它们是连接的，则表示一行和列状态之间的交集。如果连接为0，则为1。

例如你上面的图表将是:

     0    1    2    3    4   
0   [0]  [1]  [1]  [0]  [0] 
1   [1]  [0]  [1]  [1]  [0]  
2   [1]  [1]  [0]  [0]  [0] 
3   [0]  [1]  [0]  [0]  [1]
4   [0]  [0]  [0]  [1]  [0]