ब्रेड्थ-फ़र्स्ट सर्च: क्यू और बिना वज़न वाली दूरियाँ

पड़ोसियों से परतों तक

पहले “ग्राफ़ की शब्दावली और आसन्नता के निरूपण” (graph-terms-and-adjacency-representations) और “क्यू: FIFO और सीमित circular array” (queues-fifo-and-bounded-circular-array) पढ़ें। वर्टेक्स, एज, adjacency matrix, वैध ऐरे इंडेक्स और FIFO enqueue/dequeue की समझ चाहिए। इस पाठ में एक स्रोत से पहुँचने योग्य सभी वर्टेक्स ढूँढेंगे, सबसे छोटी पथ-दूरी की बढ़ती एज-संख्या के क्रम में। ग्राफ़ सरल, अनिर्देशित (undirected) और बिना वज़न वाला है। वर्टेक्स 0 से n−1 हैं। a[u][v] में 1 का अर्थ एज है; 0 का अर्थ एज नहीं है। मैट्रिक्स सममित है और विकर्ण पर शून्य हैं।

कल्पना करें कि संपर्कों के नेटवर्क में संदेश पहुँचाना है। आपके सीधे संपर्क पहली लहर हैं, उनके अब तक अनजान संपर्क दूसरी लहर, और आगे भी ऐसा ही। FIFO प्रतीक्षा-पंक्ति पहले वाली लहर को बाद वाली से पहले संसाधित करती है। किसी व्यक्ति को पंक्ति में डालते ही चिह्नित करते हैं, ताकि दो संपर्क उसे दो बार न डालें। यह उपमा कड़ियों की संख्या समझाती है; यात्रा-समय, संदेश की देरी या एज की लागत नहीं।

ब्रेड्थ-फ़र्स्ट सर्च (BFS) पहले स्रोत को दूरी 0 पर खोजती है, फिर दूरी 1, फिर 2 के वर्टेक्स, और आगे। खोज लेना (discovery) यानी दूरी तय करके क्यू में डालना। संसाधित करना (processing) यानी क्यू से निकालकर उसके पड़ोसी देखना। खोजा जा चुका वर्टेक्स अभी प्रतीक्षा में हो सकता है। यहाँ छापा गया क्रम processing का है। हर वर्टेक्स FIFO क्यू में केवल एक बार जाता है, इसलिए यहाँ discovery का क्रम भी यही है।

एक चिह्न से दो काम

हर वर्टेक्स के लिए dist[v] = −1 रखें। शुरुआत में इसका अर्थ “अभी नहीं खोजा” है; सफल खोज समाप्त होने पर इसका अर्थ “इस स्रोत से नहीं पहुँच सकते” है। dist[source] = 0 करें और स्रोत को enqueue करें। जब तक क्यू खाली नहीं:

1. आगे से u को dequeue करें।
2. v = 0, 1, …, n−1 इसी क्रम में जाँचें।
3. यदि a[u][v] == 1 और dist[v] == −1 है, तो dist[v] = dist[u] + 1 करके v को enqueue करें।

दूरी का ऐरे ही visited/discovered चिह्न भी है। चिह्न enqueue से पहले लगाएँ, बाद में dequeue होने पर नहीं। देर करने पर प्रतीक्षा में मौजूद दो parent अपने साझा पड़ोसी को उसके संसाधित होने से पहले दो बार डाल सकते हैं। इस नियम के साथ चक्र समस्या नहीं है: स्रोत पहले से चिह्नित है और बाकी हर वर्टेक्स पहली insertion पर चिह्नित हो जाता है।

पड़ोसी बढ़ते इंडेक्स में देखने से ट्रेस का क्रम निश्चित रहता है। यह एक ही दूरी की परत के भीतर बराबरी का क्रम तय करता है; पूरे आउटपुट को वर्टेक्स संख्या के अनुसार क्रमबद्ध नहीं करता। पड़ोसियों का क्रम बदलने से processing क्रम और पहली बार खोजने वाला parent बदल सकता है, सबसे छोटी दूरी नहीं।

ये दूरियाँ सबसे छोटी क्यों हैं?

स्रोत से स्वयं तक शून्य एज का रास्ता है। जब u, v को खोजता है, तब u तक के ज्ञात रास्ते में एज u−v जोड़ने से dist[u] + 1 लंबाई का रास्ता मिलता है। इसलिए हर निर्धारित दूरी के पीछे सचमुच एक रास्ता है।

