БФС за неповезани граф


Ниво тешкоће Лако
Често питани у амазонка Хулу карат мицрософт Салесфорце
Претрага у ширину Графикон Графички прелазак

Изјава о проблему

Проблем „БФС за неповезани граф“ наводи да сте добили одвојени усмерени граф, одштампајте БФС обилазак графа.

Пример

БФС за неповезани граф

БФС прелазак горњег графикона даје: 0 1 2 5 3 4 6

Приступ

Прелазак ширине првог претраживања (БФС) за неповезани усмерени графикон се мало разликује од БФС прелазак за Повезани неусмерени граф. У повезаном неусмереном графу започињемо прелазак са било ког изворног чвора S а током преласка посећује се комплетна мрежа графикона. Међутим, БФС прелазак за Дисцоннецтед Дирецтед Грапх укључује посећивање сваког од непосећених чворова и извођење БФС преласка почев од тог чвора. Преокрет прекидамо након што утврдимо да су сви чворови посећени.

 

Узмите у обзир повезани неусмерени граф дат у наставку, започињање БФС преласка из било ког чвора графикона посетило би све чворове у графу у један потез.

БФС за неповезани граф

Размотрите доле усмерени повезани граф, као што је видљиво са слике, да бисте посетили све чворове на графикону, потребно је више пута извршити БФС обилажење са чворова КСНУМКС, КСНУМКС, КСНУМКС.

БФС за неповезани граф

Алгоритам

  1. Размислите, постоје V чворови у датом графикону.
  2. Прелистајте сваки чвор од 0 до В и потражите 1. чвор који нисте посетили.
  3. Започните БФС прелазак почев од овог чвора и означите све чворове који су накнадно пређени као посећени.
  4. Прекини се након што су посећени сви чворови на графикону.

код

Ц ++ програм за БФС за неповезани граф

#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

Јава програм за БФС за неповезани граф

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. Сложеност времена: Т (н) = О (В + Е)
  2. Сложеност простора: А (н) = О (В)

Зато што користимо нашу свемирску сложеност постаје линеарна. Дакле, алгоритам постаје линеарни у простору. И због сложености времена, јер смо обишли све чворове на графикону. Алгоритам узима и линеарно време.

В = број чворова.

Е = број ивица.