as per your example
preorder inorder
tree1: ab ba
tree2: ab ab
both are not isomorphic.
its easy to extend preorder/DFS to
replace two calls to children with for loop considering the graph is N-array
tree.
Thank you,
Sid.
On Wed, Sep 14, 2011 at 5:50 PM, bugaboo <bharath.sri...@gmail.com> wrote:
> @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 <siddharam....@gmail.com> 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 <bharath.sri...@gmail.com>
> 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 <bagana.bharatku...@gmail.com>
> > > 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 <nishaant...@gmail.com>
> > > 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 <
> > > siddharam....@gmail.com
> > > > > > 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 <sundi...@gmail.com>
> 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 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.
> >
> > > > >> --
> > > > >> 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.
> >
> > > > > --
> > > > > 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 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.
> >
> > > > --
> >
> > > > **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*
> > > > <bagana.bharatku...@gmail.com>
> >
> > > --
> > > 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.
>
> --
> 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.
>
>
--
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.
