oceanmaster.wang
BAN USERThis is horroable...
- oceanmaster.wang May 27, 2014This is a algorithm question.
- oceanmaster.wang May 26, 2014should be &&
- oceanmaster.wang May 26, 2014The answer is still not complete
tseudo code should be:
nodes= {all nodes}
while( nodes is not empty )
{
randomly pick a node A in nodes.
construct Spanning tree from A and return false if loop is found.
remove all nodes in spanning tree from A.
}
return true
change to :
if(!input.containsKey(parent) || !nodes.containsKey(parent))
continue;
to avoid duplicated checking.
This can be solved as a Spanning Tree. The concept is keeps checking and removing spanning trees from the graph until a loop is found or no nodes left
public bool hasCycle(List<String, String> input)
{
HashSet<String> nodes = new HashSet<String>(input.keySet());
List<String> spanning = new LinkedList<String>();
while(nodes.size()>0)
{
spanning.add(nodes.get(0));
int expanded = 0;
while(expanded < spanning.size())
{
String parent = spanning.get(expanded++);
if(!input.containsKey(parent))
continue;
String son = input.get(parent);
if(spanning.contains(son))
return false;
spanning.add(son);
}
nodes.removeAll(spanning);
spanning.clear();
}
return true;
}
Looking for a better solution.
- oceanmaster.wang May 26, 2014
Are you sure it's "traverse" time?
- oceanmaster.wang May 28, 2014Even for "retrieval" time, of course BST is not the answer since is doesn't have to be balanced.
But a AVL tree has to be a BST, except it's self-balancing.