FIFO पहले की पूरी परतों को बाद की परतों से पहले संसाधित करता है। दूरी d की परत पर काम करते समय नया वर्टेक्स दूरी d+1 के साथ पीछे जुड़ता है; पहले से प्रतीक्षा में मौजूद दूरी-d वर्टेक्स उससे आगे रहते हैं। मानें कि v को पहली बार दूरी d+1 मिली, लेकिन कोई छोटा रास्ता भी था। उस छोटे रास्ते पर v से पहले वाला वर्टेक्स किसी पहले की परत में संसाधित होता और v को पहले ही खोज लेता। यह विरोधाभास है। इसलिए पहली निर्धारित दूरी अंतिम है।

यह बिना वज़न वाले ग्राफ़ में एज की संख्या के अनुसार सबसे छोटा रास्ता है। समान धनात्मक लागत वाली सभी एज के लिए भी यही क्रम काम करता है। असमान वज़न होने पर न्यूनतम कुल लागत की गारंटी नहीं है। वज़न 100 वाली एक एज का रास्ता, वज़न 1 और 1 वाली दो एज से महँगा हो सकता है; BFS फिर भी एज-संख्या में एक एज को छोटा मानेगी। हमारे 0/1 मैट्रिक्स में वज़न नहीं, केवल एज की अनुपस्थिति/उपस्थिति है।

वर्तमान validator जानबूझकर केवल अनिर्देशित (undirected) ग्राफ़ स्वीकार करता है। निर्देशित (directed) रूप के लिए बाहर जाने वाली arcs a[u][v]=1 का अनुसरण करें और symmetry की शर्त हटाएँ। निर्देशित single-source खोज भी बिना वज़न वाले निर्देशित रास्तों की सबसे छोटी दूरी देती है, लेकिन उसका reachable set सामान्यतः connected component नहीं होता। साझा visited चिह्न के साथ कई root चुनने पर root-क्रम पर निर्भर traversal forest बनता है; उसके ट्री को weakly या strongly connected components न कहें। निर्देशित components के वे algorithms इस पाठ के बाहर हैं।

स्टोरेज और वैधता का अनुबंध

C11 प्रोग्राम में CAP = 6 है और dynamic allocation नहीं है। Graph में n तथा CAP×CAP पूर्णांक ऐरे है। BfsResult में दूरी, processing क्रम और count हैं। कॉलर एक जीवित, पूरी तरह initialized Graph और उससे अलग जीवित, लिखने योग्य BfsResult देता है। दोनों का स्टोरेज overlap नहीं करता। Null, dangling या कम आकार वाले pointer इस अनुबंध के बाहर हैं; वैधता-जाँच ऐसा स्टोरेज ठीक नहीं कर सकती जो मौजूद ही न हो। कॉलर को परिणाम के फ़ील्ड initialize करने की आवश्यकता नहीं, क्योंकि bfs इनपुट जाँचने से पहले सभी फ़ील्ड तय कर देता है।

सक्रिय वर्टेक्स 0 से n−1 तक हैं और 0 ≤ n ≤ CAP है। valid_graph पहले n जाँचता है, फिर सक्रिय हिस्से की सभी entries के 0/1 होने, सममित होने और विकर्ण पर शून्य होने की जाँच करता है। निष्क्रिय पंक्तियाँ/कॉलम वर्टेक्स नहीं हैं। n=0 वाला ग्राफ़ संरचनात्मक रूप से वैध है, पर उसका कोई वैध स्रोत नहीं, इसलिए bfs उसके लिए 0 लौटाता है। अवैध ग्राफ़ या स्रोत पर भी 0 लौटता है; count=0 तथा परिणाम के सभी स्लॉट −1 होते हैं। यह status अवश्य जाँचें: असफल validation को “सब वर्टेक्स unreachable हैं” वाला सफल परिणाम न समझें।

सफलता पर bfs, 1 लौटाता है। processing क्रम केवल order[0] से order[count−1] में है और सक्रिय वर्टेक्स की दूरियाँ केवल dist[0] से dist[n−1] में हैं। कॉल के दौरान ग्राफ़ बदलना नहीं चाहिए। यहाँ सभी कॉल एक के बाद एक होते हैं।

