Best data structure for DFS on large graphs

Miheer Dewaskar miheer.dew at gmail.com
Tue Jul 3 13:11:05 CEST 2012


I want to make a combinatorial game solver in python.The algorithm is to
perform Depth First Search (DFS) on the states of the game.
For DFS I,would need to keep a record of the visited states.What is the
best data structure for it,keeping in mind that the number of states could
be large?

I was thinking about using Dictionary or a Binary Search Tree (BST)
,assuming that the states can be made hashable and totally ordered
respectively.
I am not sure,but if there are large number of states Dictionaries wont
help much right?

Anyway, does python have a built-in BST like data-structure ?

Thanks,
Miheer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120703/108e5049/attachment.html>


More information about the Python-list mailing list