Tri Wulandari (A11.2014.08437)
M. Rizal Imami (A11.2014.08463)
Projek ini dibuat dengan bahasa Pemrograman Python. Dengan acuan pada peta Dufan sebagai Graf.
Dengan awal = A dan tujuan = H.
Maka koding pada python sebagai berikut :
1. BFS (Breadth First Search)
graph = {'A' : set(['B']),
'B' : set(['A', 'C', 'D']),
'C' : set(['B', 'F', 'G']),
'D' : set(['B', 'F', 'E']),
'E' : set(['D']),
'F' : set(['C', 'D', 'G', 'I']),
'G' : set(['C', 'H', 'I']),
'H' : set(['G', 'I']),
'I' : set(['F', 'G', 'H'])}
def breadth(graph, start, finished):
queue = [(start)]
visited = set()
while queue:
road = queue.pop(0)
state = road[-1]
if state == finished:
return road
elif state not in visited:
for cabang in graph.get(state,[]):
road_baru = list(road)
road_baru.append(cabang)
queue.append(road_baru)
visited.add(state)
isi = len(queue)
if isi == 0:
print ("tidak ditemukan")
2. DFS (Depth First Search)
graph = {'A' : set(['B']),
'B' : set(['A', 'C', 'D']),
'C' : set(['B', 'F', 'G']),
'D' : set(['B', 'F', 'E']),
'E' : set(['D']),
'F' : set(['C', 'D', 'G', 'I']),
'G' : set(['C', 'H', 'I']),
'H' : set(['G', 'I']),
'I' : set(['F', 'G', 'H'])}
def depth(graph, start, finished):
stack = [(start)]
visited = set()
while stack:
panjang_tumpukan = len (stack)-1
road = stack.pop (panjang_tumpukan)
state = road[-1]
if state == finished:
return road
elif state not in visited:
for cabang in graph.get(state, []):
road_baru = list(road)
road_baru.append(cabang)
stack.append(road_baru)
visited.add(state)
isi = len(stack)
if isi == 0:
print("tidak ditemukan")
