नोड्स के बीच रूट: निर्देशित ग्राफ में रास्ता खोज (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.१: निर्देशित ग्राफ में नोड एस से नोड ई तक रास्ता है या नहीं। डीएफएस से बेहतर बीएफएस, जावा में ग्राफनोड पड़ोसी सूची के साथ।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

शहर एक-तरफ़ा सड़कों पर चलते हैं। घर से पार्क तीन मोड़ों में पहुँच सकते हो, पर वापसी का रास्ता न हो अगर हर तीर उल्टी दिशा में हो। निर्देशित ग्राफ वही नक्शा है: किनारों की दिशा होती है। सवाल सीधा है: नोड एस से शुरू करके क्या सिर्फ कानूनी तीरों से नोड ई तक पहुँच सकते हो?

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली ग्राफ पहुँच-योग्यता का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ४ (ट्री और ग्राफ) यहीं खुलता है।

---

१. एक-तरफ़ा सड़क की उपमा

एक छोटा बाज़ार सोचो:

• चौराहे नोड हैं।
• एक-तरफ़ा सड़कें निर्देशित किनारे हैं। ए से बी का तीर मतलब ए → बी चल सकते हो। दूसरा तीर न हो तो बी → ए नहीं।
• तुम चौराहा एस पर हो। जानना है कि चौराहा ई यातायात नियम तोड़े बिना पहुँच-योग्य है या नहीं।

इस समस्या के लिए सबसे छोटा सफर ज़रूरी नहीं। सिर्फ हाँ या नहीं: कोई कानूनी रास्ता है या नहीं?

हाथ से हर रास्ता आज़माओगे तो चक्र (घूमा जा सकने वाला ब्लॉक) पर हमेशा के लिए फँस जाओगे। इसलिए हर खोज में देखे गए चौराहे निशान लगाओ और उन्हें दोबारा न खोलो।

चौड़ाई-पहले खोज (बीएफएस) एस से लहर की तरह फैलती है: पहले एस के पड़ोसी, फिर उनके पड़ोसी, और आगे। गहराई-पहले खोज (डीएफएस) एक सड़क पर जितना दूर जा सके जाती है, फिर पीछे लौटती है। दोनों पहुँच-योग्यता बता सकते हैं। इंटरव्यू में इस हाँ/नहीं के लिए अक्सर बीएफएस पसंद: रिकर्शन स्टैक का खतरा नहीं, और ई को पहली बार छूते ही मिल जाता है (बाद में पूछो तो कूद गिनती में सबसे छोटा रास्ता भी)।

---

२. समस्या सादे शब्दों में

इनपुट: एक निर्देशित ग्राफ, शुरू नोड S, अंत नोड E।

आउटपुट: S से E तक निर्देशित पथ हो तो true, वरना false।

नोड का रूप जो हम इस्तेमाल करते हैं:

import java.util.ArrayList;
import java.util.List;

class GraphNode {
    String name;
    List<GraphNode> neighbors = new ArrayList<>();

    GraphNode(String name) {
        this.name = name;
    }

    void addNeighbor(GraphNode n) {
        neighbors.add(n);
    }
}

हर नोड सिर्फ बाहर जाने वाले किनारे जानता है (neighbors)। पूरा ग्राफ वही है जो नोडों को जोड़कर बनाते हो। पहुँच जाँच के लिए अलग Graph क्लास ज़रूरी नहीं अगर S और E के रेफरेंस पहले से हैं।

छोटे उदाहरण:

किनारे (निर्देशित)	एस	ई	जवाब	क्यों
ए→बी, बी→सी	ए	सी	true	ए → बी → सी
ए→बी, बी→सी	सी	ए	false	ए की तरफ़ कोई तीर वापस नहीं
ए→बी, बी→ए	ए	बी	true	सीधा किनारा
ए→ए (सिर्फ स्व-लूप), और कोई किनारा नहीं	ए	ए	true	शुरू = अंत (या स्व-लूप)
ए→बी, सी→डी (दो हिस्से)	ए	डी	false	ए से डी पहुँच-योग्य नहीं

कोड से पहले स्पष्ट करो:

• निर्देशित या अनिर्देशित? (निर्देशित। बिना कहे किनारे दो-तरफ़ा मत मानो।)
• S == E हो तो? (आमतौर पर true: खाली पथ। इंटरव्यूअर से पुष्टि।)
• चक्र की अनुमति? (हाँ। देखे गए नोड ट्रैक करो।)
• नल इनपुट? (false या एक्सेप्शन। एक ठेका चुनो।)
• वज़न वाले किनारे? (सिर्फ पहुँच-योग्यता में बेमतलब।)

---

३. पहले सोचो (बीएफएस पसंदीदा)

डीएफएस की पहली सोच

मौजूदा नोड से हर अनदेखे पड़ोसी पर रिकर्शन। कोई कॉल E पाए तो true। चक्र न लगे इसलिए विज़िटेड लगाओ।

चलता है। इंटरव्यू की दिक्कतें:

• गहरे ग्राफ पर कॉल स्टैक फट सकता है (जावा का डिफ़ॉल्ट स्टैक बहुत बड़ा नहीं)।
• असली छोटे रास्ते से पहले लंबी गलत शाखा में भटक सकते हो।

बीएफएस (इस समस्या के लिए पसंदीदा)

कतार इस्तेमाल करो:

१. S == E हो तो true लौटाओ। २. S को कतार में डालो। S को विज़िटेड मानो। ३. जब तक कतार खाली न हो:

• आगे का नोड u निकालो।
• u के हर पड़ोसी v पर:
  • v == E हो तो true।
  • v विज़िटेड न हो तो निशान लगाकर कतार में डालो। ४. कतार खाली → रास्ता नहीं → false।

साफ डिफ़ॉल्ट क्यों:

• साफ़ कतार, रिकर्शन गहराई की चिंता नहीं।
• E पहली बार देखते ही किनारे-गिनती में सबसे छोटा पथ मौजूद जान जाते हो। आगे के सवालों के लिए मुफ़्त गुण।
• विज़िटेड सेट हर नोड को ज़्यादा से ज़्यादा एक बार खोलता है: काम ओ(वी + ई)।

दो-तरफ़ा खोज (वैकल्पिक ज़िक्र)

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

---

४. जावा समाधान

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

class GraphNode {
    String name;
    List<GraphNode> neighbors = new ArrayList<>();

    GraphNode(String name) {
        this.name = name;
    }

    void addNeighbor(GraphNode n) {
        neighbors.add(n);
    }
}

class RouteBetweenNodes {

    /** True if a directed path exists from start to end. */
    static boolean routeExists(GraphNode start, GraphNode end) {
        if (start == null || end == null) {
            return false;
        }
        if (start == end) {
            return true;
        }

        Queue<GraphNode> queue = new LinkedList<>();
        Set<GraphNode> visited = new HashSet<>();

        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            GraphNode current = queue.poll();
            for (GraphNode neighbor : current.neighbors) {
                if (neighbor == end) {
                    return true;
                }
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return false;
    }

    // Optional: same idea with DFS recursion
    static boolean routeExistsDfs(GraphNode start, GraphNode end) {
        if (start == null || end == null) {
            return false;
        }
        if (start == end) {
            return true;
        }
        Set<GraphNode> visited = new HashSet<>();
        return dfs(start, end, visited);
    }

    private static boolean dfs(GraphNode current, GraphNode end, Set<GraphNode> visited) {
        if (current == end) {
            return true;
        }
        visited.add(current);
        for (GraphNode neighbor : current.neighbors) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, end, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}

A → B → C प्लस A → D पर ए से सी का वॉकथ्रू:

कदम	कतार (आगे पहले)	विज़िटेड	क्रिया
०	ए	{ए}	शुरू
१	बी, डी	{ए}	ए खोलो; बी और डी कतार में
२	डी, सी	{ए,बी}	बी खोलो; सी == अंत → true

अगर अंत ई हो और ए के हिस्से से कोई किनारा न पहुँचे, बीएफएस कतार खाली कर false देगा।

ऑब्जेक्ट पहचान (neighbor == end) सही है जब S और E वही रेफरेंस हों जो ग्राफ रखता है। नाम से नए नोड बनाओ तो नाम या आईडी से तुलना करो। इंटरव्यू में लगभग हमेशा असली नोड ऑब्जेक्ट मिलते हैं।

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
बीएफएस	ओ(वी + ई)	ओ(वी) कतार + विज़िटेड	हर नोड और किनारा एक बार (बाहर जाने वाले)
डीएफएस रिकर्सिव	ओ(वी + ई)	ओ(वी) विज़िटेड + कॉल स्टैक	वही क्रम; गहराई वी तक
बिना विज़िटेड	हमेशा चक्र में फँस	-	चक्र पर टूटा

V = सबसे खराब में पहुँच-योग्य नोड (या पूरा ग्राफ अगर वैश्विक निशान)। E = पार किए किनारे। ओ(वी) से ज़्यादा विज़िटेड एंट्री नहीं चाहिए।

---

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छेड़ते हैं:

• S == E → true (खाली पथ) जब तक समस्या न बदलें।
• शुरू या अंत null → false (या थ्रो)। start.neighbors पर एनपीई मत दो।
• सिर्फ स्व-लूप → S E न हो तो S का लूप जादू से E नहीं पहुँचाता।
• चक्र → विज़िटेड सेट ज़रूरी। बिना उसके ए→बी→ए अटक जाता है।
• टूटा ग्राफ → पहुँच-योग्य न होने पर false, एक्सेप्शन नहीं।
• बिना बाहर किनारे वाला नोड → खोलना कुछ नहीं करता; कतार के बाकी से खोज चलती है।
• एक से ज़्यादा किनारे / डुप्लिकेट पड़ोसी → विज़िटेड काम को रैखिक रखता है।

आम गलतियाँ:

१. ग्राफ को अनिर्देशित मानना। चुपचाप उल्टे किनारे जोड़ना यहाँ गलत है। २. विज़िटेड भूलना। किसी भी चक्र पर अनंत लूप। ३. विज़िटेड बहुत देर से लगाना। बीएफएस में कतार में डालते समय लगाओ ताकि अलग-अलग पैरेंट से एक नोड कई बार न जाए। ४. नाम या डेटा से गलत तुलना जब ऑब्जेक्ट अलग हों। ग्राफ GraphNode रेफरेंस रखता हो तो रेफरेंस समानता पसंद करो। ५. बीएफएस शुरू करते समय S को विज़िटेड न डालना। S पर लौटने वाला चक्र हमेशा फिर से खोलेगा। ६. सिर्फ E कतार से निकलने पर true, पड़ोसियों को कभी न जाँचना। खोजते समय या निकालते समय, एक तरीका चुनो। ऊपर का कोड पड़ोसी end होते ही true देता है।

कम से कम इस्तेमाल:

GraphNode a = new GraphNode("A");
GraphNode b = new GraphNode("B");
GraphNode c = new GraphNode("C");
a.addNeighbor(b);
b.addNeighbor(c);

boolean ok = RouteBetweenNodes.routeExists(a, c); // true
boolean no = RouteBetweenNodes.routeExists(c, a); // false

---

७. दोस्त को समझाओ सार

नोड्स के बीच रूट मतलब निर्देशित पहुँच-योग्यता:

१. ग्राफ नोड में पड़ोसियों की सूची (सिर्फ बाहर जाने वाले किनारे)। २. सवाल: उन तीरों से एस से ई तक चल सकते हो? ३. एस से बीएफएस: कतार + विज़िटेड सेट। ई दिखे तो true। कतार खाली तो false। ४. डीएफएस भी चलता है; इंटरव्यू का सुरक्षित डिफ़ॉल्ट बीएफएस (गहरी रिकर्शन नहीं, साफ़ ओ(वी+ई))। ५. हमेशा विज़िटेड लगाओ। निर्देशित मतलब ए→बी से बी→ए नहीं निकलता। एस==ई पर true।

तीन नोड बनाकर हाथ से बीएफएस चला सको और चक्र पर विज़िटेड क्यों ज़रूरी समझा सको, तो समस्या ४.१ तुम्हारी है। अध्याय ४ सबसे साधारण काम के ग्राफ सवाल से शुरू होता है: एस से ई पहुँच-योग्य है?

---

श्रृंखला

• गाइड: सीटीसीआई श्रृंखला गाइड
• पिछला: एनिमल शेल्टर
• अगला: मिनिमल ट्री