डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Hulu खरात माइक्रोसॉफ्ट Salesforce
पहले चौड़ाई खोजो ग्राफ ग्राफ ट्रैवर्सल

समस्या का विवरण

समस्या "डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS" बताती है कि आपको डिस्कनेक्ट किया गया ग्राफ़ दिया गया है, ग्राफ़ के BFS ट्रैवर्सल को प्रिंट करें।

उदाहरण

डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS

ऊपर दिए गए ग्राफ का बीएफएस ट्रावेलर देता है: 0 1 2 5 3 4 6 XNUMX

दृष्टिकोण

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

 

नीचे दिए गए जुड़े अप्रत्यक्ष ग्राफ पर विचार करें, ग्राफ़ के किसी भी नोड से बीएफएस ट्रैवर्सल शुरू करते हुए ग्राफ़ में सभी नोड्स पर जाएँ एकगया.

डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS

नीचे दिए गए जुड़े हुए ग्राफ पर विचार करें, क्योंकि यह छवि से स्पष्ट है, ग्राफ़ के सभी नोड्स पर जाने के लिए, बार-बार नोड से बीएफएस ट्रैवर्सल करने की आवश्यकता होती है 0, 1, 3.

डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS

कलन विधि

  1. गौर कीजिए, हैं V दिए गए ग्राफ में नोड्स।
  2. प्रत्येक नोड के माध्यम से 0 से V तक Iterate करें और पहली बार देखे गए नोड के लिए देखें।
  3. इस नोड से शुरू होने वाले बीएफएस ट्रैवर्सल को शुरू करें और बाद में देखे गए सभी नोड्स को चिह्नित करें।
  4. एक बार ग्राफ में सभी नोड्स का दौरा करने के बाद समाप्त करें।

कोड

डिस्कनेक्ट किए गए ग्राफ़ के लिए BFS के लिए C ++ प्रोग्राम

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
}

// BFS traversal function
void BFS(vector <int> graph[], int n)
{
    // vector to mark nodes as visited
    vector <bool> vis(n,false);
    
    // Process each node from 0 to n-1
    for(int i=0;i<n;i++)
    {
        // If not visited node is found
        if(vis[i] == false)
        {
            // BFS queue
            queue <int> q;
            // add not visited node to queue
            q.push(i);
            
            // BFS traversal
            while(!q.empty())
            {
                int front = q.front();
                q.pop();
                
                cout<<front<<" ";
                
                vis[front] = true;
                
                for(auto node : graph[front])
                {
                    if(vis[node] == false)
                    q.push(node);
                }
            }
        }
    }
    
    cout<<endl;
}

int main()
{
    // Construct the graph
    int n = 7;
    vector <int> graph[n];
    vector<pair<int,int>> edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
    
    for(auto e : edges)
    addEdge(graph,e.first,e.second);
    
    // Display the BFS traversal
    cout<<"BFS traversal of the given graph : ";
    BFS(graph,n);
    
    return 0;
}
BFS traversal of the given graph : 0 1 2 5 3 4 6

डिस्कनेक्टेड ग्राफ़ के लिए BFS के लिए जावा प्रोग्राम

import java.util.*;
import java.io.*;

class TutorialCup
{
    // Add Edge from node u to v
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
    }
    
    // BFS traversal function
    static void BFS(ArrayList<ArrayList<Integer>> graph, int n)
    {
        // array to mark nodes as visited
        boolean [] vis = new boolean[n];
        
        // Process each node from 0 to n-1
        for(int i=0;i<n;i++)
        {
            // If not visited node is found
            if(vis[i] == false)
            {
                // BFS queue
                Queue <Integer> q = new LinkedList<>();
                // add not visited node to queue
                q.add(i);
                
                // BFS traversal
                while(!q.isEmpty())
                {
                    int front = q.poll();
                    
                    System.out.print(front+" ");
                    
                    vis[front] = true;
                    
                    Iterator itr = graph.get(front).iterator();
                    while(itr.hasNext())
                    {
                        int node = (Integer)itr.next();
                        if(vis[node] == false)
                        q.add(node);
                        
                    }
                }
            }
        }
        
        System.out.println();
    }
    
    public static void main (String[] args) 
    {
        // Construct the graph
        int n = 7;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<n;i++)
        graph.add(new ArrayList<Integer>());
        
        int [][] edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
        for(int i=0;i<edges.length;i++)
        addEdge(graph,edges[i][0],edges[i][1]);
        
        // Display the BFS traversal
        System.out.print("BFS traversal of the given graph : ");
        BFS(graph,n);
    }
}
BFS traversal of the given graph : 0 1 2 5 3 4 6

जटिलता विश्लेषण

  1. समय जटिलता: T (n) = O (V + E)
  2. अंतरिक्ष जटिलता: ए (एन) = ओ (वी)

क्योंकि हम अपने अंतरिक्ष जटिलता का उपयोग कर रहे हैं रैखिक हो जाता है। तो एल्गोरिथ्म अंतरिक्ष में रैखिक हो जाता है। और समय जटिलता के लिए जैसा कि हमने ग्राफ में सभी नोड्स का दौरा किया है। एल्गोरिथ्म रैखिक समय भी लेता है।

V = नोड्स की संख्या।

ई = किनारों की संख्या।