StarWalker

Where my heart will take me

0%

BFS and DFS

Posted on Edited on In Views: Valine:
Algorithms review for coming interviews

Pseudocode

BFS

1
2
3
4
5
6
7
8
9
10
11
12
from collections import deque

def BFS():
    while (q != None):
        u = q.popleft()
        for v in subState[u]:
            if Flag(v) and Optimize(v):
                setFlag(v)
                v.pre = u
                if goalTest(v):
                    outputResult()
                q.append(v)

DFS

1
2
3
4
5
6
7
8
9
10
11
12
def DFS_working(x):
    if goalTest(x):
        outputResult()
    for xi in subState[x]:
        if Flag(xi) and Optimize(xi):
            setSomeAttrs(flag, pre, ...)
            DFS_working(xi)
            delSomeAttrs(flag, pre, ...)

def DFS():
    for x in subState[source]:
        DFS_working(x)

Stack and Queue in Python

Using list as stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

Using list as queue

1
2
3
4
5
6
7
8
9
10
>>> from collections import deque
>>> queue = deque(["Eric", "John", "Michael"])
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.popleft()                 # The first to arrive now leaves
'Eric'
>>> queue.popleft()                 # The second to arrive now leaves
'John'
>>> queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])