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 <yprakash....@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.