ग्राफ एल्गोरिदम

ग्राफ्स गणितीय संरचनाएँ हैं जो वस्तुओं के बीच युग्मित संबंधों को मॉडल करने के लिए उपयोग की जाती हैं। इस संदर्भ में, एक ग्राफ़ ऐसे वर्टिस (जिसे नोड्स या पॉइंट्स भी कहते हैं) से बना होता है, जो किनारों (जिसे लिंक्स या लाइन्स भी कहते हैं) द्वारा जुड़ा होता है। ग्राफ एल्गोरिदम गणितीय प्रक्रियाएं हैं जो ग्राफ्स से संबंधित समस्याओं को हल करने के लिए डिज़ाइन की गई हैं।

ग्राफ एल्गोरिदम का महत्व

कंप्यूटर विज्ञान, जीवविज्ञान, और सामाजिक विज्ञान सहित कई क्षेत्रों में ग्राफ्स मौलिक रूप से महत्वपूर्ण हैं। वे समस्याओं जैसे नेटवर्क फ्लो, सबसे छोटे पथ ढूंढना, स्पैनिंग वृक्ष बनाना, और भी बहुत कुछ हल करने में मदद करते हैं। चलिए कुछ बुनियादी और उन्नत ग्राफ एल्गोरिदम का अन्वेषण करते हैं।

मूल परिभाषाएँ

एल्गोरिदम में जाने से पहले, ग्राफ्स से संबंधित कुछ बुनियादी शर्तों को समझना आवश्यक है।

• वर्टेक्स (या नोड): ग्राफ में वह बिंदु जहाँ किनारे मिलते हैं।
• एज (या लिंक): दो वर्टिस के बीच का संबंध।
• ऐडजेंसी: दो वर्टिस सीधे तौर पर एक एज द्वारा जुड़े होते हैं तो वे पड़ोसी होते हैं।
• पथ: एज की श्रृंखला जो वर्टिस की श्रृंखला को जोड़ती है।
• साइकिल: एक पथ जो एक ही वर्टेक्स पर शुरू और समाप्त होता है।
• कनेक्टेड ग्राफ: एक ग्राफ जिसमें हर जोड़ी के वर्टिस के बीच एक पथ होता है।

ग्राफ के प्रकार

• डायरेक्टेड ग्राफ (डाइग्राफ): एक ग्राफ जिसमें एज की दिशाएँ होती हैं। प्रत्येक एज वर्टिस की एक क्रमबद्ध जोड़ी होती है।
• अनडायरेक्टेड ग्राफ: एक ग्राफ जिसमें एज की कोई दिशा नहीं होती। प्रत्येक एज वर्टिस की एक असंक्रमित जोड़ी होती है।
• वेटेड ग्राफ: एक ग्राफ जिसमें प्रत्येक एज से जुड़ी एक संख्यात्मक मान (वेट) होता है।
• अनवेटेड ग्राफ: एक ग्राफ जिसमें एज का कोई वेट नहीं होता।
• कंप्लीट ग्राफ: एक ग्राफ जिसमें हर जोड़ी वर्टिस के बीच बिल्कुल एक एज होता है।

ग्राफ का निरूपण

ग्राफ्स को दो मुख्य तरीकों से प्रस्तुत किया जा सकता है:

ऐडजेंसी मैट्रिक्स

ऐडजेंसी मैट्रिक्स एक 2D सरणी है जहाँ प्रत्येक तत्व इंगित करता है कि वर्टिस की जोड़ी के बीच एक एज है या नहीं।

a = [
    [0, 1, 0, 0],
    [1, 0, 1, 1],
    [0, 1, 0, 1],
    [0, 1, 1, 0]
]

यह मैट्रिक्स एक ग्राफ को दर्शाता है जिसमें 4 वर्टिस हैं और जोड़ी (0,1), (1,2), (1,3) और (2,3) के बीच एज हैं।

ऐडजेंसी सूची

