4
\$\begingroup\$

I'm using ArrayList<Nodes> to store adjacent nodes, and ArrayList<Integer> to store the corresponding weights of the vertices. Is this efficient if I only use it for small inputs? Is it efficient for large inputs as well?

class Node {
    public ArrayList<Node> adjacent = new ArrayList<Node>();
    public ArrayList<Integer> weights = new ArrayList<Integer>();
    boolean visited;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It is one of the popular data structure for storing graphs - AdjencyList. So far it seems good. \$\endgroup\$ – Mangat Rai Modi Jan 16 '18 at 14:45
  • \$\begingroup\$ I had seen some classes where they created classes for vertices as well, I found it too complicated, I guess this should work and no more classes should be needed \$\endgroup\$ – Bugs Buggy Jan 16 '18 at 15:05
  • 1
    \$\begingroup\$ do you mean edges? Because here Node is a vertex and weights I believe are the weight for the edges going to adjacent nodes. Depending on problem you might need to create a class for edges too, for e.g. if edges have some extra data your problem like cost, distance and other metrics. In that case, your weights will become an array list of the Edge class \$\endgroup\$ – Mangat Rai Modi Jan 16 '18 at 15:20
  • \$\begingroup\$ Yes I meant edges. Sorry for the confusion, can I not save that data in the node, like suppose in Node A adjacent matrix element x is Node B. Edge connecting A to B has some weight, we can store that as element x in another array. This would be applicable to unidirectional Graph, in case of bidirectional, a lot of data would be redundant but again for small number of input it will just work. \$\endgroup\$ – Bugs Buggy Jan 16 '18 at 15:58
  • 1
    \$\begingroup\$ If the core of the question is whether the data structure is OK: Yes. As others have pointed out, this is an adjacency list. Depending on the desired genericity, one would/could/should try to add an abstraction layer to hide this implementation detail from the user, but this is not trivial (and may not be necessary in your case). If the question is about "low level code recommendations": It should be private final List<Node> adjacent (+ the necessary accessor methods) \$\endgroup\$ – Marco13 Jan 20 '18 at 21:09
2
\$\begingroup\$

Is this efficient if I only use it for small inputs?

For small inputs, anything is efficient. For big data, having each Node as such a large object would be inefficient. I depends what kind of actions you would do over the graph. If you access it sequentially, there can be also a linked implementation like:

class LinkedNode {
    public Node firstChild;   
    public Node nextSibling;   
    boolean visited;
}

Here's an alternative, without objects but with arrays instead:

int[] edgeWeights;
int[] edgeIndicies;

At the begin, edgeIndicies will have values [0,1,2,...n]. Sorting the weights, you move the indicies instead, so if the indicies are the following: [5,7,9,...] you know edgeWeights[5] is the smallest, edgeWeights[7] is the second smallest, ...etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.