BFS للرسم البياني غير المتصل


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون هولو قيراط Microsoft ساليسفورسي
اتساع البحث الأول رسم بياني اجتياز الرسم البياني

المشكلة بيان

توضح مشكلة "BFS للرسم البياني غير المتصل" أنه يتم إعطاؤك رسمًا بيانيًا موجهًا غير متصل ، وطباعة مسح BFS للرسم البياني.

مثال

BFS للرسم البياني غير المتصل

يعطي اجتياز BFS للرسم البياني أعلاه: 0 1 2 5 3 4 6

الرسالة

يختلف اجتياز بحث النطاق الأول (BFS) للرسم البياني الموجه غير المتصل قليلاً عن اجتياز BFS للرسم البياني متصل غير موجه. في رسم بياني متصل غير موجه ، نبدأ المسح من أي عقدة مصدر S ويتم زيارة شبكة الرسم البياني الكاملة أثناء الاجتياز. ومع ذلك ، فإن اجتياز BFS للرسم البياني الموجه غير المتصل يتضمن زيارة كل من العقد التي لم تتم زيارتها وإجراء اجتياز BFS بدءًا من تلك العقدة. نقوم بإنهاء الاجتياز بمجرد أن نجد أن جميع العقد قد تمت زيارتها.

 

ضع في اعتبارك الرسم البياني غير المباشر المتصل الموضح أدناه ، فإن بدء اجتياز BFS من أي عقدة في الرسم البياني سيزور جميع العقد في الرسم البياني في مرة واحدة.

BFS للرسم البياني غير المتصل

ضع في اعتبارك الرسم البياني المتصل الموجه أدناه ، كما هو واضح من الصورة ، لزيارة جميع العقد في الرسم البياني ، يلزم إجراء مسح BFS بشكل متكرر من العقد 0، 1، 3.

BFS للرسم البياني غير المتصل

خوارزمية

  1. النظر ، هناك V العقد في الرسم البياني المحدد.
  2. كرر خلال كل عقدة من 0 إلى 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

برنامج Java لـ 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 (ن) = O (V + E)
  2. تعقيد الفضاء: A (n) = O (V)

لأننا كنا نستخدم تعقيد الفضاء لدينا يصبح خطيًا. لذلك تصبح الخوارزمية خطية في الفضاء. وللتعقيد الزمني حيث قمنا بزيارة جميع العقد في الرسم البياني. تستغرق الخوارزمية وقتًا خطيًا أيضًا.

V = عدد العقد.

E = عدد الحواف.