從數組創建鏈接的數據結構

Question

我是新來的鏈接數據結構，並想知道如何創建一個無向圖，當從2d數組給出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個移動。

Answer 1

1. 創建一個類節點包含
2. 迭代通過在點陣列的節點相鄰節點的列表。爲每個節點創建一個節點對象，你覺得（可能會更好，讓他們在開始時的地圖。
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(); 

Answer 2

有兩種基本方式代表圖形。

鄰接矩陣和鄰接列表。您可以閱讀wikiepdia中的鄰接矩陣：http://en.wikipedia.org/wiki/Adjacency_matrix

要實現鄰接列表，請爲每個節點創建一個列表，然後將列表中的所有節點放入列表中。

這裏是更多的曲線圖表示： http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29#Representations

Answer 3

來表示圖中的最簡單的方法是使用鄰接矩陣，這是在其中行和列表示圖中的節點的二維布爾矩陣，並如果它們連接在一行和一列之間的交叉點。它包含一個，否則連接爲零。

例如您的上圖是：

 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]