BFS สำหรับ Disconnected Graph


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน Hulu การัต ไมโครซอฟท์ Salesforce
การค้นหาครั้งแรกที่กว้าง กราฟ กราฟ Traversal

คำชี้แจงปัญหา

ปัญหา“ BFS for Disconnected Graph” ระบุว่าคุณได้รับกราฟที่ถูกตัดการเชื่อมต่อพิมพ์การส่งผ่าน BFS ของกราฟ

ตัวอย่าง

BFS สำหรับ Disconnected Graph

การข้ามผ่าน BFS ของกราฟด้านบนให้: 0 1 2 5 3 4 6

เข้าใกล้

การข้ามผ่านการค้นหาแรกกว้าง (BFS) สำหรับ Disconnected Directed Graph นั้นแตกต่างกันเล็กน้อย การส่งผ่าน BFS สำหรับกราฟที่ไม่ได้บอกทิศทางที่เชื่อมต่อ ในกราฟที่ไม่มีทิศทางที่เชื่อมต่อเราจะเริ่มการส่งผ่านจากโหนดต้นทางใด ๆ S และมีการเยี่ยมชมเครือข่ายกราฟทั้งหมดในระหว่างการส่งผ่าน อย่างไรก็ตามการข้ามผ่าน BFS สำหรับ Disconnected Directed Graph เกี่ยวข้องกับการเยี่ยมชมแต่ละโหนดที่ไม่ได้เยี่ยมชมและดำเนินการข้ามผ่าน BFS โดยเริ่มจากโหนดนั้น เรายุติการข้ามผ่านเมื่อพบว่ามีการเยี่ยมชมโหนดทั้งหมดแล้ว

 

พิจารณากราฟที่ไม่ได้บอกทิศทางที่เชื่อมต่อที่ระบุด้านล่างการเริ่มการส่งผ่าน BFS จากโหนดใด ๆ ของกราฟจะไปที่โหนดทั้งหมดในกราฟใน ไปครั้งเดียว.

BFS สำหรับ Disconnected Graph

พิจารณากราฟที่เชื่อมต่อที่กำหนดทิศทางด้านล่างซึ่งเห็นได้ชัดจากภาพในการเยี่ยมชมโหนดทั้งหมดในกราฟจำเป็นต้องทำการส่งผ่าน BFS ซ้ำ ๆ จากโหนด 0, 1, 3.

BFS สำหรับ Disconnected Graph

ขั้นตอนวิธี

  1. พิจารณามี V โหนดในกราฟที่กำหนด
  2. วนซ้ำแต่ละโหนดจาก 0 ถึง V และมองหาโหนดที่ไม่ได้เยี่ยมชมที่ 1
  3. เริ่มต้นการข้ามผ่าน BFS โดยเริ่มจากโหนดนี้และทำเครื่องหมายโหนดทั้งหมดที่ข้ามผ่านในภายหลังเมื่อเข้าเยี่ยมชม
  4. สิ้นสุดเมื่อเข้าชมโหนดทั้งหมดในกราฟแล้ว

รหัส

โปรแกรม C ++ สำหรับ BFS สำหรับ Disconnected Graph

#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 สำหรับ Disconnected Graph

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 = จำนวนขอบ