DFS: खोज, वापसी और ट्रैवर्सल फ़ॉरेस्ट

पहले पहुँच को समझें

Depth-first search (DFS) किसी अनदेखे पड़ोसी की पूरी खोज करने के बाद लौटता है और अगला पड़ोसी देखता है। इस पाठ में discovery और finish के क्रम, visited चिह्न और एक स्रोत से खोज बनाम सभी वर्टेक्स की खोज समझेंगे। पहले “ग्राफ़ की शब्दावली और आसन्नता के निरूपण” पढ़ें। रिकर्शन का यह विचार याद रखें: हर कॉल के अपने स्थानीय चर होते हैं और संतान कॉल लौटने पर रुका हुआ काम आगे बढ़ता है। ऐरे, लूप, शर्तें और फ़ंक्शन पहले से आने चाहिए।

हमारे ग्राफ़ में n वर्टेक्स हैं, जिनके नंबर 0 से n−1 हैं; 0 <= n <= 6। यह simple undirected ग्राफ़ है: self-loop और parallel edge नहीं हैं, और हर एज दोनों दिशाओं में चलने देती है। पूरी तरह आरंभित 0/1 adjacency matrix सममित है और विकर्ण पर शून्य है। adj[u][v]=1 का अर्थ एज का होना है; 0 उसका न होना। यह भार नहीं, अस्तित्व का चिह्न है। हर पड़ोसी-जाँच बढ़ते वर्टेक्स नंबर में होगी। स्रोत या पड़ोसियों का क्रम बदलने पर दूसरा वैध DFS क्रम मिल सकता है।

खोजें, नीचे जाएँ, लौटें, समाप्त करें

किसी अनदेखे वर्टेक्स u में प्रवेश करते समय:

1. तुरंत u को seen चिह्न दें और discovery क्रम में जोड़ें।
2. v=0,1,...,n−1 जाँचें। हर जुड़े हुए अनदेखे v का DFS parent u रखें, depth[v]=depth[u]+1 करें और रिकर्शन से v की पूरी खोज करें।
3. सभी पड़ोसियों की जाँच समाप्त होने पर u को finish क्रम में जोड़कर लौटें।

Discovery पहली बार प्रवेश है। Finish उस कॉल द्वारा शुरू किया गया पूरा रिकर्सिव काम समाप्त होना है। Finish दूसरी discovery नहीं है: पहुँचे हुए हर वर्टेक्स का दोनों सूचियों में एक-एक स्थान है। इस पाठ में केवल “DFS क्रम” कहने पर discovery क्रम समझें; finish पूछने पर अलग सूची लिखें। शाखाएँ होने पर कोई शुरुआती संतान अगली संतान की discovery से पहले finish हो सकती है, इसलिए finish हमेशा discovery का उलटा नहीं है।

संतान की खोज के दौरान parent कॉल अपने लूप में रुकी रहती है। उसके u और v सुरक्षित रहते हैं। संतान के लौटने पर वही कॉल अपनी पड़ोसी-जाँच आगे बढ़ाती है। जिस वर्टेक्स का कोई अनदेखा पड़ोसी न बचे, वह तुरंत finish होता है; इसके लिए उसकी degree शून्य होना आवश्यक नहीं।

रिकर्शन से पहले चिह्न लगाने पर दोबारा प्रवेश रुकता है। अनिर्देशित एज 0–1 में, 1 की कॉल को 0 की ओर लौटती एज दिखती है, लेकिन 0 पहले से seen होने पर वह उसे छोड़ देती है। चक्र में भी पहले से seen वर्टेक्स की एज छोड़ते हैं। केवल seen से यह नहीं पता चलता कि उसकी कॉल अभी सक्रिय है या finish हो चुकी है। यह प्रोग्राम एज-वर्गीकरण या cycle detection नहीं करता; undirected ग्राफ़ में parent की ओर एज मिलना सामान्य है।

हल किया उदाहरण 1: त्रिभुज में depth सबसे छोटी दूरी नहीं है

