Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #24812 > unrolled thread

Re: Best data structure for DFS on large graphs

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Best data structure for DFS on large graphs Stefan Behnel <stefan_ml@behnel.de> - 2012-07-03 13:23 +0200

#24812 — Re: Best data structure for DFS on large graphs

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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web