स्थानीय क्यू में CAP भौतिक स्लॉट हैं; एक खोज में कुल अधिकतम n स्लॉट इस्तेमाल होते हैं। head अगली निकाली जाने वाली entry का इंडेक्स है और tail अगली insertion का खाली स्थान। प्रतीक्षारत क्यू queue[head..tail−1] है; head == tail पर यह खाली है। queue[tail++] पहले पुराने tail पर लिखता है, फिर tail बढ़ाता है; queue[head++] पहले पुराने head से पढ़ता है, फिर head बढ़ाता है।

हर सक्रिय वर्टेक्स अधिकतम एक बार insert होता है, इसलिए 0 ≤ head ≤ tail ≤ n ≤ CAP। नए वर्टेक्स की insertion से पहले n से कम वर्टेक्स insert हुए हैं, अतः write सीमा में है। इंडेक्स कभी wrap नहीं करते और निकाले गए स्लॉट फिर उपयोग नहीं होते। यह एक खोज के लिए सीमित क्यू है, अनगिनत enqueue/dequeue के लिए सामान्य reusable क्यू नहीं। नई कॉल में नया क्यू बनता है। लंबे समय तक चलने वाले सामान्य सीमित क्यू को स्लॉट फिर उपयोग करने की व्यवस्था चाहिए, जैसे prerequisite की circular-array queue। दूरी अधिकतम n−1 ≤ 5 है, इसलिए जोड़ भी सीमित है।

ट्रेस 1: डायमंड, चक्र और एक अगम्य वर्टेक्स

n=6 और अनिर्देशित एज {0−1, 0−2, 1−3, 2−3, 3−4} लें। वर्टेक्स 5 अलग-थलग है। स्रोत 0 है। डायमंड 0−1−3−2−0 एक चक्र है। नीचे क्यू में केवल प्रतीक्षारत entries हैं; निकाली गई entries भौतिक ऐरे में रह सकती हैं।

processing क्रम 0,1,2,3,4 है; वर्टेक्स इंडेक्स क्रम में दूरी [0,1,1,2,3,−1] है। 0−1−3 और 0−2−3 दोनों, 3 तक दो एज वाले सबसे छोटे रास्ते हैं। निर्धारित scan क्रम के कारण 1 पहले 3 को खोजता है। 2 से 3 की एज, 3 को फिर enqueue नहीं करती। वर्टेक्स 5 कभी क्यू में नहीं जाता।

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

नया C syntax: typedef struct नाम वाले फ़ील्ड को एक record type में जोड़कर Graph या BfsResult जैसा छोटा नाम देता है। Graph g = {6, {...}} में पहला initializer n तय करता है; अंदर के braces मैट्रिक्स की पंक्तियाँ initialize करते हैं। &g और &result मौजूद records के पते bfs को देते हैं; फ़ंक्शन इन पतों से ग्राफ़ पढ़ता और कॉलर का परिणाम भरता है। int queue[CAP] = {0} क्यू के सभी स्लॉट शून्य करता है, हालाँकि केवल insert किए स्लॉट पढ़े जाते हैं। main में BfsResult result का initializer नहीं है, पर bfs किसी परिणाम को पढ़ने से पहले count तथा हर dist/order स्लॉट लिखता है, असफलता पर भी।

struct wrapper से const Graph pointer के द्वारा ग्राफ़ केवल पढ़ा जाता है; strict C11 में बहुआयामी ऐरे के qualifier का mismatch भी नहीं होता। g->n, pointer के माध्यम से फ़ील्ड चुनता है; out->dist[v] कॉलर के परिणाम में लिखता है। क्यू और counters हर कॉल के अपने स्थानीय मान हैं।

#include <stdio.h>

enum { CAP = 6 };
typedef struct {
    int n;
    int a[CAP][CAP];
} Graph;
typedef struct {
    int dist[CAP];
    int order[CAP];
    int count;
} BfsResult;

/* g points to one live, fully initialized Graph. */
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->a[u][v] != 0 && g->a[u][v] != 1) ||
                g->a[u][v] != g->a[v][u] ||
                (u == v && g->a[u][v] != 0)) {
                return 0;
            }
        }
    }
    return 1;
}

