@siddharam: Performing inorder and pre/postorder will still have false positives.
Consider 2 trees one with root node "a" with node "b" as left child, another tree with root node "a" with node "b" as its right child. Anyway, for binary trees, I am aware of a recursive solution to find out similarity or isomorphism. Not sure how this extends for a graph. Always thought a DFS and/or BFS should suffice but apparently not. On Sep 14, 1:43 am, siddharam suresh <[email protected]> wrote: > bharath.sriram, > perform inorder traversal and peorder/postorder traversal on both tree then > compare both the result of two tree. > Thank you, > Sid. > > > > > > > > On Wed, Sep 14, 2011 at 10:22 AM, bugaboo <[email protected]> wrote: > > This brings up another interesting question. How do you find out if 2 > > graphs are identical? (By identical, I mean exact similarity and NOT > > isomorphism). Clearly, checking to see if both the DFS traversal and > > BFS traversal match seem to have false positives as Bharathkumar > > mentioned. > > > On Sep 13, 12:50 am, bharatkumar bagana <[email protected]> > > wrote: > > > @nishaanth: > > > ex: > > > 1 > > > 2 3 > > > 4 > > > 5 > > > bfs:12345 > > > dfs:12345 > > > branching factor of this tree is not 1 .......... > > > > On Tue, Sep 13, 2011 at 9:38 AM, nishaanth <[email protected]> > > wrote: > > > > yes branching factor should be 1. it can be not equal to 1 only for the > > > > penultimate node. by penultimate node i mean whose children are the > > leaves > > > > of the tree. rest all cases it should be 1. > > > > > On Tue, Sep 13, 2011 at 9:24 AM, siddharam suresh < > > [email protected] > > > > > wrote: > > > > >> cant say if there more than one leaf element > > > >> still both the algo give same result > > > >> Thank you, > > > >> Sid. > > > > >> On Tue, Sep 13, 2011 at 7:52 AM, Sundi <[email protected]> wrote: > > > > >>> if the dfs and bfs of a graph is same, does it mean that if the > > > >>> branching factor of a graph is one? > > > > >>> a>b>c>d > > > > >>> example: both dfs abd bfs are same here.... > > > > >>> -- > > > >>> 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. > > > > > -- > > > > S.Nishaanth, > > > > Computer Science and engineering, > > > > IIT Madras. > > > > > -- > > > > 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. > > > > -- > > > > **Please do not print this e-mail until urgent requirement. Go Green!! > > > Save Papers <=> Save Trees > > > *BharatKumar Bagana* > > > **http://www.google.com/profiles/bagana.bharatkumar< > >http://www.google.com/profiles/bagana.bharatkumar> > > > * > > > Mobile +91 8056127652* > > > <[email protected]> > > > -- > > 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.
