Gene: why do you say that adjacency list is not a good solution for sparse matrix? what other alternates are you looking at?
Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, May 29, 2012 at 9:09 PM, Gene <[email protected]> wrote: > 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. > > -- 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.