/* out points to separate live writable storage, disjoint from g. */
int bfs(const Graph *g, int source, BfsResult *out) {
    out->count = 0;
    for (int v = 0; v < CAP; ++v) {
        out->dist[v] = -1;
        out->order[v] = -1;
    }
    if (!valid_graph(g) || source < 0 || source >= g->n) {
        return 0;
    }
    int queue[CAP] = {0};
    int head = 0;
    int tail = 0;
    out->dist[source] = 0;
    queue[tail++] = source;
    while (head < tail) {
        int u = queue[head++];
        out->order[out->count++] = u;
        for (int v = 0; v < g->n; ++v) {
            if (g->a[u][v] == 1 && out->dist[v] == -1) {
                out->dist[v] = out->dist[u] + 1;
                queue[tail++] = v;
            }
        }
    }
    return 1;
}

int main(void) {
    Graph g = {6, {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {1, 0, 0, 1, 0, 0},
        {0, 1, 1, 0, 1, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0}
    }};
    BfsResult result;
    if (!bfs(&g, 0, &result)) {
        puts("Invalid graph or source");
        return 1;
    }
    printf("Order:");
    for (int i = 0; i < result.count; ++i) {
        printf(" %d", result.order[i]);
    }
    printf("\nDistance:");
    for (int v = 0; v < g.n; ++v) {
        printf(" %d", result.dist[v]);
    }
    putchar('\n');
    return 0;
}

अपेक्षित आउटपुट:

Order: 0 1 2 3 4 Distance: 0 1 1 2 3 -1

ट्रेस 2: बढ़ते पड़ोसी, पर पूरा क्रम संख्यानुसार नहीं

n=6 और एज {0−2, 0−4, 2−5, 4−1} लें; 3 अलग-थलग है। स्रोत 0 के लिए शुरू में [0] है। 0 निकालने पर क्यू [2,4] है, दोनों की दूरी 1 है। 2 निकालने पर 5 जुड़ता है: [4,5]। 4 निकालने पर 1 जुड़ता है: [5,1]। 5 और फिर 1 निकालने पर क्यू खाली है। क्रम 0,2,4,5,1 और दूरी [0,2,1,−1,1,2] है। 5 का parent पहले आया था, इसलिए 5, वर्टेक्स 1 से पहले संसाधित होता है। FIFO परतों का क्रम बचाता है, संख्याओं की sorting नहीं करता।

ट्रेस 3: अलग-थलग स्रोत और disconnected ग्राफ़

n=5 तथा एज {0−1, 1−2, 3−4} लें। 0 से खोज 0,1,2 संसाधित करती है और दूरी [0,1,2,−1,−1] देती है। 3 से नई खोज 3,4 संसाधित करती है और [−1,−1,−1,0,1] देती है। ये दो अलग स्रोतों की दो अलग दूरी-ऐरे हैं। पहले छह-वर्टेक्स उदाहरण में अलग-थलग स्रोत 5 से नई खोज केवल 5 संसाधित करती है और [−1,−1,−1,−1,−1,0] देती है। वैध एक-वर्टेक्स ग्राफ़ में भी अकेला स्रोत दूरी 0 पर संसाधित होता है। खाली ग्राफ़ में स्रोत नहीं हो सकता।

अनिर्देशित ग्राफ़ के सभी components का ट्रैवर्सल करने के लिए बाहरी लूप हर अब तक unvisited वर्टेक्स को नया root चुन सकता है। पूरे बाहरी लूप में साझा visited ऐरे रखते हुए queue traversal करें। इससे BFS forest बनता है। हर root की अपने component के संदर्भ में दूरी 0 होगी; ये किसी एक साझा स्रोत की दूरियाँ नहीं हैं। दिया गया bfs single-source है और हर कॉल में परिणाम reset करता है। उसे बार-बार बुलाकर केवल आखिरी परिणाम रखना forest जमा नहीं करता। यहाँ all-components routine लागू नहीं किया गया है।

लागत, गलतियाँ और मुख्य बातें

यदि स्रोत से r वर्टेक्स तक पहुँच सकते हैं, तो BFS लूप r पंक्तियों में प्रत्येक की n entries देखता है: O(nr), और सबसे खराब स्थिति में O(n²)। यह प्रोग्राम पूरे सक्रिय n×n मैट्रिक्स को validate भी करता है, इसलिए गैर-खाली इनपुट पर पूरी कॉल O(n²) है। आकार बढ़ा सकने वाले रूप में मैट्रिक्स का स्टोरेज O(n²) और क्यू व परिणाम का स्टोरेज O(n) है। यहाँ CAP स्थिर 6 है, इसलिए वास्तविक allocated आकारों की स्थिर सीमा है। जाना-पहचाना O(V+E) BFS समय adjacency lists के लिए है; यह मैट्रिक्स की हर पंक्ति जाँचने का समय नहीं है। लेखक की exhaustive जाँच अलग reference algorithm उपयोग करती है; वह विद्यार्थी के BFS का हिस्सा नहीं है।