ऐडजेंसी सूची ग्राफ को वर्टिस की एक सूची के रूप में प्रस्तुत करती है, जहाँ प्रत्येक वर्टेक्स की अपनी सूची होती है जो उसके पड़ोसी वर्टिस हैं।

{
    0: [1],
    1: [0, 2, 3],
    2: [1, 3],
    3: [1, 2]
}

इस सूची में, वर्टेक्स 0 वर्टेक्स 1 से जुड़ा हुआ है, वर्टेक्स 1 वर्टेक्स 0, 2, 3 से जुड़ा है, और इसी प्रकार।

ग्राफ पारगमन एल्गोरिदम

ग्राफ पारगमन का अर्थ एक ग्राफ के प्रत्येक वर्टेक्स की यात्रा करने की प्रक्रिया है। ग्राफ को पारगमन करने के दो मुख्य तरीके हैं:

ब्रेड्थ-फर्स्ट सर्च (BFS)

BFS वह विधि है जो वर्तमान गहराई पर स्थित पड़ोसी नोड्स का पता लगाकर ग्राफ के माध्यम से दोहराता है, फिर अगले गहराई स्तर पर स्थित नोड्स की ओर बढ़ता है।

def bfs(graph, start):
    visited = set()
    queue = [start]

    while queue:
        vertex = queue.pop(0)

        if vertex not in visited:
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)

    return visited

उपरोक्त कोड में, ग्राफ को वर्टेक्स start से शुरू करके पार किया जाता है। BFS विधि एक कतार का उपयोग अगले वर्टेक्स पॉइंट्स को यात्रा करने के लिए करती है।

BFS का कार्य उदाहरण

उपरोक्त SVG एक साधारण ग्राफ दिखाता है जिसमें वर्टेक्स 0 से 3 तक संख्या दी गई हैं। वर्टेक्स 0 से शुरू होने पर, BFS इस क्रम में नोड्स का दौरा करेगा: 0, 1, 3, 2।

डेप्थ-फर्स्ट सर्च (DFS)

DFS एक पारगमन विधि है जिसमें गहराई को प्राथमिकता दी जाती है, और कोई शाखा के लंबवत एक तक संभव बनाने से पहले बैकट्रैक होता है।

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    for next in graph[start]:
        if next not in visited:
            dfs(graph, next, visited)

    return visited

DFS कोड में, विधि रिकर्सिव रूप से कॉल की जाती है और फ़ंक्शन कॉल्स के माध्यम से एक स्टैक पथ का ट्रैक रखने के लिए उपयोग किया जाता है।

DFS का कार्य उदाहरण

उसी ग्राफ के लिए, DFS इस क्रम में नोड्स का दौरा करेगा: 0, 1, 2, 3।

सबसे छोटा पथ एल्गोरिदम

ग्राफ एल्गोरिदम का उद्देश्य अक्सर नोड्स के बीच का सबसे छोटा पथ खोजने का होता है। यहाँ दो प्रसिद्ध सबसे छोटे पथ एल्गोरिदम हैं:

डिज्कस्ट्रा का एल्गोरिदम

डिज्कस्ट्रा का एल्गोरिदम एक वेटेड ग्राफ में प्रारंभिक वर्टेक्स से सभी अन्य वर्टिस के लिए सबसे छोटा पथ खोजता है।

import heapq

def dijkstra(graph, start):
    queue = []
    heapq.heappush(queue, (0, start))
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

यह एल्गोरिदम कतार का उपयोग करता है जिससे सबसे छोटे सामूहिक वज़न वाले एज को पहले पाया जा सके। यह प्राथमिकता कतार (मिन-हीप) का उपयोग करता है ताकि न्यूनतम दूरी वाले एज को प्रभावी ढंग से प्राप्त किया जा सके।

बेल्मन-फोर्ड एल्गोरिदम

बेल्मन-फोर्ड एल्गोरिदम एक ग्राफ में एकल स्रोत वर्टेक्स से सभी अन्य वर्टिस के लिए सबसे छोटा पथ गणना करता है। यह ग्राफ्स को नकारात्मक वज़न के साथ संभाल सकता है।

