1

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.

Improve this question
3
  • 1
    I'd start by actually thinking about what data structure you want to end up with and writing at least a dummy implementation. There are several possible representations for graphs, and they can be implemented differently, so it's not clear which one you want to build. (For instance, your original int[][] is already a perfectly valid graph data structure.) Commented Apr 7, 2013 at 22:00
  • Are you trying to read an edge list? Into what structure? Commented Apr 7, 2013 at 22:00
  • I just edited my question. Should be more clear on what I am trying to do. Commented Apr 7, 2013 at 22:05

3 Answers 3

Reset to default
3

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2
  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();
Improve this answer

6 Comments

I worked a lot to bring this answer so don't forget to accept if this helps. Thanks!
Is there a way that I could possibly find a path between the nodes like what I explained in my edit? I really appreciate it.
The path algorithm you're looking for sound like a different question to me. I would open another post if I were you.
If I'm getting the question right it sounds pretty similar to the travelling salesperson problem: en.wikipedia.org/wiki/Travelling_salesman_problem The difference here is that it is not a circular path and it can have repeartitions.
It is really a simplified version of TSP.
|
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]
Improve this answer

2 Comments

Shouldn't array[1][3] have a [1] same with array[3][1]? and array[3][0] be 0? I'm just asking.
How would I go about going through the path and count each move? Sorry. Probably a stupid question. I just don't understand how I would implement in code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.