Materi Graph - Struktur Data

Materi Graph

Graph adalah kumpulan noktah (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 noktah, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge).

Istilah dalam Graph :

• Tepi adalah bagian dasar lain dari grafik, dan menghubungkan dua simpul / Tepi mungkin satu arah atau dua arah. Jika ujung-ujungnya dalam grafik semuanya satu arah, grafiknya adalah graf berarah, atau digraf.
• Simpul adalah bagian paling dasar dari grafik dan juga disebut sebagai simpul.
• Tepi dapat ditimbang untuk menunjukkan bahwa ada biaya untuk berpindah dari satu titik ke titik yang lain
• Jalur dalam grafik adalah urutan simpul yang dihubungkan oleh tepi
• Siklus dalam grafik diarahkan adalah jalur yang dimulai dan berakhir pada titik yang sama.

Macam-macam graph :

• unlabelled graph
• labelled graph
• weighted graph
• Disconected graph
• Connceted graph
• Complete graph
• Simple path : ABC
• Cycle Graph

Graph Traversals

• Menemukan jalur terpendek ke item tertentu dalam grafik
• Menemukan semua item yang item yang diberikan dihubungkan oleh jalur
• Melintasi semua item dalam grafik

­Tugas Praktikum 8

Kelas A,B,E
1. Buat program untuk mencari
- Semua jalur dari A ke E
- Jalur tercepat dan alternatifnya(yang sama cepatnya) dari A ke E
- Semua edge (penghubung antar 2 titik), semisal (a,c), (a,d), (b,c),(b,e) dsb

Dari graph berikut ini

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

Penyelesaiaan Codingan :

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

def find_ListShortestPath(Allpaths,ShortestPath):
    ListShortest = [];
    for path in Allpaths:
        if len(path) == len(ShortPath):
            ListShortest.append(path)
    return ListShortest
    
def displayBlock(Paths):
    for i in range(len(Paths)):
        print('Path',i+1,'=',Paths[i])


def find_AllEdge(graphs):
    ListEdge = []
    for keys in graphs.keys():
        if graphs[keys] != []:
            for value in graphs[keys]:
                temp = keys+' => ' +value
                ListEdge.append(temp)
    return ListEdge
    
    
graphSembarang = {
         'A': ['C','D'],
         'B': ['C','E'],
         'C': ['A','B','D','E'],
         'D': ['C','E'],
         'E': ['C','B'],
         'F': []
         }

#print(find_path(graph, 'E', 'C'))


ListAll_Path = all_path(graphSembarang,'A','E')
print('\nAll Path  : ')
displayBlock(ListAll_Path)

ShortPath = shortest_path(graphSembarang,'A','E')
ListShortestPath = find_ListShortestPath(ListAll_Path,ShortPath)
print('\nShortest Path and Alternative : ')
displayBlock(ListShortestPath)


SemuaEdge = find_AllEdge(graphSembarang)
print('\nAll Edge : ')
displayBlock(SemuaEdge)

Hasil RUN :