algorithm
पहले चौड़ाई खोजो
खोज…
स्रोत से अन्य नोड्स के लिए सबसे छोटा रास्ता खोजना
चौड़ाई-पहली-खोज (बीएफएस) पेड़ या ग्राफ डेटा संरचनाओं को खोजने या खोजने के लिए एक एल्गोरिथ्म है। यह ट्री रूट पर शुरू होता है (या ग्राफ के कुछ मनमाने ढंग से नोड, कभी-कभी 'खोज कुंजी' के रूप में संदर्भित होता है) और अगले स्तर के पड़ोसियों के पास जाने से पहले पड़ोसी नोड्स की खोज करता है। बीएफएस का आविष्कार 1950 के दशक के अंत में एडवर्ड फॉरेस्ट मूर द्वारा किया गया था, जिन्होंने इसका इस्तेमाल एक भूलभुलैया से सबसे छोटे रास्ते को खोजने के लिए किया था और 1961 में CY ली द्वारा वायर रूटिंग एल्गोरिथम के रूप में स्वतंत्र रूप से खोजा था।
बीएफएस एल्गोरिथ्म की प्रक्रियाएं इन मान्यताओं के तहत काम करती हैं:
- हम किसी भी नोड को एक से अधिक बार पार नहीं करेंगे।
- स्रोत नोड या हम जिस नोड से शुरू कर रहे हैं वह स्तर 0 में स्थित है।
- नोड्स हम सीधे स्रोत नोड से पहुंच सकते हैं स्तर 1 नोड्स हैं, नोड्स हम सीधे स्तर 1 नोड्स से पहुंच सकते हैं स्तर 2 नोड्स और इतने पर हैं।
- स्तर स्रोत से सबसे छोटे मार्ग की दूरी को दर्शाता है।
आइए एक उदाहरण देखें: 
मान लें कि यह ग्राफ कई शहरों के बीच संबंध का प्रतिनिधित्व करता है, जहां प्रत्येक नोड एक शहर को दर्शाता है और दो नोड्स के बीच एक किनारे को दर्शाता है कि वहां एक सड़क लिंक है। हम नोड 1 से नोड 10 तक जाना चाहते हैं। तो नोड 1 हमारा स्रोत है , जो कि स्तर 0 है । हम नोड 1 पर जाते हैं। हम यहां से नोड 2 , नोड 3 और नोड 4 पर जा सकते हैं। तो वे स्तर (0 + 1) = स्तर 1 नोड होंगे। अब हम उन्हें दौरा करेंगे और उनके साथ काम करेंगे।
रंगीन नोड्स का दौरा किया जाता है। वर्तमान में हम जिन नोड्स के साथ काम कर रहे हैं, उन्हें गुलाबी रंग से चिह्नित किया जाएगा। हम एक ही नोड पर दो बार नहीं जाएंगे। नोड 2 , नोड 3 और नोड 4 से , हम नोड 6, नोड 7 और नोड 8 पर जा सकते हैं। आइए उन्हें चिह्नित करें। इन नोड्स का स्तर स्तर (1 + 1) = स्तर 2 होगा । 
यदि आपने ध्यान नहीं दिया है, तो नोड्स का स्तर केवल स्रोत से सबसे छोटी पथ दूरी को दर्शाता है। उदाहरण के लिए: हमने स्तर 2 पर नोड 8 पाया है । इसलिए स्रोत से नोड 8 की दूरी 2 है ।
हम अभी तक अपने लक्ष्य नोड तक नहीं पहुंचे हैं, यह नोड 10 है । तो चलो अगले नोड्स पर जाएँ। हम सीधे नोड 6 , नोड 7 और नोड 8 से जा सकते हैं । 
हम देख सकते हैं कि, हमने 3 स्तर पर नोड 10 पाया। इसलिए स्रोत से नोड 10 तक का सबसे छोटा रास्ता है । हमने ग्राफ स्तर को स्तर से खोजा और सबसे छोटा रास्ता पाया। अब उन किनारों को मिटा दें जिनका हमने उपयोग नहीं किया था: 
उन किनारों को हटाने के बाद जिनका हमने उपयोग नहीं किया, हमें एक पेड़ मिलता है जिसे बीएफएस पेड़ कहा जाता है। यह पेड़ स्रोत से अन्य सभी नोड्स के लिए सबसे छोटा रास्ता दिखाता है।
तो हमारा काम होगा, स्रोत से स्तर 1 नोड तक जाना। तब स्तर 1 से स्तर 2 नोड्स तक और इसी तरह जब तक हम अपने गंतव्य तक नहीं पहुंच जाते। हम उन नोड्स को संग्रहीत करने के लिए कतार का उपयोग कर सकते हैं जिन्हें हम संसाधित करने जा रहे हैं। यही है, हम जिस नोड के साथ काम करने जा रहे हैं, उसके लिए हम अन्य सभी नोड्स को धक्का देंगे, जिन्हें सीधे ट्रैवर्स किया जा सकता है और अभी तक कतार में नहीं लगाया गया है।
हमारे उदाहरण का अनुकरण:
पहले हम स्रोत को कतार में धकेलते हैं। हमारी कतार दिखेगी:
front
+-----+
| 1 |
+-----+
नोड 1 का स्तर 0. स्तर [1] = 0 होगा । अब हम अपना बीएफएस शुरू करते हैं। सबसे पहले, हम अपनी कतार से एक नोड पॉप करते हैं। हमें नोड 1 मिलता है । हम इस से नोड 4 , नोड 3 और नोड 2 पर जा सकते हैं। हम नोड 1 से इन नोड्स तक पहुँच चुके हैं। तो स्तर [४] = स्तर [३] = स्तर [२] = स्तर [१] + १ = १ । अब हम उन्हें दौरे के रूप में चिह्नित करते हैं और उन्हें कतार में धकेलते हैं।
front
+-----+ +-----+ +-----+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
अब हम नोड 4 को पॉप करते हैं और इसके साथ काम करते हैं। हम नोड 4 से नोड 7 पर जा सकते हैं। स्तर [2] = स्तर [४] + १ = २ । हम नोड 7 को विज़िट के रूप में चिह्नित करते हैं और इसे कतार में धकेलते हैं।
front
+-----+ +-----+ +-----+
| 7 | | 2 | | 3 |
+-----+ +-----+ +-----+
नोड 3 से , हम नोड 7 और नोड 8 पर जा सकते हैं। चूंकि हमने पहले ही नोड 7 को विज़िट के रूप में चिह्नित किया है, हम नोड 8 को चिह्नित करते हैं, हम स्तर [8] = स्तर [3] + 1 = 2 बदलते हैं। हम कतार में नोड 8 को धक्का देते हैं।
front
+-----+ +-----+ +-----+
| 6 | | 7 | | 2 |
+-----+ +-----+ +-----+
यह प्रक्रिया तब तक जारी रहेगी जब तक हम अपने गंतव्य तक नहीं पहुँच जाते या कतार खाली नहीं हो जाती। स्तर सरणी हमें स्रोत से सबसे छोटी पथ की दूरी प्रदान करेगी। हम इन्फिनिटी मान के साथ स्तर सरणी को इनिशियलाइज़ कर सकते हैं, जो यह चिन्हित करेगा कि नोड्स का अभी तक दौरा नहीं किया गया है। हमारा छद्म कोड होगा:
Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
u -> Q.pop()
for all edges from u to v in Adjacency list
if level[v] == infinity
level[v] := level[u] + 1
Q.push(v)
end if
end for
end while
Return level
स्तर सरणी के माध्यम से पुनरावृत्ति करके, हम स्रोत से प्रत्येक नोड की दूरी का पता लगा सकते हैं। उदाहरण के लिए: स्रोत से नोड 10 की दूरी को स्तर [10] में संग्रहीत किया जाएगा।
कभी-कभी हमें न केवल सबसे छोटी दूरी, बल्कि उस पथ को भी प्रिंट करने की आवश्यकता हो सकती है जिसके माध्यम से हम स्रोत से अपने नियत नोड तक जा सकते हैं। इसके लिए हमें एक पेरेंट ऐरे रखना होगा। मूल [स्रोत] NULL होगा। स्तर सरणी में प्रत्येक अद्यतन के लिए, हम केवल लूप के लिए हमारे छद्म कोड में parent[v] := u जोड़ेंगे। बीएफएस खत्म करने के बाद, रास्ता खोजने के लिए, हम मूल सरणी को वापस लाएँगे, जब तक कि हम स्रोत तक नहीं पहुँच जाते हैं, जिसे NULL मान द्वारा निरूपित किया जाएगा। छद्म कोड होगा:
Procedure PrintPath(u): //recursive | Procedure PrintPath(u): //iterative
if parent[u] is not equal to null | S = Stack()
PrintPath(parent[u]) | while parent[u] is not equal to null
end if | S.push(u)
print -> u | u := parent[u]
| end while
| while S is not empty
| print -> S.pop
| end while
जटिलता:
हमने एक बार और प्रत्येक किनारों पर एक बार प्रत्येक नोड का दौरा किया है। तो जटिलता ओ (वी + ई) होगी जहां वी नोड्स की संख्या है और ई किनारों की संख्या है।
एक 2 डी ग्राफ में स्रोत से सबसे छोटा रास्ता खोजना
अधिकांश समय, हमें एकल स्रोत से अन्य सभी नोड्स या 2 डी ग्राफ़ में एक विशिष्ट नोड के लिए सबसे छोटा रास्ता खोजने की आवश्यकता होगी। उदाहरण के लिए कहें: हम यह पता लगाना चाहते हैं कि शूरवीरता में एक निश्चित वर्ग तक पहुँचने के लिए शूरवीर को कितनी चालों की आवश्यकता होती है, या हमारे पास एक सरणी होती है जहाँ कुछ कोशिकाएँ अवरुद्ध हो जाती हैं, हमें एक कक्ष से दूसरे कक्ष तक के सबसे छोटे मार्ग का पता लगाना होता है। । हम केवल क्षैतिज और लंबवत रूप से आगे बढ़ सकते हैं। यहां तक कि विकर्ण चाल भी संभव हो सकती है। इन मामलों के लिए, हम वर्गों या कोशिकाओं को नोड्स में परिवर्तित कर सकते हैं और BFS का उपयोग करके इन समस्याओं को आसानी से हल कर सकते हैं। अब हमारा दौरा , माता - पिता और स्तर 2 डी सरणियां होंगी। प्रत्येक नोड के लिए, हम सभी संभावित चालों पर विचार करेंगे। एक विशिष्ट नोड की दूरी का पता लगाने के लिए, हम यह भी जाँचेंगे कि क्या हम अपने गंतव्य तक पहुँच गए हैं।
दिशा सरणी नामक एक अतिरिक्त चीज होगी। यह केवल हमारे द्वारा जाने वाले निर्देशों के सभी संभावित संयोजनों को संग्रहीत करेगा। आइए बताते हैं, क्षैतिज और ऊर्ध्वाधर चाल के लिए, हमारी दिशा सरणियाँ होंगी:
+----+-----+-----+-----+-----+
| dx | 1 | -1 | 0 | 0 |
+----+-----+-----+-----+-----+
| dy | 0 | 0 | 1 | -1 |
+----+-----+-----+-----+-----+
यहाँ dx x- अक्ष में चाल का प्रतिनिधित्व करता है और डाई y- अक्ष में चाल का प्रतिनिधित्व करता है। फिर से यह हिस्सा वैकल्पिक है। आप सभी संभावित संयोजनों को अलग से भी लिख सकते हैं। लेकिन दिशा सरणी का उपयोग करके इसे संभालना आसान है। विकर्ण चाल या नाइट चाल के लिए और भी अधिक संयोजन हो सकते हैं।
हमें ध्यान में रखने की जरूरत है:
- यदि किसी भी सेल को अवरुद्ध किया जाता है, तो हर संभव चाल के लिए, हम जाँचेंगे कि सेल अवरुद्ध है या नहीं।
- यदि हम सीमा से बाहर चले गए हैं, तो हम यह भी जाँचेंगे कि हमने सरणी सीमाएँ पार कर ली हैं।
- पंक्तियों और स्तंभों की संख्या दी जाएगी।
हमारा छद्म कोड होगा:
Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
for j from 1 to column
visited[i][j] := false
end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
top := Q.pop
for i from 1 to m
temp.x := top.x + dx[i]
temp.y := top.y + dy[i]
if temp is inside the row and column and top doesn't equal to blocksign
visited[temp.x][temp.y] := true
level[temp.x][temp.y] := level[top.x][top.y] + 1
Q.push(temp)
end if
end for
end while
Return level
जैसा कि हमने पहले चर्चा की है, बीएफएस केवल अनवीटेड ग्राफ के लिए काम करता है। भारित रेखांकन के लिए, हमें दिक्जस्ट्रा के एल्गोरिथ्म की आवश्यकता होगी। नकारात्मक बढ़त चक्रों के लिए, हमें बेलमैन-फोर्ड के एल्गोरिथ्म की आवश्यकता है। फिर से यह एल्गोरिथ्म एकल स्रोत सबसे छोटा पथ एल्गोरिथम है। यदि हमें प्रत्येक नोड से अन्य सभी नोड्स की दूरी का पता लगाने की आवश्यकता है, तो हमें फ्लोयड-वारशॉल के एल्गोरिथ्म की आवश्यकता होगी।
BFS का उपयोग करके अप्रत्यक्ष ग्राफ़ के जुड़े घटक।
अप्रत्यक्ष ग्राफ के जुड़े घटकों को खोजने के लिए BFS का उपयोग किया जा सकता है। हम यह भी पा सकते हैं कि दिया गया ग्राफ जुड़ा हुआ है या नहीं। हमारी बाद की चर्चा मानती है कि हम अप्रत्यक्ष रेखांकन के साथ काम कर रहे हैं। एक जुड़े हुए ग्राफ की परिभाषा है:
यदि हर जोड़ी के बीच एक रास्ता है तो एक ग्राफ जुड़ा हुआ है।
निम्नलिखित एक जुड़ा हुआ ग्राफ है ।
निम्नलिखित ग्राफ जुड़ा नहीं है और 2 जुड़े घटक हैं:
- कनेक्टेड घटक 1: {ए, बी, सी, डी, ई}
- कनेक्टेड घटक 2: {f}
BFS एक ग्राफ ट्रैवर्सल एल्गोरिथम है। इसलिए एक यादृच्छिक स्रोत नोड से शुरू करके, यदि एल्गोरिथ्म की समाप्ति पर, सभी नोड्स का दौरा किया जाता है, तो ग्राफ जुड़ा हुआ है, अन्यथा यह जुड़ा नहीं है।
एल्गोरिथ्म के लिए छद्म कोड।
boolean isConnected(Graph g)
{
BFS(v)//v is a random source node.
if(allVisited(g))
{
return true;
}
else return false;
}
अप्रत्यक्ष ग्राफ जुड़ा हुआ है या नहीं, यह जानने के लिए सी कार्यान्वयन:
#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100
void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);
int count = 0;
//Queue node depicts a single Queue element
//It is NOT a graph node.
struct node
{
int v;
struct node *next;
};
typedef struct node Node;
typedef struct node *Nodeptr;
Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;//array that keeps track of visited vertices.
int main()
{
int n,e;//n is number of vertices, e is number of edges.
int i,j;
char **graph;//adjacency matrix
printf("Enter number of vertices:");
scanf("%d",&n);
if(n < 0 || n > MAXVERTICES)
{
fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
return -1;
}
graph = malloc(n * sizeof(char *));
visited = malloc(n*sizeof(char));
for(i = 0;i < n;++i)
{
graph[i] = malloc(n*sizeof(int));
visited[i] = 'N';//initially all vertices are not visited.
for(j = 0;j < n;++j)
graph[i][j] = 0;
}
printf("enter number of edges and then enter them in pairs:");
scanf("%d",&e);
for(i = 0;i < e;++i)
{
int u,v;
scanf("%d%d",&u,&v);
graph[u-1][v-1] = 1;
graph[v-1][u-1] = 1;
}
if(isConnected(graph,n))
printf("The graph is connected");
else printf("The graph is NOT connected\n");
}
void enqueue(int vertex)
{
if(Qfront == NULL)
{
Qfront = malloc(sizeof(Node));
Qfront->v = vertex;
Qfront->next = NULL;
Qrear = Qfront;
}
else
{
Nodeptr newNode = malloc(sizeof(Node));
newNode->v = vertex;
newNode->next = NULL;
Qrear->next = newNode;
Qrear = newNode;
}
}
int deque()
{
if(Qfront == NULL)
{
printf("Q is empty , returning -1\n");
return -1;
}
else
{
int v = Qfront->v;
Nodeptr temp= Qfront;
if(Qfront == Qrear)
{
Qfront = Qfront->next;
Qrear = NULL;
}
else
Qfront = Qfront->next;
free(temp);
return v;
}
}
int isConnected(char **graph,int noOfVertices)
{
int i;
//let random source vertex be vertex 0;
BFS(graph,0,noOfVertices);
for(i = 0;i < noOfVertices;++i)
if(visited[i] == 'N')
return 0;//0 implies false;
return 1;//1 implies true;
}
void BFS(char **graph,int v,int noOfVertices)
{
int i,vertex;
visited[v] = 'Y';
enqueue(v);
while((vertex = deque()) != -1)
{
for(i = 0;i < noOfVertices;++i)
if(graph[vertex][i] == 1 && visited[i] == 'N')
{
enqueue(i);
visited[i] = 'Y';
}
}
}
अप्रत्यक्ष ग्राफ के सभी जुड़े हुए घटकों को खोजने के लिए, हमें केवल BFS फ़ंक्शन में कोड की 2 पंक्तियों को जोड़ना होगा। बीएफएस फ़ंक्शन को कॉल करने के लिए विचार किया जाता है जब तक कि सभी कोने का दौरा नहीं किया जाता है।
जोड़ी जाने वाली लाइनें हैं:
printf("\nConnected component %d\n",++count);
//count is a global variable initialized to 0
//add this as first line to BFS function
तथा
printf("%d ",vertex+1);
add this as first line of while loop in BFS
और हम निम्नलिखित फ़ंक्शन को परिभाषित करते हैं:
void listConnectedComponents(char **graph,int noOfVertices)
{
int i;
for(i = 0;i < noOfVertices;++i)
{
if(visited[i] == 'N')
BFS(graph,i,noOfVertices);
}
}
