^ A list representation .... consider a graph with 1 million nodes..and at a time only 2 nodes will be connected...Compare the difference in the two representations... Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Tue, May 29, 2012 at 10:00 PM, Ashish Goel <[email protected]> wrote: > 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. > -- 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.
