Graph

Definisi

Graph adalah sekelompok simpul-simpul (node/vertices) V dan sekelompok sisi (edges) E yang menghubungkan beberapa simpul tersebut sebagai lokasi - lokasi , maka himpunan dari simpul - simpul tersebut adalah himpunan lokasi - lokasi yang ada.
Graph juga di definisikan sebagai himpunan benda - benda yang disebut verteks (node) yang terhubung oleh sisi (edge/arc). Graph juga biasanya digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).

Ilustrasi

Algoritma

def find_path(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return path

    if start not in graph:

        return None

    for node in graph[start]:

        if node not in path:

            newpath = find_path(graph, node, end, path)

            if newpath:

                return newpath

    return None

def find_all_paths(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return [path]

    if start not in graph:

        return []

    paths = []

    for node in graph[start]:

        if node not in path:

            newpaths = find_all_paths(graph, node, end, path)

            for newpath in newpaths:

                paths.append(newpath)

    return paths

def find_shortest_path(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return path

    if start not in graph:

        return None

    shortest = None

    for node in graph[start]:

        if node not in path:

            newpath = find_shortest_path(graph, node, end, path)

            if newpath:

                if not shortest or len(newpath) < len(shortest):

                    shortest = newpath

    return shortest

def find_longest_path(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return path

    if start not in graph:

        return None

    longest = None

    for node in graph[start]:

        if node not in path:

            newpath = find_longest_path(graph, node, end, path)

            if newpath:

                if not longest or len(newpath) > len(longest):

                    longest = newpath

    return longest

Kode Program

graph = {'A': ['B', 'C','D'],

             'B': ['A','E', 'D'], 

             'C': ['A','D','E'], 

             'D': ['A','B','C','E'], 

             'E': ['B','C','D']} 

def find_all_paths(graph, start, end, path=[]):

        path = path + [start]

        if start == end:

            return [path]

        paths = []

        for node in graph[start]:

            if node not in path:

                newpaths = find_all_paths(graph, node, end, path)

                for newpath in newpaths:

                    paths.append(newpath)

        return paths

def find_terpendek(graph,data):

        titik= 1000

        for i in data:

                if (len(i)-1)< titik:

                        titik=(len(i)-1)

        print("Jalur Terpendek : ")

        for z in data:

                if titik == (len(z)-1):

                        print(' '.join(z),'ada',titik,'titik ')

def find_terpanjang(graph,data):

        titik = 0

        for i in data:

                for j in range(len(i)):

                        if titik < j :

                                titik = j

        print("Jalur Terpanjang : ")

        for x in data:

                if titik == (len(x)-1) or titik == len(x):

                        print(' '.join(x),'ada',titik,'titik ')

                        

m=find_all_paths(graph,'A','E')

find_terpendek(graph,m)

find_terpanjang(graph,m)