def bellman_ford(graph, start):
    distance = {i: float('inf') for i in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                raise ValueError("The graph contains a negative weight cycle")

    return distance

डिज्कस्ट्रा के एल्गोरिदम के विपरीत, बेल्मन-फोर्ड नकारात्मक वज़न वाली किनारों वाले ग्राफ्स पर भी काम करता है। यह बार-बार प्रत्येक एज की जाँच करता है ताकि यह सुनिश्चित हो सके कि इष्टतम पथ मिल गए हैं।

मिनिमम स्पैनिंग ट्री (MST) एल्गोरिदम

एक कनेक्टेड, अनडायरेक्ट ग्राफ का मिनिमम स्पैनिंग ट्री एक एज का उपसमुच्चाय होता है जो बिना किसी साइकिल के सभी वर्टिस को जोड़ता है और कम से कम संभव कुल एज वज़न के साथ।

क्रूसकल का एल्गोरिदम

क्रूसकल का एल्गोरिदम सबसे छोटे वाले एज से शुरू करके क्रमशः एजों को जोड़ता है, और केवल उन्हीं एज को जोड़ता है जो साइकिल नहीं बनाते हैं।

def kruskal(graph):
    parent = {}
    
    def find(n):
        while parent[n] != n:
            n = parent[n]
        return n

    def union(n1, n2):
        root1 = find(n1)
        root2 = find(n2)
        parent[root2] = root1

    graph.sort(key=lambda x: x[2])
    for n1, n2, _ in graph:
        parent[n1] = n1
        parent[n2] = n2

    mst = []
    for n1, n2, weight in graph:
        if find(n1) != find(n2):
            union(n1, n2)
            mst.append((n1, n2, weight))
    return mst

यह एल्गोरिदम सभी एजों को वज़न के आधार पर पहले से क्रमित करके शुरू करता है। यह जुड़े घटकों का ट्रैक रखने और यह सुनिश्चित करने के लिए कि साइकिल का निर्माण ना हो, यूनियन-फाइंड डेटा संरचना का उपयोग करता है।

प्रिम का एल्गोरिदम

प्रिम का एल्गोरिदम एक मनमानी वर्टेक्स से शुरू करके और पहले से चयनित वर्टिस से गैर-चयनित वर्टिस तक न्यूनतम-वज़न वाले एज को क्रमशः जोड़ते हुए एमएसटी का निर्माण करता है।

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_edges = [(0, start, None)]

    while min_edges:
        weight, vertex, frm = heapq.heappop(min_edges)
        if vertex in visited:
            continue

        visited.add(vertex)
        if frm is not None:
            mst.append((frm, vertex, weight))

        for next_vertex, next_weight in graph[vertex].items():
            if next_vertex not in visited:
                heapq.heappush(min_edges, (next_weight, next_vertex, vertex))
    return mst

प्रिम का एल्गोरिदम एक प्राथमिकता कतार का उपयोग करता है ताकि हमेशा वर्तमान फ्रिंज में सबसे कम लागत वाले नोड का विस्तार किया जा सके।

निष्कर्ष

ग्राफ एल्गोरिदम नोड्स और एज के नेटवर्क से संबंधित व्यापक समस्याओं का समाधान प्रदान करते हैं। चाहे वह सबसे छोटा पथ खोजने का हो, इष्टतम कनेक्शन हो या नोड्स का पारगमन करना हो, ये एल्गोरिदम जटिल समस्याओं को कुशलतापूर्वक हल करने में महत्वपूर्ण भूमिका निभाते हैं। बुनियादी परिभाषाएँ, निरूपण और प्रमुख एल्गोरिदम जैसे BFS, DFS, डिज्कस्ट्रा, बेल्मन-फोर्ड, क्रूसकल, और प्रिम को समझना वास्तविक जीवन के अनुप्रयोगों में ग्राफ एल्गोरिदम का लाभ उठाने के लिए महत्वपूर्ण है।

टिप्पणियाँ