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)

二部グラフ判定

スタックを用いた深さ優先探索で二部グラフ判定を行うプログラムです．スタックの操作関数（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_whiteとvisited_blackを初期化
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 C[i] == color:
            flag = False            # 「二部グラフではない」と判定される条件は？
        if i in visited:
            continue
        if i in stack:
            continue
        push(i)
        C[i] = color_neighbour

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