Python - Algoritma Grafik

Grafik adalah struktur data yang sangat berguna dalam menyelesaikan banyak tantangan matematika yang penting. Misalnya topologi jaringan komputer atau menganalisis struktur molekul senyawa kimia. Mereka juga digunakan dalam lalu lintas kota atau perencanaan rute dan bahkan dalam bahasa manusia dan tata bahasanya. Semua aplikasi ini memiliki tantangan yang sama dalam melintasi grafik menggunakan tepinya dan memastikan bahwa semua node grafik dikunjungi. Ada dua metode umum yang ditetapkan untuk melakukan traversal ini yang dijelaskan di bawah ini.

Traversal Pertama Kedalaman:

Juga disebut pencarian pertama kedalaman (DFS), algoritma ini melintasi grafik dalam gerakan lingkungan kedalaman dan menggunakan tumpukan untuk mengingat untuk mendapatkan simpul berikutnya untuk memulai pencarian, ketika jalan buntu terjadi dalam iterasi apa pun. Kami mengimplementasikan DFS untuk grafik dengan python menggunakan tipe data yang ditetapkan karena mereka menyediakan fungsionalitas yang diperlukan untuk melacak node yang dikunjungi dan yang belum dikunjungi.

class graph:

    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }


dfs(gdict, 'a')

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

a b d e c

Breadth First Traversal

Juga disebut pencarian pertama yang melebar (BFS), algoritma ini melintasi gerakan lingkungan luas grafik dan menggunakan antrian untuk mengingat untuk mendapatkan simpul berikutnya untuk memulai pencarian, ketika jalan buntu terjadi dalam iterasi apa pun. Silakan kunjungi tautan ini di situs web kami untuk memahami detail langkah-langkah BFS untuk grafik.

Kami mengimplementasikan BFS untuk grafik dalam python menggunakan struktur data antrian yang dibahas sebelumnya. Saat kami terus mengunjungi node yang belum dikunjungi dan terus menambahkannya ke antrean. Kemudian kita mulai dequeue hanya node yang tersisa tanpa node yang belum dikunjungi. Kami menghentikan program ketika tidak ada node yang berdekatan berikutnya untuk dikunjungi.

import collections
class graph:
    def __init__(self,gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict

def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
        seen, queue = set([startnode]), collections.deque([startnode])
        while queue:
            vertex = queue.popleft()
            marked(vertex)
            for node in graph[vertex]:
                if node not in seen:
                    seen.add(node)
                    queue.append(node)

def marked(n):
    print(n)

# The graph dictionary
gdict = { "a" : set(["b","c"]),
                "b" : set(["a", "d"]),
                "c" : set(["a", "d"]),
                "d" : set(["e"]),
                "e" : set(["a"])
                }

bfs(gdict, "a")

Ketika kode di atas dijalankan, itu menghasilkan hasil sebagai berikut -

a c b d e