Program Pencarian Pohon Akar Menggunakan Breath first Search ( BFS ) Dan Depth First Search ( DFS ) Dengan Sofware Python.
Breath first Search ( BFS )
pohon = {'A':set(['B','C','E']),
'B':set(['A','G','D']),
'C':set(['A','I']),
'D':set(['B','H','I']),
'E':set(['A','F']),
'F':set(['E','H']),
'G':set(['B','H']),
'H':set(['D','F','G','I']),
'I':set(['C','D'])}
def bfs(graf, mulai, tujuan):
queue = [[mulai]]
visited = set()
while queue:
jalur = queue.pop(0)
state = jalur[-1]
if state == tujuan:
return jalur
elif state not in visited:
for cabang in graf.get(state, []):
jalur_baru = list(jalur)
jalur_baru.append(cabang)
queue.append(jalur_baru)
visited.add(state)
isi = len(queue)
if isi == 0:
print("tidak ditemukan")
Depth First Search ( DFS )
pohon = {'A':set(['B','C','E']),
'B':set(['A','G','D']),
'C':set(['A','I']),
'D':set(['B','H','I']),
'E':set(['A','F']),
'F':set(['E','H']),
'G':set(['B','H']),
'H':set(['D','F','G','I']),
'I':set(['C','D'])}
def dfs(graf, mulai, tujuan):
stack = [[mulai]]
visited = set()
while stack:
panjang_tumpukan = len(stack)-1
jalur = stack.pop(panjang_tumpukan)
state = jalur[-1]
if state == tujuan:
return jalur
elif state not in visited:
for cabang in graf.get(state, []):
jalur_baru = list(jalur)
jalur_baru.append(cabang)
stack.append(jalur_baru)
visited.add(state)
isi = len(stack)
if isi == 0:
print("Tidak ditemukan")
