CODEWITHSUNDEEP
javalinked-list
mjenkins2010
mjenkins2010

Reputation: 51

Create linked data structures from array

I am new to linked data structures and was wondering how to create an undirected graph when given 2 points from a 2d array and no weight determined between the points. I've searched around and couldn't really find what I was looking for.

Example:

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

Drawn out it should look like this.

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

EDIT

I also want to be able to find the shortest path from 0 to 4 and traversing to each point at least once while counting each move along the way. There is the possibility that you may have to move backwards. In above example, the shortest path from 0 - 4 is (0-2)(2-1)(1-3)(3-4) and counts to be 4 moves.

Upvotes: 1

Views: 162

Answers (3)

Avi
Avi

Reputation: 21760

  1. Create a class Node that contains a list of adjacent nodes
  2. Iterate through your nodes in the points array. Create a Node object for each node you find (probably it would be better to keep them in a Map at the beginning.
  3. Iterate once again and fill the adjacent nodes list for each node.

Consider this class 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;
    }
}

And this method creates a collection of all nodes and they're linked together:

 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();

Upvotes: 2

Dimitris Fousteris
Dimitris Fousteris

Reputation: 1111

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]

Upvotes: 2

orestis
orestis

Reputation: 972

There are two basic ways to represent graphs.

Adjacency matrix and adjacency lists. You can read about the adjacency matrix in wikiepdia: http://en.wikipedia.org/wiki/Adjacency_matrix

To implement adjacency lists you create one list for each node and you put in the list all the nodes that the respective node is connected to.

Here is more on graph representations: http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29#Representations

Upvotes: 3

Related Questions