CODEWITHSUNDEEP
pythongraphbreadth-first-search
James
James

Reputation: 319

optimizing breadth first search in python

I have written a depth first search that returns the depth the target node was found at or a -1 if no path was found. the algorithm works but I need to speed it up. Here is the function

def depth(dic, head, target):
    if(head==target):
        return
    depth=1
    que = deque()
    que.append('|') #used to mark end of each breadth so i can count depth correctly
    used = list()
    add = True

    while(que): #while the que isn't empty
        for x in dic[head]: #check current level
            if x==target:
                print(depth),
                return;
        for x in dic[head]: #add this level to the que and used list
            for y in used:
                if y==x:
                    add=False
                    break
            if add == True:
                que.append(x)
                used.append(x)
            add=True
        que.append('|') #add our delimiter
        while(que): #grab the next item from the que and inc depth count
            temp = que.popleft()
            if temp=='|': #bump depth counter since we found end of a level
                depth+=1
            else:
                head=temp #bump to next node to check
                break

    print('-1'), #reached the end, node not found

the dic that is being passed in is declared

dic = defaultdict(list)

so that each value is a list of integers and i'm using the | so I know when to bump the depth counter. I realize that I'm getting bogged down in the middle where I'm checking all nodes at the current level and adding them to the que and used list but I am at a loss how to speed that up.

EDIT:

for anyone that has a similar issue here is the algorithm that I ended up with, the way it steps through the search is a little odd because i'm returning the shallowest depth at which a value can be found and if not all connections at the same depth were checked at the same time we could end up finding nodes at the next depth (like an off by one error)

def depthOfNodeBFS(dic, head, target):
    if(head==target):
        return
    depth=0
    que = []
    que.append(head)
    used = set()
    nex = list()

    while(que): #while the que isn't empty
        depth+=1 #bump the depth counter
        for x in que: #check the next level of all nodes at current depth
            if target in dic[x]: #if the target is found were done
                print(depth),
                return;
            else:               #other wise track what we've checked
                nex.append(x)
                used.add(x)
        while(nex):       #remove checked from que and add children to que
            que.pop(0)
            que.extend(dic[nex.pop()]-used)
    print('-1'),

Upvotes: 1

Views: 944

Answers (1)

saulspatz
saulspatz

Reputation: 5271

This looks more like breadth-first search than depth-first search to me, but you shouldn't have nested while loops. The usual algorithm for a breadth-first search is something like:

add the root to the queue
while the queue is not empty:
  dequeue the first element elt
  if elt is the solution, return it
  otherwise, add each child of elt to the queue

If you want to report the depth, I'd suggest adding tuples (node, depth) to the queue:

add (root, 0) to the queue
while the queue is not empty:
  elt, depth = queue.popleft()
  if elt is the solution, return (elt, depth)
  otherwise, for each child of elt:
     add (child, depth+1) to the queue

Upvotes: 2

Related Questions