Graph Pada Python

Graph Pada Python

graf dalam komputer sains (ilmu komputer) adalah sebuah tipe data abstrak. Graf terdiri dari titik-titik (nodes) yang terhubung dengan sisi/busur (edge/arcs).

Berikut ini contoh graf yang akan kita tulis dalam kode program python:

Graf tersebut merupakan graf berarah yang memiliki enam buah titik dan delapan busur (arcs). Adapun delapan busur tersebut bisa kita nyatakan seperti berikut ini.

A -> B
A -> C
B -> C
B -> D
C -> D
D -> C
E -> F
F -> C

Graf sebenarnya bisa diubah ke dalam bentuk matriks dan ditulis dalam bentuk array dua dimensi ke dalam kode. Namun, karena contoh yang saya temukan menggunakan dictionary, maka graf di atas bisa dituliskan seperti berikut ini.

graf = {'A': ['B', 'C'],
        'B': ['C', 'D'],
        'C': ['D'],
        'D': ['C'],
        'E': ['F'],
        'F': ['C']}

Source code :

from __future__ import print_function

graph = { "a": ["c","d"],
          "b": ["c", "e"],
          "c": ["a", "b", "d", "e"],
          "d": ["c","e"],"e": ["c", "b"],
          "f": []}

def find_path(graph, start, end, path=[]):
                path = path + [start]
                for node in graph[start]:
                    if not node in path:
                        newpath = find_path(graph, node, end, path)
                        if newpath != None:
                            return newpath
                if start == end:
                    return path
                if not start in graph:
                    return None

def all_path(graph, start, end, path=[]):
                path = path + [start]
                if start == end:
                    return [path]
                if not start in graph:
                    return []
                paths = []
                for node in graph[start]:
                    if not node  in path:
                        newpaths = all_path(graph, node, end, path)
                        for newpath in newpaths:
                            paths.append(newpath)
                return paths

def shortest_path(graph, start, end, path=[]):
                path = path + [start]
                if start == end:
                    return path
                if not start in graph:
                    return None
             
                shortest = None
                for node in graph[start]:
                    if node not in path:
                        newpath = shortest_path(graph, node, end, path)
                        if newpath != None:
                            if not shortest or len(newpath) < len(shortest):
                                shortest = newpath
                return shortest

def main_menu():
    print ("=".center(80,"="))
    print("Selamat Datang Di Aplikasi (Graph)".upper().center(80))
    print("By : Moh. Irsad 170411100024".upper().center(80))
    print ("=".center(80,"="))
    stop = False
    while not stop:
        print ("=".center(30,"="))
        print ("Menu Aplikasi Graph")
        print ("=".center(30,"="))
        print ("1. Menemukan Jalur")
        print ("2. Tampilkan Semua Jalur")
        print ("3. Jalur Tercepat")
        print ("=".center(30,"="))
        opsi = int(input("Masukkan pilihan anda : "))
        print ()
     
        if opsi == 1 :
            print ("=".center(30,"="))
            print ("1. Menemukan Jalur")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            print ()
            Kondisi = find_path(graph, awal, akhir)
            if Kondisi == None :
                print ("=".center(40,"="))
                print ("Jalur yang anda inginkan tidak ada!!!")
                print ("=".center(40,"="))
            else :
                print ("=".center(40,"="))
                print("Jalur Ditemukan :",find_path(graph, awal, akhir))
                print ("=".center(40,"="))
             
        elif opsi == 2:
            print ("=".center(30,"="))
            print ("2. Tampilkan Semua Jalur")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            no = 1
            for i in all_path(graph,awal,akhir):
                print ("=".center(40,"="))
                print ("Jalur ke-%d : " %(no),i)
                print ("=".center(40,"="))
                no += 1
             
        elif opsi == 3:
            print ("=".center(30,"="))
            print ("3. Jalur Tercepat")
            print ("=".center(30,"="))
            for i in graph:
                print ("Jalur ",i,":",graph[i])
            print ()
            awal = raw_input("Masukan Jalur Awal : ")
            akhir = raw_input("Masukan Jalur Tujuan Anda : ")
            print ("=".center(40,"="))
            print("Jalur tercepat : ", shortest_path(graph,awal,akhir))
            print ("=".center(40,"="))
         
        else :
            print ("=".center(40,"="))
            print ("Pilihan yang anda masukan tidak ada".center(40))
            print ("=".center(40,"="))
             
        if opsi != 4:       
            opsi2 =raw_input("Apakah anda ingin mencoba opsi lain? (Yes/No) :")
            if opsi2 == 'No':
                stop = True
                print("=".center(80,"="))
                print("Terimakasih telah mencoba aplikasi kami.".upper().center(80))
                print("Moh. Irsad 170411100024".center(80))
                print("=".center(80,"="))

main_menu()

Post,In, dan Preorder BinaryTree (Rekursif dan Non-Rekursif)

Post,In, dan Preorder BinaryTree (Rekursif dan Non-Rekursif)

Ada tiga pola umum yang digunkaan untuk mengunjungi semua node dalam tree. Perbedaan antara 3 pola ini adalah urutan kunjungan terhadap node. Kunjungan ini dinamakan “traversal.”, yaitu preorder, inorder dan postorder. Berikut ini adalah definisinya:

1. Preorder
Dalam suatu preorder traversal, node root dikunjungi pertama, kemudian secara rekursif melakukan preorder traversal dari subtree kiri, diikuti oleh suatu preorder traversal rekursif dari subtree kanan.

2. Inorder
Pada suatu inorder traversal, secara rekursif dilakukan inorder traversal pada subtree kiri, mengunjungi node root dan terakhir melakukan inorder traversal rekursif dari subtree kanan.

3. Postorder
Dalam suatu postorder traversal, dilakukan suatu postorder traversal rekursif dari subtree kiri dan subtree kanan diikuti dengan kunjungan ke node root.

Source code :

from __future__ import print_function

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items==[]

    def push(self,items):
        self.items.append(items)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
 
class Binarytree:
    def __init__(self,root):
        self.key = root
        self.leftChild = None
        self.rightChild = None

    def insertLeft(self,newNode):
        if self.leftChild == None :
            self.leftChild = Binarytree(newNode)

        else :
            t = Binarytree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t

    def insertRight(self,newNode):
        if self.rightChild == None :
            self.rightChild = Binarytree(newNode)

        else :
            t = Binarytree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getrightChild(self):
        return self.rightChild

    def getleftChild(self):
        return self.leftChild

    def getrootVal(self):
        return self.key

    def setrootVal(self,obj):
        self.key = obj

    def size(self):
        count = 0
        selfleft = self
        selfright = self
        while selfleft.getleftChild() != None or selfright.getrightChild() != None :
            count += 1
            if selfleft.getleftChild() != None:
                selfleft = selfleft.getleftChild()
            else :
                selfright = selfright.getrightChild()
        return count

#Post,In,Pre dengan Rekursif
def Inorder(root):
    if root!= None:
        Inorder(root.getleftChild())
        print(root.getrootVal(),end=" ")
        Inorder(root.getrightChild())

def Preorder(root):
    if root!= None:
        print(root.getrootVal(),end=" ")
        Preorder(root.getleftChild())
        Preorder(root.getrightChild())

def Postorder(root):
    if root!= None:
        Postorder(root.getleftChild())
        Postorder(root.getrightChild())
        print(root.getrootVal(),end=" ")

#Post,In,Pre tanpa Rekursif
def pre_order(root):
    s=Stack()
    current = root
    s.push(current)
    while not s.isEmpty():
        current = s.pop()
        print(current.getrootVal(),end =" ")
     
        if current.getrightChild()!=None:
            s.push(current.getrightChild())
         
        if current.getleftChild()!=None:
            s.push(current.getleftChild())

def post_order(root):
    s1=Stack()
    s2=Stack()
    current = root
    s1.push(current)
    while not s1.isEmpty():
        current = s1.pop()
        s2.push(current.getrootVal())
         
        if current.getleftChild()!= None:
            s1.push(current.getleftChild())
     
        if current.getrightChild()!=None:
            s1.push(current.getrightChild())
         
    while not s2.isEmpty():
        print(s2.pop(),end=" ")
 
def in_order(root):
    s=Stack()
    current = root
    done = False
    while not done:
        if current != None:
            s.push(current)
            current = current.getleftChild()
        else:
            if s.size() > 0 :
                current = s.pop()
                print(current.getrootVal(),end=" ")
                current = current.getrightChild()
            else:
                done = True
#Main_program
     
root = Binarytree('P')
root.insertLeft('F')
root.getleftChild().insertLeft('B')
root.getleftChild().insertRight('H')
root.getleftChild().getleftChild().insertLeft('A')
root.getleftChild().getrightChild().insertRight('M')
root.insertRight('S')
root.getrightChild().insertLeft("R")
root.getrightChild().insertRight("W")
print ("=".center(40,"="))
print ("Tugas Praktikum 7\nBy : Moh. Irsad(170411100024)")
print ("=".center(40,"="))
print ("Tree :\n")
print(root.getrootVal(),end = " ")
print(root.getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getrightChild().getrootVal(),end = " ")
print(root.getleftChild().getleftChild().getleftChild().getrootVal(),end = " ")
print(root.getleftChild().getrightChild().getrightChild().getrootVal(),end = " ")
print(root.getrightChild().getrootVal(),end = " ")
print(root.getrightChild().getleftChild().getrootVal(),end = " ")
print(root.getrightChild().getrightChild().getrootVal())
print ("=".center(25,"="))
print ("No. 1".center(25))
print ("=".center(25,"="))
print ("Menggunakan Rekursif\n")
print ("Inorder :\n")
Inorder(root)
print ()
print ("\nPreorder :\n")
Preorder(root)
print ()
print ("\nPostorder :\n")
Postorder(root)
print ()
print ("=".center(25,"="))
print ("No. 2".center(25))
print ("=".center(25,"="))
print ("Tanpa Menggunakan Rekursif\n")
print ("Inorder :\n")
in_order(root)
print ()
print ("\nPreorder :\n")
pre_order(root)
print ()
print ("\nPostorder :\n")
post_order(root)
print ()
print ("=".center(25,"="))