विच्छेद गरिएको ग्राफको लागि BFS


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन Hulu karat माइक्रोसफ्ट SalesForce
चौड़ाई पहिलो खोजी ग्राफ ग्राफ Traversal

समस्या वक्तव्य

समस्या "विच्छेद गरिएको ग्राफको लागि BFS" बताउँछ कि तपाईंलाई एक विच्छेदित निर्देशित ग्राफ दिइन्छ, ग्राफको BFS traversal प्रिन्ट गर्नुहोस्।

उदाहरणका

विच्छेद गरिएको ग्राफको लागि BFS

माथिको ग्राफको BFS traversal दिन्छ: ० १ १ २ 0 1 2।

दृष्टिकोण

विच्छेदन निर्देशित ग्राफको लागि चौडाई पहिलो खोजी (BFS) ट्रभर्सल भन्दा अलि फरक छ BFS traversal जडित अज्ञात ग्राफको लागि। एक जडित अप्रसिद्ध ग्राफमा, हामी कुनै पनि स्रोत नोडबाट ट्राभर्सल शुरू गर्दछौं S र पूर्ण ग्राफ नेटवर्क traversal को दौरान भ्रमण गरीन्छ। जे होस्, विच्छेदन निर्देशित ग्राफको लागि BFS traversal ले भ्रमण नगरेको प्रत्येक भ्रमण गर्नु र Bode traversal प्रदर्शन गर्नु समावेश छ त्यो नोडबाटै। हामीले ट्राभर्सल टर्मिनल गरेपछि फेला पारे कि सबै नोडहरू भ्रमण गरिसकेका छन्।

 

तल दिईएको जड अज्ञात रेखाचित्रलाई विचार गर्नुहोस्, BFS traversal लाई ग्राफको कुनै नोडबाट शुरू गरीएको ग्राफमा सबै नोडहरू भेट्न जान्छ एक पटक.

विच्छेद गरिएको ग्राफको लागि BFS

तल निर्देशित जडित ग्राफलाई विचार गर्नुहोस्, जस्तो कि छविबाट स्पष्ट हुन्छ, ग्राफमा सबै नोडहरू भ्रमण गर्न, यो बारम्बार नोड्सबाट BFS traversal प्रदर्शन गर्न आवश्यक छ। 0, 1, 3.

विच्छेद गरिएको ग्राफको लागि BFS

अल्गोरिदम

  1. विचार गर्नुहोस्, त्यहाँ छन् V दिईएको ग्राफमा नोडहरू।
  2. ० देखि V सम्म प्रत्येक नोडको माध्यम बाट इटरेट गर्नुहोस् र पहिलो भ्रमण नगरिएको नोडको लागि हेर्नुहोस्।
  3. यस नोडबाट शुरू BFS ट्राभर्सल शुरू गर्नुहोस् र सबै नोडहरू मार्क गर्नुहोस् जुन पछि भ्रमण गरिएकोको रूपमा ट्रान्स्ड गरियो।
  4. ग्राफमा सबै नोडहरू भ्रमण गरिसकेपछि समाप्त गर्नुहोस्।

कोड

C ++ कार्यक्रम BFS को लागि विच्छेद गरिएको ग्राफको लागि

#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. ठाउँ जटिलता: A (n) = O (V)

किनभने हामीले हाम्रो अन्तरिक्ष जटिलता प्रयोग गरिरह्यौं रैखिक बन्छ। त्यसो भए एल्गोरिथ्म स्पेसमा रेखीय हुन्छ। र समय जटिलताको लागि हामीले ग्राफमा सबै नोडहरू भ्रमण गरेका छौं। एल्गोरिथ्म लिनर समय लिन्छ।

V = नोडहरूको संख्या।

E = किनारहरूको संख्या।