DA:dfsbfs

キューを用いた幅優先探索

##### キュー操作のための関数群 #####
def isEmpty():
    if head == tail:
        print('キューは空です！')
        return True
    return False

def push(x):
    global tail
    if tail == len(queue):
        print('これ以上要素を追加できません！')
        return
    queue[tail] = x
    tail += 1

def pop():
    global head
    if isEmpty():
        return
    head += 1
    return queue[head-1]

def show():
    if isEmpty():
        return
    if head < tail:
        print(queue[head:tail])

##### テストコード #####
V = [[] for i in range(7)]
V[0] = [1, 2]
V[1] = [3, 4]
V[2] = [5, 6]

# キュー（訪問先リスト）の初期化
queue = [0 for i in range(100)]
head = 0
tail = 0

# 訪問済リストvisitedの初期化
visited = []

# 最初の訪問先は0
push(0)

while not isEmpty():
    a = pop()
    visited.append(a)
    for i in V[a]:
        if i in visited:
            continue
        if i in queue[head:tail]:
            continue
        push(i)

print(visited)

スタックを用いた深さ優先探索

##### スタック操作のための関数群 #####
def isEmpty():
    if cur == 0:
        print('スタックは空です！')
        return True
    return False

def push(x):
    global cur
    if cur == len(stack):
        print('これ以上要素を追加できません！')
        return
    stack[cur] = x
    cur += 1

def pop():
    global cur
    if isEmpty():
        return
    cur -= 1
    return stack[cur]

def show():
    print(stack[:cur])

##### テストコード #####
V = [[] for i in range(7)]
V[0] = [1, 2]
V[1] = [3, 4]
V[2] = [5, 6]

# スタック（訪問先リスト）の初期化
stack = [0 for i in range(10)]
cur = 0

# 訪問済リストvisitedの初期化
visited = []

# 最初の訪問先は0
push(0)

while not isEmpty():
    a = pop()
    visited.append(a)
    for i in reversed(V[a]):
        push(i)

print(visited)

再帰関数を用いた深さ優先探索

行きがけ順

def dfs(a):
    if a in visited:
        return

    visited.append(a)

    for i in V[a]:
        dfs(i)

##### テストコード #####
V = [[] for i in range(7)]
V[0] = [1, 2]
V[1] = [3, 4]
V[2] = [5, 6]

# スタック（訪問先リスト）の初期化
stack = [0 for i in range(10)]
cur = 0

# 訪問済リストvisitedの初期化
visited = []

# 最初の訪問先は0
dfs(0)
print(visited)

帰りがけ順

def dfs(a):
    if a in visited:
        return

    for i in V[a]:
        dfs(i)

    visited.append(a)