GRAPH

-

GRAPH
1.     PENGERTIAN GRAPH
Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai node, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

2.     ISTILAH PADA GRAPH
Terdapat beberapa istilah yang berkaitan dengan graph yaitu :
Ø  Vertex
Vertex yaitu himpunan node / titik pada sebuah graph.
Ø  Edge
Edge yaitu himpunan garis yang menghubungkan tiap node / vertex.
Ø  Adjacent
Adjacent yaitu Adalah dua buah titik dikatakan berdekatan (adjacent) jika dua buah titik tersebut terhubung dengan sebuah sisi.
Ø  Weight
Disebut sebuah graph berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real.
Ø  Path
Path yaitu jalur dengan setiap vertex berbeda.
Ø  Cycle
Adalah Siklus (Cycle) atau Sirkuit (Circuit) yaitu lintasan yang berawal dan berakhir pada simpul yang sama.

3.     JENIS JENIS GRAPH
Ø  Undirected Graph
Graph tak berarah (undirected graph atau non-directed graph) dimana urutan simpul dalam sebuah busur tidak dipentingkan.
Ø  Directed Graph
Graph berarah (directed graph) dimana urutan simpul mempunyai arti.
Ø  Weighted Graph
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot. Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.
4.     CONTOH SOURCE CODE
def main():
    pass

if __name__ == '__main__':
    main()
graph = {'A': ['B', 'C','D'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}

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:
                    return newpath
        if start == end:
            return path
        if not start in graph:
            return None

        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:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath

        return shortest




print(find_path(graph, 'E', 'C'))
print(all_path(graph,'A','D'))
print(shortest_path(graph,'A','D'))
Di post oleh :
1. FITRI ANISA (170411100014)


2. DHEA OKY SYAFITRI (170411100006)



Komentar

Posting Komentar

Postingan populer dari blog ini

Class and Object in Python

-
Class dan Objek Class Merupakan Struktur data yang bisa kita gunakan untuk mendefinisikan objek yang menyimpan data bersama-sama nilai-nilai dan perilaku (behavior). Kelas adalah suatu entitas yang merupakan bentuk program dari suatu abstraksi untuk permasalahan dunia nyata, dan instans dari class merupakan realisasi dari beberapa objek. contoh kelas : binatang, kendaraan, benda dsb. 2. objek merupakan Instance dari class. Jika class secara umum merepresentasikan (template) sebuah object, maka sebuah instance adalah representasi nyata dari class itu sendiri. 3. pada dasarnya ada 2 karakteristik yang utama pada sebuah objek : Objek memiliki attribut sebagai status yang disebut Stat Objek memiliki tingkahlaku yang kemudian disebut Method 4. keyword class diikuti dengan nama class yang kita inginkan. Lebih baik digunakan kata yang diawali huruf kapital. 5. Setiap method harus memiliki parameter self yang artinya method tersebut dim...
Baca selengkapnya

DOUBLE LINKED LIST

-
DOUBLE LINKED LIST 1.       PENGERTIAN DOUBLE LINKED LIST Double Linked List sama seperti  Single Linked List  merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada double linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Double Linked List.  2.       SOURCE CODE class Node:     def __init__(self,initdata):         self.data = initdata         self.next = None         self.previous = None     def getData(self):         return self.data  ...
Baca selengkapnya