BFS עבור גרף מנותק


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית Hulu קראט מיקרוסופט Salesforce
רוחב החיפוש הראשון גרף חציית גרפים

הצהרת בעיה

הבעיה "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 (n) = O (V + E)
  2. מורכבות בחלל: A (n) = O (V)

מכיוון שהשתמשנו במורכבות החלל שלנו הופכת ליניארית. אז האלגוריתם הופך ליניארי במרחב. ולמורכבות הזמן כשביקרנו בכל הצמתים בגרף. האלגוריתם לוקח גם זמן ליניארי.

V = מספר הצמתים.

E = מספר הקצוות.