BFS برای نمودار قطع شده


سطح دشواری ساده
اغلب در آمازون Hulu به عیار مایکروسافت Salesforce
عرض اول جستجو گراف پیمایش نمودار

بیان مسأله

مسئله "BFS برای نمودار جدا شده" بیان می کند که به شما یک نمودار کارگردانی قطع شده داده می شود ، مسیر BFS نمودار را چاپ کنید.

مثال

BFS برای نمودار قطع شده

عرض BFS نمودار بالا: 0 1 2 5 3 4 6 را نشان می دهد

روش

پیمایش پیمای اول جستجوی عرض (BFS) برای نمودار کارگردان جداشده کمی متفاوت است پیمایش BFS برای نمودار بدون جهت متصل شده است. در یک نمودار بدون جهت متصل ، عبور از هر گره منبع را شروع می کنیم S و از شبکه نمودار کامل در طول پیمایش بازدید می شود. با این حال ، پیمایش BFS برای نمودار Directed Disconnected Directed شامل بازدید از هر یک از گره های بازدید نشده و انجام پیمایش BFS با شروع از آن گره است. وقتی متوجه شدیم همه گره ها بازدید شده اند ، ما مسیر عبور را خاتمه می دهیم.

 

نمودار غیر مستقیم جهت داده شده در زیر را در نظر بگیرید ، شروع پیمایش BFS از هر گره از نمودار ، از همه گره های نمودار موجود در نمودار بازدید می کند یک بروید.

BFS برای نمودار قطع شده

نمودار متصل مستقیم را در نظر بگیرید ، همانطور که از تصویر مشخص است ، برای بازدید از همه گره های نمودار ، برای انجام مکرر پیمایش BFS از گره ها لازم است 0، 1، 3.

BFS برای نمودار قطع شده

الگوریتم

  1. در نظر بگیرید ، وجود دارد V گره ها در نمودار داده شده.
  2. از هر گره از 0 تا V تکرار کنید و به دنبال گره 1 بازدید نشده بروید.
  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 = تعداد لبه ها.