Kamis, 20 April 2017

Program Pencarian Pohon Akar Menggunakan Breath first Search ( BFS ) Dan Depth First Search ( DFS ) Dengan Sofware Python.



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")
















Pengikut