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]):
        if i in visited:
            continue
        if i in stack:
            continue
        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)

二部グラフ判定

スタックを用いた深さ優先探索で二部グラフ判定を行うプログラムです．スタックの操作関数（push, pop等）も必要ですが，ここでは省略しています．

##### テストコード #####
# グラフ作成
V = [[] for i in range(5)]
V[0] = [1, 3]
V[1] = [0, 2, 4]
V[2] = [1]
V[3] = [0, 4]
V[4] = [1, 3]

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

# C[i] は頂点 i の色．-1:未探索，0:白，1:黒 
C = [-1 for i in range(5)]

# スタック（訪問先リスト）の初期化
stack = [0 for i in range(100)]
cur = 0
color = 0       # 0:白，1:黒 

# 判定用のflag
flag = True

# 探索開始
push(0)
C[0] = color

while not isEmpty():
    a = pop()
    visited.append(a)
    color = C[a]

    color_neighbour = (color + 1) % 2     # 頂点aと隣接するの頂点は，aとは異なる色であるため．
    for i in reversed(V[a]):
        if ###ここを埋めて下さい###:
            flag = False            # 「二部グラフではない」と判定される条件は？
        if i in visited:
            continue
        if i in stack:
            continue
        push(i)
        C[i] = ###ここを埋めて下さい###   #頂点iは何色になるべきか？

if flag:
    print('二部グラフです！')
else:
    print('二部グラフではありません！')

トポロジカルソート

def dfs(a):
    if a in visited:
        return
    ###ここを埋めて下さい###
    #隣接する頂点を訪問するための再起呼び出しのコードと，
    #訪問済の頂点をvisitedに追加するコードが必要です．

V = [[] for i in range(8)]
V[0] = [5]
V[1] = [3, 6]
V[2] = [5, 7]
V[3] = [0, 7]
V[4] = [1, 2, 6]
V[5] = []
V[6] = [7]
V[7] = [0]

visited = []
dfs(4)
print(visited[::-1]) # visitedの中身を逆順で表示