नया ग्राफ़ लें: वर्टेक्स 0,1,2 और एज {0–1,0–2,1–2}। स्रोत 0 है और पड़ोसी बढ़ते क्रम में हैं।

चुनी गई DFS ट्री एज 0–1 और 1–2 हैं। मूल ग्राफ़ की एज 0–2 अभी भी मौजूद है, लेकिन parent एज नहीं बनी। Parents NONE,0,1 और DFS depths 0,1,2 हैं। फिर भी मूल ग्राफ़ में 0 से 2 सिर्फ एक एज दूर है। DFS depth चुने हुए ट्रैवर्सल ट्री की parent एज गिनती है; वह स्रोत से न्यूनतम एज संख्या की गारंटी नहीं देती। यहाँ विषय ट्रैवर्सल है, shortest path की गणना नहीं।

हल किया उदाहरण 2: शाखाओं में finish उलटा क्रम नहीं

पहले पाठ वाला ग्राफ़ लें: n=5, एज {0–1,0–3,1–2,1–3,3–4}। स्रोत 0 से discovery क्रम 0,1,2,3,4 है। पहले 0, फिर 1, फिर 2 में प्रवेश होता है। 2 का अकेला पड़ोसी 1 seen है, इसलिए 2 finish होता है। अभी सक्रिय 1 की कॉल अब 3 खोजती है और 3 फिर 4 खोजता है। Finish क्रम 2,4,3,1,0 मिलता है।

यह discovery का उलटा 4,3,2,1,0 नहीं है। विशेष बात: 3 की discovery से पहले 2 finish हो गया। Parents NONE,0,1,1,3 और depths 0,1,2,2,3 हैं। हर गैर-रूट का parent उससे पहले discover होता है और हर संतान अपने parent से पहले finish होती है। इससे यह निष्कर्ष नहीं निकलता कि सभी sibling उलटे discovery क्रम में finish होंगे।

हल किया उदाहरण 3: स्रोत और पूरा फ़ॉरेस्ट

नीचे के प्रोग्राम में छह वर्टेक्स हैं: {0,1,2} का त्रिभुज, एज 3–4 और अलग-थलग वर्टेक्स 5। तीन connected components हैं। स्रोत 0 की नई खोज केवल 0,1,2 discover और 2,1,0 finish करती है। 3,4,5 unseen रहते हैं और उनका parent तथा depth NONE रहता है। यह स्रोत 0 से पहुँच का पूरा उत्तर है; खोज की विफलता नहीं।

सभी वर्टेक्स के लिए एक ही साझा marker ऐरे रखें और संभावित रूट 0,1,...,5 देखें। 0 से उसकी पूरी component खोजें; seen 1 और 2 छोड़ें। अनदेखे 3 से शुरू करें, जो 4 खोजता है; फिर 4 छोड़ें। अंत में अलग-थलग 5 से शुरू करें। Discovery 0,1,2,3,4,5 और finish 2,1,0,4,3,5 हैं। रूट संख्या 3 है। हर नए रूट का parent NONE और depth 0 है। Depth अपने ट्री के रूट से है, सभी की 0 से नहीं। हर संभावित रूट के बीच seen साफ न करें; ऐसा करने पर components दोबारा खोजी जाएँगी।

इस undirected मॉडल में फ़ॉरेस्ट रूट की संख्या connected components की संख्या है; isolated वर्टेक्स भी एक component है। Directed ग्राफ़ की खोज केवल outgoing arcs पर जाती है। उसकी reachable set या outer-loop DFS forest को अपने-आप undirected, weakly connected या strongly connected components नहीं कह सकते। जैसे केवल arc 1→0 हो, तो बढ़ते-रूट लूप में 0 और 1 दोनों से नई खोज शुरू होगी, जबकि दिशा हटाने पर एक component है। हमारा validator जानबूझकर केवल undirected इनपुट स्वीकार करता है।

सीमित रिकॉर्ड और स्टोरेज की शर्तें

Graph रिकॉर्ड में n और 6×6 matrix है। Traversal रिकॉर्ड में साझा markers, parent/depth ऐरे, दोनों क्रमों के ऐरे, उनकी लंबाइयाँ और रूट गिनती है। स्टोरेज का आकार स्थिर है; dynamic allocation नहीं है। n से छोटे इंडेक्स ही वर्टेक्स हैं। अनुपयोगी matrix खाने validation और traversal में नहीं पढ़े जाते। क्रम ऐरे के केवल पहले discovered या finished खाने अर्थपूर्ण हैं; बाकी खाने में शून्य होना वर्टेक्स 0 की अतिरिक्त visit नहीं है।

Caller को अलग, आपस में न चढ़ने वाले पतों पर जीवित और आरंभित Graph तथा Traversal ऑब्जेक्ट देने होंगे। दोनों pointer non-null और सही होने चाहिए। Validator ऑब्जेक्ट का जीवनकाल या वास्तविक स्टोरेज नहीं जाँच सकता। खोज के दौरान ग्राफ़ अपरिवर्तित रहेगा और कॉल एक के बाद एक होंगी। valid_graph पहले 0<=n<=CAP, सक्रिय खानों के 0/1 मान, शून्य विकर्ण और सममिति जाँचता है। Self-loop और असममित matrix इस अनुबंध में अवैध हैं; त्रिभुज जैसे चक्र वैध हैं।

दोनों सार्वजनिक खोज फ़ंक्शन हर कॉल पर परिणाम नए सिरे से आरंभ करते हैं। सफलता पर 1, अवैध ग्राफ़ पर 0 लौटाते हैं; dfs_source गलत स्रोत पर भी 0 देता है। n=0 का खाली ग्राफ़ वैध है: dfs_forest खाली क्रम और शून्य रूट के साथ सफल होता है, लेकिन dfs_source के लिए कोई वैध स्रोत नहीं होता। आंतरिक visit अकेले validator नहीं है; wrappers से ही बुलाएँ, जो सही अनदेखा वर्टेक्स और आरंभित रूट depth सुनिश्चित करते हैं।

पूरा C11 प्रोग्राम

चलाने से पहले आउटपुट का अनुमान लगाएँ। यहाँ matrix के मान नहीं, वर्टेक्स नंबर छपते हैं।

#include <stdio.h>

enum { CAP = 6, NONE = -1 };

typedef struct {
    int n;
    int adj[CAP][CAP];
} Graph;

typedef struct {
    int seen[CAP];
    int parent[CAP];
    int depth[CAP];
    int discovery[CAP];
    int finish[CAP];
    int discovered;
    int finished;
    int roots;
} Traversal;

int valid_graph(const Graph *g) {
    if (g->n < 0 || g->n > CAP) {
        return 0;
    }
    for (int u = 0; u < g->n; ++u) {
        for (int v = 0; v < g->n; ++v) {
            if ((g->adj[u][v] != 0 && g->adj[u][v] != 1) ||
                (u == v && g->adj[u][v] != 0) ||
                g->adj[u][v] != g->adj[v][u]) {
                return 0;
            }
        }
    }
    return 1;
}

void reset_traversal(Traversal *t) {
    *t = (Traversal){0};
    for (int v = 0; v < CAP; ++v) {
        t->parent[v] = NONE;
        t->depth[v] = NONE;
    }
}

/* Internal helper: validated graph; u is valid and not yet seen. */
void visit(const Graph *g, int u, Traversal *t) {
    t->seen[u] = 1;
    t->discovery[t->discovered] = u;
    ++t->discovered;
    for (int v = 0; v < g->n; ++v) {
        if (g->adj[u][v] == 1 && !t->seen[v]) {
            t->parent[v] = u;
            t->depth[v] = t->depth[u] + 1;
            visit(g, v, t);
        }
    }
    t->finish[t->finished] = u;
    ++t->finished;
}

int dfs_source(const Graph *g, int source, Traversal *t) {
    reset_traversal(t);
    if (!valid_graph(g) || source < 0 || source >= g->n) {
        return 0;
    }
    t->roots = 1;
    t->depth[source] = 0;
    visit(g, source, t);
    return 1;
}

