ब्रेड्थ फर्स्ट सर्च (BFS) एल्गोरिथ्म
मान लीजिए आपके पास एक ग्राफ़ है जो
n वर्टिस (शिखरों) और e एज (धाराओं) से बना हुआ है। आप एक वर्टेक्स से शुरू करके धीरे-धीरे पूरे ग्राफ़ को घुमना चाहते हैं, ताकि उन सभी वर्टिस तक पहुँचा जा सके जो इस आरंभिक वर्टेक्स से कनेक्टेड (जुड़े) हैं। ऐसा करने के कई तरीके हैं, लेकिन सबसे लोकप्रिय तरीकों में से एक है ब्रेड्थ-फर्स्ट सर्च (BFS) एल्गोरिथ्म। अपनी प्रकृति के कारण, BFS आपको सोर्स वर्टेक्स से ग्राफ़ के सभी अन्य वर्टेक्स तक का सबसे छोटा रास्ता निकालने में मदद करता है, जिसके चलते यह कई एप्लिकेशन में बहुत उपयोगी साबित होता है।
BFS के बारे में सोचने का एक बढ़िया तरीका है ग्राफ़ में “आग लगाने” की कल्पना करना और यह देखना कि आग कैसे फैलती जाती है। मान लीजिए कि हर वर्टेक्स को जलने में 1 मिनट लगता है, और जैसे ही वह वर्टेक्स जल जाता है, आग उसके पड़ोसी वर्टेक्स तक फैल जाती है। फिर उन पड़ोसियों को भी 1 मिनट तक जलना पड़ता है, और उसके बाद आग उनके पड़ोसियों तक फैलती है, और यह क्रम इसी तरह आगे बढ़ता जाता है।
सबसे पहले, आप स्टार्टिंग वर्टेक्स को “जलाना” शुरू करते हैं। फिर आग उसके सभी पड़ोसी वर्टेक्स तक पहुँचती है। एक मिनट बाद, उन पड़ोसियों के पड़ोसियों में आग फैलने लगती है, फिर उनसे जुड़े हुए वर्टेक्स तक आग पहुँचती है, और यह प्रक्रिया तब तक चलती रहती है जब तक कि कोई वर्टेक्स बाकी नहीं बचता। ग्राफ़ को इस तरह जलता हुआ देखने की मानसिक छवि BFS एल्गोरिथ्म को लागू करने में बहुत मददगार हो सकती है।
BFS एल्गोरिथ्म को लागू करने का एक साधारण तरीका है एक
queue (पंक्ति) का उपयोग करना और एक लिस्ट रखना जो उन वर्टेक्स को ट्रैक करती है जो पहले से “यूज़्ड” (जले हुए या विज़िट किए जा चुके) हैं:from collections import deque
n, e = map(int, input().split()) # n: vertices (शिखर), e: edges (धाराएं)
g = [[] for _ in range(n)] # ग्राफ़ - adjacency list
for _ in range(e): # एज पढ़ें
a, b = map(int, input().split()) # a -> b और b -> a
g[a].append(b)
g[b].append(a)
start = int(input()) # शुरुआती वर्टेक्स
used = [False] * n # पहले से इस्तेमाल/विज़िट किए गए वर्टेक्स की सूची
q = deque([start]) # वर्टेक्स की queue
used[start] = True # शुरुआती वर्टेक्स को विज़िट किया चिह्नित करें
while q: # जब तक queue ख़ाली न हो
v = q.popleft() # queue से वर्टेक्स निकालें
print(v, end=' ') # वर्टेक्स को प्रिंट करें
for to in g[v]: # v से जुड़े हर वर्टेक्स के लिए
if not used[to]: # अगर वह वर्टेक्स अभी विज़िट नहीं हुआ है
q.append(to) # उसे queue में डालें
used[to] = True # और विज़िट किया हुआ चिह्नित करेंयहाँ सबसे पहले हम ग्राफ़ को इनिशियलाइज़ करते हैं और फिर
start वर्टेक्स से ग्राफ़ का ट्रवर्सल शुरू करते हैं। शुरू में, सभी used मान False सेट रहते हैं। जैसे-जैसे हम हर वर्टेक्स को विज़िट करते हैं, हम उसे queue में डालते हैं और “यूज़्ड” मार्क करते हैं। यह प्रक्रिया ग्राफ़ को “जलाने” जैसी स्थिति को दर्शाती है। हर स्टेप में, हम मौजूदा वर्टेक्स v से जुड़े हुए उन तमाम वर्टेक्स को queue में जोड़ते जाते हैं जो अभी तक यूज़्ड नहीं हुए, और उन्हें यूज़्ड के रूप में मार्क भी करते हैं।आइए कुछ इनपुट्स पर एल्गोरिथ्म को स्टेप-बाय-स्टेप देख लें:
n = 4, e = 4
इनपुट में दिए गए
a, b जोड़े इस प्रकार हैं: [(0, 1), (0, 2), (1, 2), (3, 2)]शुरुआती वर्टेक्स 3 है
used = [False, False, False, True],q = [3]
v = 3,q = []→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
used = [False, False, True, True],q = [2]
v = 2,q = []→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
used = [True, True, True, True],q = [0, 1]
v = 0,q = [1]→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
v = 1,q = []→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
- पूर्ण
n = 5, e = 4
इनपुट में दिए गए
a, b जोड़े इस प्रकार हैं: [(0, 1), (0, 2), (1, 2), (3, 4)]शुरुआती वर्टेक्स 0 है
used = [True, False, False, False, False],q = [0]
v = 0,q = []→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
used = [True, True, True, False, False],q = [1, 2]
v = 1,q = [2]→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
v = 2,q = []→ ऐसे सभी पड़ोसी जिनकाusedअभी False है, उन्हें queue में जोड़ें
- पूर्ण
Notice how nodes 3 and 4 were never visited.
They were not connected to the initial node 0.
चुनौती: ग्राफ़ में कनेक्टेड कॉम्पोनेंट्स की संख्या निकालें
मान लीजिए आप एक बिना दिशा (undirected) वाले ग्राफ़ के साथ काम कर रहे हैं जिसमें
v वर्टेक्स और e एज हैं। आपको इस ग्राफ़ में कनेक्टेड कॉम्पोनेंट्स की संख्या निकालनी है। वर्टेक्स का एक सेट तब कनेक्टेड कॉम्पोनेंट कहलाता है जब उन वर्टेक्स के बीच किसी भी जोड़ी के लिए एक-दूसरे तक पहुँचना संभव हो।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
v (1 ≤ v ≤ 100 000) और e (1 ≤ e ≤ 100 000) होते हैं।अगली
e पंक्तियों में प्रत्येक में दो पूर्णांक v1, v2 (1 ≤ v1, v2 ≤ v) दिए होते हैं, जिनका अर्थ है कि वर्टेक्स v1 वर्टेक्स v2 से कनेक्टेड है और vice versa.आउटपुट
प्रोग्राम को ग्राफ़ में मौजूद कनेक्टेड कॉम्पोनेंट्स की संख्या प्रिंट करनी चाहिए।
उदाहरण
इनपुट | आउटपुट |
7 6
1 2
2 3
1 3
4 5
5 6
4 6 | 3 |
2 1
1 2 | 1 |
2 0 | 2 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB