I'm interested to see problems where tree implementation causes a
performance problem. Example?
Choice of graph data structures is very problem-dependent. An
adjacency matrix will probably be fastest and simplest for dense
graphs. For sparse ones there are many, many answers.
An efficient way to do n-ary trees (which are usually sparse graphs)
in C:
typedef struct node_s {
// Use a fixed size array of NODE* if you know
// the maximum number of children in advance.
// Here we assume this isn't true.
struct node_s **children;
int n_children;
...
} NODE;
NODE *make_node(int max_children)
{
// Allocate nodes in a single array if you know the max
// number in advance. Here we assume this isn't true.
NODE *node = safe_malloc(sizeof *node);
node->children = safe_malloc(max_children * sizeof *node->children);
node-n_children = 0;
return node;
}
void add_child(NODE *parent, NODE *child)
{
parent->children[parent->n_children++] = child;
}
void walk
On May 29, 6:17 am, prakash y <[email protected]> wrote:
> How to implement complex data structures like trees (with unknown no.of
> subtrees) and graphs efficiently in C/Java?
> I have implemented binary trees in Java as it always contains two nodes.
> But I don't know about graphs.
> I am not able to solve these problems in coding contests because of this.
> Can anyone please suggest me?
>
> Thanks in advance.
> ~Prakash.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
