1

我是链接数据结构的新手，想知道如何在给定二维数组中的 2 个点并且在点之间没有确定权重时创建无向图。我四处寻找，并没有真正找到我要找的东西。

例子：

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 步。

4

3 回答 3

3

有两种基本的方式来表示图。

邻接矩阵和邻接列表。您可以在 wikiepdia 中阅读有关邻接矩阵的信息：http ://en.wikipedia.org/wiki/Adjacency_matrix

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

以下是关于图形表示的更多信息： http ://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29#Representations

于 2013-04-07T22:07:34.417 回答
2
  1. 创建一个包含相邻节点列表的类Node
  2. 遍历点数组中的节点。为您找到的每个节点创建一个 Node 对象（可能最好在开始时将它们保存在 Map 中。
  3. 再次迭代并填充每个节点的相邻节点列表。

考虑这个类节点：

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();
于 2013-04-07T22:01:27.543 回答
2

The simplest way to represent graphs is to use the Adjacency matrix, which is a two-dimensional boolean matrix in which rows and columns represent nodes in the graph, and the intersection between one row and column states if they are connected. It contains one if they are connected zero otherwise.

For example your above graph will be:

     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]
于 2013-04-07T22:09:46.500 回答