सामान्य गलतियाँ: dequeue पर चिह्न लगाना; खोजे हुए वर्टेक्स को फिर enqueue करना; वर्टेक्स के लेबल से दूरी निकालना; disconnected वर्टेक्स की दूरी 0 बताना; enqueue और processing को एक ही क्षण मानना; failure status अनदेखा करना; असमान weighted ग्राफ़ पर न्यूनतम लागत का दावा करना; या पूरे आउटपुट को संख्यानुसार sorted बताना।

मुख्य बातों का बॉक्स:

• FIFO सबसे छोटी एज-संख्या की न घटने वाली दूरी में वर्टेक्स संसाधित करता है।
• insertion से पहले discovery चिह्न लगाएँ; हर वर्टेक्स अधिकतम एक बार क्यू में जाता है।
• dist[source]=0; सफलता के बाद dist[v]=−1 ठीक तभी है जब उस स्रोत से v तक नहीं पहुँच सकते।
• पड़ोसी क्रम समान परत की बराबरी तय करता है, दूरी नहीं बदलता।
• एक स्रोत की reachability और पूरे ग्राफ़ के components को ढकना अलग प्रश्न हैं।

हल-जाँच सहित दो अतिरिक्त अभ्यास

1. ट्रेस 1 में पड़ोसी scan उलटा करके v=n−1 से 0 करें। कोड बदलने से पहले क्रम और दूरियाँ बताएँ। उत्तर: क्रम 0,2,1,3,4; दूरियाँ पहले जैसी [0,1,1,2,3,−1]। अब 2 पहले 3 को खोजता है। 3 तक दो एज की सबसे छोटी दूरी नहीं बदलती।
2. ट्रेस 1 में अनिर्देशित एज 0−4 जोड़ें और scan बढ़ते क्रम में रखें। 0 संसाधित करने के ठीक बाद क्यू और फिर सभी दूरियाँ बताएँ। उत्तर: क्यू [1,2,4]; क्रम 0,1,2,4,3; दूरी [0,1,1,2,1,−1]। वर्टेक्स 1, वर्टेक्स 3 को दूरी 2 पर खोजता है; जब 4 संसाधित होता है, 3 पहले से चिह्नित है। नया छोटा रास्ता दूरी बदलता है, लेकिन अलग-थलग वर्टेक्स अब भी अगम्य है।

साथ दिए छह प्रश्न मौलिक आधारभूत अभ्यास हैं। प्रत्येक में ठीक एक सही विकल्प है। इन्हें पिछले परीक्षा-प्रश्न या पूरा परीक्षा-पाठ्यक्रम नहीं कहा गया है।

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

B01

एक अनिर्देशित ग्राफ़ में वर्टेक्स 0..4 और एज {0–2, 0–3, 2–4, 3–1} हैं। BFS का स्रोत 0 है और पड़ोसी बढ़ते क्रम में जाँचे जाते हैं। processing क्रम क्या है?

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

उत्तर: C

A गलत है: बढ़ता पड़ोसी scan पूरा processing क्रम sorted नहीं बनाता; 1 दो एज दूर है। B गलत है: पहले से क्यू में मौजूद 3, नए जुड़े 4 से पहले संसाधित होगा। C सही है: 0 से 2,3 जुड़ते हैं; 2 से 4 और 3 से 1 पीछे जुड़ते हैं; क्रम 0,2,3,4,1 है। D गलत है: 0 का scan पहले 2, फिर 3 डालता है, उलटा नहीं।

B02

n=6 के लिए अनिर्देशित एज {0–1, 1–2, 2–3, 0–3, 4–5} हैं। 0 से सफल BFS के बाद dist[0..5] क्या है?

A. [0,1,2,1,−1,−1] B. [0,1,2,3,−1,−1] C. [0,1,2,1,0,1] D. [1,2,3,2,−1,−1]

उत्तर: A

A सही है: 1 और 3 सीधे 0 से जुड़े हैं, 2 दो एज दूर है, और component {4,5} अगम्य है। B गलत है: सीधी एज 0–3 से dist[3]=1 है, भले ही तीन एज का रास्ता भी हो। C गलत है: इसमें दूसरे root 4 की दूरियाँ single-source परिणाम में मिला दी गई हैं। D गलत है: दूरी एज गिनती है, इसलिए स्रोत की दूरी 0 है, 1 नहीं।