int dfs_forest(const Graph *g, Traversal *t) {
    reset_traversal(t);
    if (!valid_graph(g)) {
        return 0;
    }
    for (int v = 0; v < g->n; ++v) {
        if (!t->seen[v]) {
            ++t->roots;
            t->depth[v] = 0;
            visit(g, v, t);
        }
    }
    return 1;
}

void print_order(const char *label, const int order[], int count) {
    printf("%s", label);
    for (int i = 0; i < count; ++i) {
        printf(" %d", order[i]);
    }
    printf("\n");
}

#ifndef DFS_NO_MAIN
int main(void) {
    Graph g = {6, {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 1, 0, 0, 0},
        {1, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    Traversal t = {0};
    if (!dfs_source(&g, 0, &t)) {
        return 1;
    }
    print_order("source discovery:", t.discovery, t.discovered);
    print_order("source finish:", t.finish, t.finished);
    printf("source depth of 2: %d\n", t.depth[2]);
    if (!dfs_forest(&g, &t)) {
        return 1;
    }
    print_order("forest discovery:", t.discovery, t.discovered);
    print_order("forest finish:", t.finish, t.finished);
    printf("forest roots: %d\n", t.roots);
    return 0;
}
#endif

सटीक आउटपुट:

source discovery: 0 1 2
source finish: 2 1 0
source depth of 2: 2
forest discovery: 0 1 2 3 4 5
forest finish: 2 1 0 4 3 5
forest roots: 3

नई syntax और सुरक्षा का कारण

“typedef struct” रिकॉर्ड प्रकार को छोटा नाम देता है। Graph g={6,{...}} पहले n, फिर nested matrix की पंक्तियाँ आरंभ करता है। Traversal t={0} सभी fields शून्य करता है। reset_traversal का C11 compound literal (Traversal){0} नया शून्य रिकॉर्ड मान बनाकर सौंपता है, फिर हर parent और depth को NONE=-1 करता है। यह sentinel “parent नहीं” या “अभी खोजी गई depth नहीं” दर्शाता है; इसे ऐरे इंडेक्स नहीं बनाते।

&g और &t पते देते हैं। Graph * तथा Traversal * पैरामीटर caller के असली रिकॉर्ड की ओर इशारा करते हैं। g->n, pointer से field चुनता है; यह (*g).n जैसा है। const Graph * से ग्राफ़ पढ़ सकते हैं, बदल नहीं सकते। Mutable Traversal * के कारण रिकर्सिव कॉल वही markers और output ऐरे साझा करती हैं। हर कॉल के स्थानीय loop चर फिर भी अलग हैं। हर recursive entry पर ऐरे की कॉपी नहीं बनती। print_order का array parameter भी मौजूदा स्टोरेज को संदर्भित करता है। उसका const char *label, अंत में शून्य कैरेक्टर वाले टेक्स्ट स्ट्रिंग की ओर pointer है; %s उस स्ट्रिंग को छापता है। main के string literal labels वैध स्टोरेज और अंतिम शून्य कैरेक्टर देते हैं।

|| short-circuit करता है और visit बुलाने से पहले स्रोत सीमा जाँची जाती है। && का दायाँ भाग तभी चलता है जब बायाँ true हो। !t->seen[v] का अर्थ v अभी चिह्नित नहीं है; ++ एक बढ़ाता है। reset की braces आरंभित temporary रिकॉर्ड मान बनाती हैं, dynamic memory नहीं। <stdio.h>, printf की घोषणा देता है; %d int छापता है और \n पंक्ति समाप्त करता है। #ifndef DFS_NO_MAIN अलग test फ़ाइल को दूसरा main बनाए बिना helpers शामिल करने देता है; सामान्य compilation में उदाहरण का main रहता है।

हर recursive entry पहले अनदेखा वर्टेक्स चिह्नित करती है, इसलिए कुल entry अधिकतम n और एक साथ सक्रिय visit कॉल भी अधिकतम n हैं। Isolated रूट की एक कॉल होती है और वह दोनों क्रमों में आता है। अधिकतम depth n−1 है, यहाँ अधिकतम 5। क्रमों की लंबाई n से बड़ी नहीं होती, इसलिए स्थिर ऐरे पर्याप्त हैं। यह सीमित उदाहरण बहुत बड़े ग्राफ़ में call stack सुरक्षित रहने की गारंटी नहीं है।

n×n matrix की validation O(n²) है। पहुँचे हुए r वर्टेक्स में हर बार n खाने जाँचने पर traversal O(rn), साथ में initialization, लेता है। पूरा forest O(n²) है। दिए गए validator सहित source search भी कुल O(n²) है। प्रसिद्ध O(n+m) DFS सीमा adjacency list मानती है, हर matrix पंक्ति की पूरी जाँच नहीं। सामान्य आकार वाले संस्करण में matrix O(n²) और markers, parent/depth, क्रम तथा recursive stack O(n) अतिरिक्त स्थान लेते हैं। यहाँ CAP=6 सभी वास्तविक आकार सीमित करता है।

सीमित उपमा

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

मुख्य बातें

• नीचे जाने से पहले चिह्न लगाएँ; केवल जुड़े, अनदेखे वर्टेक्स पर recurse करें।
• Discovery पहली entry है; finish पूरी पड़ोसी-जाँच और child कॉलों के बाद है।
• एक source कॉल ठीक उसी स्रोत से पहुँचने योग्य वर्टेक्स खोजती है।
• साझा markers वाला बढ़ते-रूट outer loop पूरा DFS forest देता है।
• इस undirected मॉडल में forest roots, connected components गिनते हैं।
• DFS parent depth सबसे छोटी दूरी होना आवश्यक नहीं।
• Matrix में हर visit पर n खाने जाँचते हैं; list वाला complexity नियम अलग है।
• आंतरिक recursion से पहले सीमित निरूपण और स्रोत की वैधता जाँचें।

दो अतिरिक्त अभ्यास

1. छह-वर्टेक्स प्रोग्राम में स्रोत 4 करें। दोनों क्रम और खोजी गई depths निकालें। उत्तर: discovery 4,3; finish 3,4; depth[4]=0 और depth[3]=1। बाकी unseen और NONE हैं। दूसरे component से शुरुआत अपने-आप वर्टेक्स 0 पर नहीं जाती।
2. n=3 और कोई एज नहीं। स्रोत 1 तथा पूरे forest की तुलना करें। उत्तर: स्रोत की discovery और finish दोनों [1], एक रूट। पूरे forest में दोनों [0,1,2], तीन रूट, सभी की depth 0। यहाँ सूचियाँ समान होने से दोनों घटनाओं की परिभाषा समान नहीं हो जाती।

यह मौलिक अभ्यासों वाला प्रारंभिक ट्रैवर्सल पाठ है। सबसे छोटे पथ के एल्गोरिदम, topological sorting और चक्र/एज-वर्गीकरण के लिए अलग पाठ चाहिए। ये पिछले परीक्षा-प्रश्न या पूरे पाठ्यक्रम का कवरेज नहीं हैं।

छह मौलिक अभ्यास प्रश्न

हर प्रश्न में ठीक एक विकल्प चुनें।

1

त्रिभुज {0–1,0–2,1–2} में स्रोत 0 और बढ़ते पड़ोसी क्रम पर discovery तथा finish क्या हैं?

A. Discovery 0,1,2; finish 2,1,0 B. Discovery 0,2,1; finish 1,2,0 C. Discovery 0,1,2; finish 0,1,2 D. Discovery 0,1,0,2; finish 2,0,1,0

2

n=4 और एज {0–1,2–3} में नया source DFS, 1 से शुरू होता है। कौन-से वर्टेक्स discover होंगे?

A. अपने-आप सभी चार B. केवल 1 C. ठीक 1 और 0 D. ठीक 1,0,2

3

रिकर्सिव पड़ोसी कॉलों से पहले साझा seen चिह्न क्यों लगाना चाहिए?

A. यह सभी वर्टेक्स क्रमबद्ध करता है B. यह DFS depth को सबसे छोटी दूरी बनाता है C. यह ग्राफ़ के सारे चक्र मिटाता है D. यह पीछे की एज से उसी सक्रिय वर्टेक्स में फिर प्रवेश रोकता है

4

स्रोत 0 और ग्राफ़ {0–1,0–2,1–2} में parent[2]=1 तथा depth[2]=2 हैं। सही अर्थ क्या है?

A. 0 से 2 के हर पथ में दो एज हैं B. चुने DFS parent पथ में दो एज हैं, जबकि मूल ग्राफ़ में एक-एज पथ भी है C. ग्राफ़ में एज 0–2 नहीं है D. वर्टेक्स 2 दो बार discover हुआ

5

n=0 के वैध खाली ग्राफ़ पर दिए wrappers क्या करते हैं?

A. दोनों ग्राफ़ को malformed मानकर अस्वीकार करते हैं B. स्रोत 0 वाला dfs_source सफल होकर 0 खोजता है C. dfs_forest शून्य रूट के साथ सफल; स्रोत 0 वाला dfs_source विफल D. dfs_forest एक खाली रूट बनाता है

6

n=5, एज {0–1,0–3,1–2,1–3,3–4}, स्रोत 0 और बढ़ते पड़ोसी क्रम पर finish क्रम कौन-सा है?

A. 2,4,3,1,0 B. 4,3,2,1,0 C. 0,1,2,3,4 D. 2,1,4,3,0

हल सहित उत्तर

1: A

A सही है: 0 से 1, फिर 2 में उतरते हैं; सबसे गहरी कॉल से रूट तक finish होता है।

B गलत है: 1 से पहले 2 चुनना दिए बढ़ते पड़ोसी क्रम के विरुद्ध है।

C गलत है: अधूरी child कॉलों से पहले 0 finish नहीं हो सकता।

D गलत है: नीचे जाने से पहले 0 चिह्नित है; उसकी दोबारा discovery नहीं होती।

2: C

A गलत है: source कॉल में अलग components शुरू करने वाला outer loop नहीं है।

B गलत है: अनदेखा पड़ोसी 0, 1 से पहुँचने योग्य है।

C सही है: एज 1–0 इन दो reachable वर्टेक्स को जोड़ती है; 2 और 3 नहीं पहुँचते।

D गलत है: 1 से 2 का पथ नहीं; खोज नंबर देखकर छलाँग नहीं लगाती।

3: D

A गलत है: चिह्न visit दर्ज करता है, संख्यात्मक sorting नहीं।

B गलत है: त्रिभुज में स्रोत से एक एज दूर वर्टेक्स की DFS depth फिर भी 2 है।

C गलत है: ट्रैवर्सल ग्राफ़ या एज नहीं बदलता।

D सही है: पड़ोसी कॉल marker देखकर पुनः प्रवेश छोड़ती है, भले पुरानी कॉल अभी finish न हो।

4: B

A गलत है: सीधी एज 0–2 एक-एज पथ है।

B सही है: depth चुना ट्री पथ 0–1–2 मापती है, सबसे छोटी दूरी की गारंटी नहीं।

C गलत है: एज मौजूद हो सकती है, भले DFS parent एज न चुनी जाए।

D गलत है: depth parent एज गिनती है, discovery की बारंबारता नहीं।

5: C

A गलत है: अनुबंध शून्य वर्टेक्स की अनुमति देता है।

B गलत है: n=0 में वैध वर्टेक्स इंडेक्स 0 नहीं है।

C सही है: forest लूप की कोई iteration नहीं; source सीमा-जाँच 0 अस्वीकार करती है।

D गलत है: रूट असली खोजे गए वर्टेक्स हैं; खाली ग्राफ़ में कोई नहीं।

6: A

A सही है: 2 पहले finish; फिर 1, 3 और 4 खोजता है, जो 1 और 0 से पहले finish होते हैं।

B गलत है: discovery उलटने से 2, 3 और 4 के बाद आता है, जबकि वे 2 के finish के बाद ही discover होते हैं।

C गलत है: यह discovery क्रम है; रूट सबसे बाद finish होता है।

D गलत है: अनदेखे पड़ोसी 3 और उसके descendant 4 की खोज से पहले 1 finish नहीं हो सकता।