Салгасан графикийн BFS


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Hulu Karat Microsoft- Борлуулалтын хүч
Өргөн уудам хайлт График Графикийн хөндлөн огтлол

Асуудлын мэдэгдэл

"BFS for Disconnected Graph" гэсэн асуудалд танд салгасан чиглэлийн графикийг өгч, графикийн 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 хүртэлх цэг бүрийг давтаж, 1-р очоогүй цэгийг хайж олох.
  3. Энэ цэгээс эхлэн BFS дамжуулалтыг эхлүүлээд дараа нь дамжсан бүх зангилааг зочилсон байдлаар тэмдэглэ.
  4. График дээрх бүх цэгүүд зочилсны дараа дуусгавар болно.

код

Таслагдсан графикийн BFS-д зориулсан C ++ програм

#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-д зориулсан Java програм

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 = ирмэгийн тоо.