Re: Best data structure for DFS on large graphs

Discussion in 'Python' started by Stefan Behnel, Jul 3, 2012.

  1. Miheer Dewaskar, 03.07.2012 13:11:
    > 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?


    Dicts are fast for lookup, not for searching.


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


    It has lists and bisect:

    http://docs.python.org/library/bisect.html

    Stefan
     
    Stefan Behnel, Jul 3, 2012
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wolodja Wentland
    Replies:
    8
    Views:
    1,241
    anand jeyahar
    Dec 11, 2009
  2. Tiago de Paula Peixoto
    Replies:
    0
    Views:
    421
    Tiago de Paula Peixoto
    Dec 12, 2009
  3. Miheer Dewaskar
    Replies:
    0
    Views:
    176
    Miheer Dewaskar
    Jul 3, 2012
  4. Tim Chase
    Replies:
    0
    Views:
    180
    Tim Chase
    Jul 3, 2012
  5. Miheer Dewaskar
    Replies:
    0
    Views:
    225
    Miheer Dewaskar
    Jul 3, 2012
Loading...

Share This Page