डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएस


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन Hulu करात मायक्रोसॉफ्ट सेल्सबॉल्स
रुंदी प्रथम शोध आलेख ग्राफ ट्रॅव्हर्सल

समस्या विधान

"डिस्कनेक्ट केलेल्या आलेखासाठी बीएफएस" समस्या असे सांगते की आपल्याला डिस्कनेक्ट केलेला निर्देशित आलेख देण्यात आला आहे, ग्राफचा बीएफएस ट्रव्हर्सल प्रिंट करा.

उदाहरण

डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएस

उपरोक्त आलेखाचा बीएफएस ट्रव्हर्सल देतो: 0 1 2 5 3 4 6

दृष्टीकोन

डिस्कनेक्ट डायरेक्ट आलेखसाठी ब्रेडथ फर्स्ट सर्च (बीएफएस) ट्रॅव्हर्सल यापेक्षा किंचित वेगळे आहे बीएफएस आडवे कनेक्ट न केलेले पुनर्निर्देशित आलेख कनेक्ट केलेल्या रीडायरेक्ट आलेखमध्ये आम्ही कोणत्याही सोर्स नोडवरून ट्रॅव्हर्सल सुरू करतो S आणि संपूर्ण ग्राफ नेटवर्क ट्रॅव्हर्सल दरम्यान भेट दिली जाते. तथापि, डिस्कनेक्ट डायरेक्टर्ड आलेखसाठी बीएफएस ट्रॅव्हर्सलमध्ये न भेटलेल्या प्रत्येक नोडला भेट देणे आणि त्या नोडपासून प्रारंभ होणारे बीएफएस ट्रॅव्हर्सल करणे समाविष्ट आहे. एकदा आम्हाला आढळले की सर्व नोड्सना भेट दिली गेली आहे.

 

खाली दिलेल्या कनेक्ट केलेल्या पुनर्निर्देशित ग्राफचा विचार करा, आलेखाच्या कोणत्याही नोडपासून बीएफएस ट्रॅव्हर्सल सुरू केल्याने ग्राफमधील सर्व नोड्सना भेट दिली जाईल एक जा.

डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएस

खाली निर्देशित कनेक्ट केलेला आलेख विचारात घ्या, जसे प्रतिमेवरून स्पष्ट आहे, आलेखामधील सर्व नोड्सना भेट देण्यासाठी, नोड्समधून वारंवार बीएफएस ट्रॅव्हर्सल करणे आवश्यक आहे. 0, 1, 3.

डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएस

अल्गोरिदम

  1. विचार करा, आहेत V दिलेल्या आलेखामध्ये नोड्स.
  2. 0 ते V पर्यंतच्या प्रत्येक नोडमध्ये जा आणि 1 ला भेट दिलेल्या नोडसाठी शोधा.
  3. या नोडपासून प्रारंभ होणारा बीएफएस ट्रॅव्हर्सल सुरू करा आणि त्यानंतर भेट दिलेल्या प्रमाणे सर्व नोड चिन्हांकित करा.
  4. एकदा आलेखमधील सर्व नोड्स भेट दिल्यानंतर समाप्त करा.

कोड

डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएससाठी सी ++ प्रोग्राम

#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

डिस्कनेक्ट केलेल्या आलेखसाठी बीएफएससाठी जावा प्रोग्राम

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. वेळ कॉम्प्लेक्सिटी: टी (एन) = ओ (व्ही + ई)
  2. स्पेस कॉम्प्लेक्सिटी: ए (एन) = ओ (व्ही)

कारण आपण आपली जागा वापरत आहोत जटिलता रेखीय होते. तर अल्गोरिदम अवकाशात रेषात्मक होते. आणि वेळेच्या जटिलतेसाठी कारण जसे आम्ही आलेखमधील सर्व नोड्सना भेट दिली आहे. अल्गोरिदमला रेषीय वेळही लागतो.

व्ही = नोड्सची संख्या.

ई = कडा संख्या.