B03

यह implementation v को enqueue करने से पहले dist[v] क्यों तय करता है?

A. क्यू को संख्यानुसार sorted करने के लिए B. हर आने वाली एज के लिए वर्टेक्स को एक बार डालने हेतु C. यह सुनिश्चित करने के लिए कि हर वर्टेक्स तक पहुँच सकते हैं D. ताकि दूसरा संसाधित पड़ोसी v को फिर enqueue न करे

उत्तर: D

A गलत है: FIFO insertion वर्टेक्स के लेबल sort नहीं करती। B गलत है: उद्देश्य प्रति वर्टेक्स एक insertion है, प्रति एज एक नहीं। C गलत है: चिह्न components के बीच नए रास्ते नहीं जोड़ते। D सही है: dist[v] तुरंत −1 से बदलता है, भले ही v अभी क्यू में प्रतीक्षा कर रहा हो।

B04

n वर्टेक्स के वैध ग्राफ़ पर इंडेक्स wrap किए बिना monotonic क्यू सुरक्षित क्यों है?

A. हर dequeue, tail को शून्य कर देता है B. एक कॉल में कुल अधिकतम n insertion होते हैं C. क्यू में कभी दो से अधिक वर्टेक्स नहीं होते D. adjacency matrix क्यू का आकार अपने-आप बढ़ा देता है

उत्तर: B

A गलत है: इस खोज में head और tail केवल बढ़ते हैं। B सही है: स्रोत और बाकी हर वर्टेक्स अधिकतम एक बार insert होते हैं; इसलिए write को n−1 के आगे स्लॉट नहीं चाहिए। C गलत है: star ग्राफ़ के केंद्र को संसाधित करने पर n−1 वर्टेक्स प्रतीक्षा में हो सकते हैं। D गलत है: क्यू का स्टोरेज स्थिर स्थानीय ऐरे है; मैट्रिक्स उसकी capacity नहीं बदलता।

B05

इस validation सहित मैट्रिक्स-आधारित BFS implementation के लिए कौन-सा दावा सही है?

A. पूरी कॉल हमेशा O(V+E) है क्योंकि यह BFS है B. यह किसी भी धनात्मक एज-वज़न के लिए कुल लागत न्यूनतम करता है C. यह सबसे छोटी एज-संख्या दूरी देता है; गैर-खाली पूरी कॉल O(n²) है D. यह किसी भी वैध स्रोत से हर component पर जाता है

उत्तर: C

A गलत है: मैट्रिक्स की पंक्तियों और पूरे मैट्रिक्स की जाँच पर adjacency-list वाली सीमा लागू नहीं होती। B गलत है: असमान वज़न पर कम एज वाला रास्ता अधिक महँगा हो सकता है। C सही है: FIFO बिना वज़न की दूरियाँ देता है और पूरे सक्रिय मैट्रिक्स की जाँच n² entries देखती है। D गलत है: अनिर्देशित ग्राफ़ में एक स्रोत केवल अपने component तक पहुँचता है।

B06

पूरी तरह initialized Graph में n=0 और शून्य मैट्रिक्स है। अलग वैध result स्टोरेज के साथ bfs(&g, 0, &result) क्या करता है?

A. 1 लौटाकर वर्टेक्स 0 संसाधित करता है B. 0 लौटाता है, count=0 करता है और परिणाम के सभी स्लॉट −1 करता है C. 1 लौटाता है और dist[0]=−1 रखता है क्योंकि 0 अगम्य है D. स्रोत जाँचने से पहले मैट्रिक्स की पंक्ति 0 पढ़ता है

उत्तर: B

A गलत है: n=0 पर सक्रिय वर्टेक्स 0 है ही नहीं। B सही है: खाली ग्राफ़ संरचनात्मक जाँच में वैध है, पर स्रोत 0 सीमा-जाँच में असफल है; परिणाम पहले initialize होता है। C गलत है: अगम्य सक्रिय वर्टेक्स सफल खोज का परिणाम हो सकते हैं; यहाँ वैध स्रोत ही नहीं और status 0 है। D गलत है: validator के पास जाँचने के लिए सक्रिय entries नहीं हैं; स्रोत की जाँच traversal से पहले कॉल अस्वीकार करती है।