ડિસ્કનેક્ટેડ ગ્રાફ માટે બી.એફ.એસ.


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન Hulu કરાત માઈક્રોસોફ્ટ Salesforce
બ્રેડથ ફર્સ્ટ સર્ચ ગ્રાફ ગ્રાફ ટ્રversવર્સલ

સમસ્યા નિવેદન

સમસ્યા "બીએસએફ માટે ડિસ્કનેક્ટેડ ગ્રાફ" કહે છે કે તમને ડિસ્કનેક્ટેડ ડિરેક્ટર ગ્રાફ આપવામાં આવે છે, ગ્રાફના બીએફએસ ટ્રેવર્સલને છાપો.

ઉદાહરણ

ડિસ્કનેક્ટેડ ગ્રાફ માટે બી.એફ.એસ.

ઉપરોક્ત ગ્રાફની બી.એફ.એસ. ટ્રાવર્સલ આપે છે: 0 1 2 5 3 4 6

અભિગમ

ડિસ્કનેક્ટેડ ડાયરેક્ટેડ ગ્રાફ માટે બ્રેડથ ફર્સ્ટ સર્ચ (બીએફએસ) ટ્રાવર્સલથી થોડું અલગ છે બી.એફ.એસ.ની આડઅસર કનેક્ટેડ રીડાયરેક્ટ ગ્રાફ માટે. કનેક્ટેડ રીડાયરેક્ટ કરેલા ગ્રાફમાં, અમે કોઈપણ સ્રોત નોડથી ટ્ર traવર્સલ શરૂ કરીએ છીએ S અને સંપૂર્ણ ગ્રાફ નેટવર્કની મુલાકાત ટ્રેવર્સલ દરમિયાન કરવામાં આવે છે. જો કે, ડિસ્કનેક્ટેડ ડાયરેક્ટેડ ગ્રાફ માટેના બીએફએસ ટ્રાવેસર્લમાં, મુલાકાત લીધેલા નોડ્સમાંથી દરેકની મુલાકાત લેવી અને તે નોડથી શરૂ થતાં બીએફએસ ટ્રાવર્સલનો સમાવેશ થાય છે. એકવાર અમને જોવા મળે છે કે બધા ગાંઠોની મુલાકાત લેવામાં આવી છે.

 

નીચે આપેલ કનેક્ટેડ રીડાયરેક્ટ ગ્રાફને ધ્યાનમાં લો, ગ્રાફના કોઈપણ નોડથી બીએફએસ ટ્રાવર્સલ શરૂ કરવાથી આલેખમાંના બધા ગાંઠોની મુલાકાત લેશે એક જાઓ.

ડિસ્કનેક્ટેડ ગ્રાફ માટે બી.એફ.એસ.

નીચે નિર્દેશિત કનેક્ટેડ ગ્રાફને ધ્યાનમાં લો, કારણ કે તે ચિત્રમાંથી સ્પષ્ટ થાય છે, ગ્રાફમાંના બધા ગાંઠોની મુલાકાત લેવા માટે, વારંવાર ગાંઠોથી બીએફએસ ટ્ર traવર્સલ કરવાની જરૂર છે. 0, 1, 3.

ડિસ્કનેક્ટેડ ગ્રાફ માટે બી.એફ.એસ.

અલ્ગોરિધમ

  1. ધ્યાનમાં લો, ત્યાં છે V આપેલ ગ્રાફમાં ગાંઠો.
  2. 0 થી V સુધીના દરેક નોડમાં ભરો અને 1 લી ન મુલાકાત લીધેલ નોડ શોધો.
  3. આ નોડથી શરૂ થતું બીએફએસ ટ્ર traવર્સલ શરૂ કરો અને ત્યારબાદ મુલાકાત લીધેલા બધા ગાંઠોને માર્ક કરો.
  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. અવકાશ જટિલતા: એ (એન) = ઓ (વી)

કારણ કે આપણે આપણી સ્પેસ જટિલતાનો ઉપયોગ કરી રહ્યા છીએ તે રેખીય બને છે. તેથી અલ્ગોરિધમનો અવકાશમાં રેખીય બને છે. અને સમય જટિલતા માટે કારણ કે આપણે આલેખમાંના બધા ગાંઠોની મુલાકાત લીધી છે. એલ્ગોરિધમનો પણ રેખીય સમય લે છે.

વી = ગાંઠોની સંખ્યા.

ઇ = ધારની સંખ્યા.