Rekurencyjne wykonywanie pierwszego przeszukiwania wszerz

Załóżmy, że chcesz zaimplementować rekurencyjne przeszukiwanie wszerz drzewa binarnego . Jak byś się do tego zabrał?

Czy jest możliwe używanie tylko stosu wywołań jako pamięci dyskowej?

(Zakładam, że to tylko jakieś ćwiczenie myślowe, a nawet podchwytliwe zadanie domowe / pytanie do rozmowy kwalifikacyjnej, ale przypuszczam, że mógłbym sobie wyobrazić jakiś dziwny scenariusz, w którym z jakiegoś powodu nie masz miejsca na sterty [jakiś naprawdę zły zwyczaj menadżer pamięci? jakieś dziwne problemy ze środowiskiem wykonawczym / systemem operacyjnym?], podczas gdy nadal masz dostęp do stosu ...)

Przechodzenie wszerz tradycyjnie używa kolejki, a nie stosu. Natura kolejki i stosu jest prawie przeciwna, więc próba użycia stosu wywołań (który jest stosem, stąd nazwa) jako pamięci dyskowej (kolejki) jest prawie skazana na niepowodzenie, chyba że robisz coś głupiego absurdalnego ze stosem wywołań, którym nie powinieneś być.

Z tego samego powodu naturą każdej rekursji innej niż ogon, którą próbujesz zaimplementować, jest zasadniczo dodanie stosu do algorytmu. To sprawia, że ​​pierwsze przeszukiwanie w drzewie binarnym nie jest już obszerne, a tym samym czas wykonywania i inne elementy tradycyjnego BFS nie mają już pełnego zastosowania. Oczywiście zawsze można w trywialny sposób przekształcić dowolną pętlę w wywołanie rekurencyjne, ale nie jest to żadna sensowna rekurencja.

Istnieją jednak sposoby, jak pokazali inni, aby zaimplementować coś, co jest zgodne z semantyką BFS za pewną cenę. Jeśli koszt porównania jest drogi, ale przemierzanie węzłów jest tanie, to tak jak zrobił to @Simon Buchan , możesz po prostu uruchomić iteracyjne przeszukiwanie w głąb, przetwarzając tylko liście. Oznaczałoby to brak rosnącej kolejki przechowywanej w stercie, tylko lokalną zmienną głębokości, a stosy są budowane w kółko na stosie wywołań, gdy drzewo jest przechodzone w kółko. I jak zauważył @Patrick , drzewo binarne wspierane przez tablicę jest zwykle przechowywane w kolejności przechodzenia wszerz, więc przeszukiwanie wszerz byłoby trywialne, również bez kolejki pomocniczej.

Jeśli używasz tablicy do tworzenia kopii zapasowej drzewa binarnego, możesz algebraicznie określić następny węzeł. jeśli ijest węzłem, to jego dzieci można znaleźć w 2i + 1(dla lewego węzła) i 2i + 2(dla prawego węzła). Następny sąsiad węzła jest określany przez i + 1, chyba że ijest to potęga2

Oto pseudokod dla bardzo naiwnej implementacji pierwszego przeszukiwania wszerz w binarnym drzewie wyszukiwania opartym na tablicy. Zakłada to tablicę o stałym rozmiarze, a zatem drzewo o stałej głębokości. Będzie patrzeć na węzły bez rodzica i może stworzyć niemożliwy do zarządzania duży stos.

bintree-bfs(bintree, elt, i)
    if (i == LENGTH)
        return false

    else if (bintree[i] == elt)
        return true

    else 
        return bintree-bfs(bintree, elt, i+1)        

Nie mogłem znaleźć sposobu, aby zrobić to całkowicie rekurencyjnie (bez żadnej pomocniczej struktury danych). Ale jeśli kolejka Q jest przekazywana przez referencję, możesz mieć następującą rekurencyjną funkcję głupiego ogona:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

W poniższej metodzie zastosowano algorytm DFS, aby uzyskać wszystkie węzły na określonej głębokości - co jest takie samo jak wykonanie BFS dla tego poziomu. Jeśli znajdziesz głębokość drzewa i zrobisz to na wszystkich poziomach, wyniki będą takie same jak w przypadku BFS.

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

Znalezienie głębokości drzewa to bułka z masłem:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

Prosta rekurencja BFS i DFS w Javie: po
prostu wypchnij / zaoferuj węzeł główny drzewa w stosie / kolejce i wywołaj te funkcje.

public static void breadthFirstSearch(Queue queue) {

    if (queue.isEmpty())
        return;

    Node node = (Node) queue.poll();

    System.out.println(node + " ");

    if (node.right != null)
        queue.offer(node.right);

    if (node.left != null)
        queue.offer(node.left);

    breadthFirstSearch(queue);
}

public static void depthFirstSearch(Stack stack) {

    if (stack.isEmpty())
        return;

    Node node = (Node) stack.pop();

    System.out.println(node + " ");

    if (node.right != null)
        stack.push(node.right);

    if (node.left != null)
        stack.push(node.left);

    depthFirstSearch(stack);
}

Znalazłem bardzo piękny, rekurencyjny (a nawet funkcjonalny) algorytm związany z przemierzaniem Breadth-First. Nie mój pomysł, ale myślę, że należy o tym wspomnieć w tym temacie.

Chris Okasaki bardzo wyraźnie wyjaśnia swój algorytm numeracji wszerz z ICFP 2000 pod adresem http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html za pomocą tylko 3 zdjęć.

Implementacja Debasish Ghosh w Scali, którą znalazłem pod adresem http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html , to:

trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]

def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
  if (trees.isEmpty) Queue.Empty
  else {
    trees.dequeue match {
      case (E, ts) =>
        bfsNumForest(i, ts).enqueue[Tree[Int]](E)
      case (Node(d, l, r), ts) =>
        val q = ts.enqueue(l, r)
        val qq = bfsNumForest(i+1, q)
        val (bb, qqq) = qq.dequeue
        val (aa, tss) = qqq.dequeue
        tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
    }
  }
}

def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
  val q = Queue.Empty.enqueue[Tree[T]](t)
  val qq = bfsNumForest(1, q)
  qq.dequeue._1
}

Głupi sposób:

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}

Oto krótkie rozwiązanie Scala :

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

Pomysł wykorzystania wartości zwracanej jako akumulatora jest dobrze dopasowany. Może być zaimplementowany w innych językach w podobny sposób, po prostu upewnij się, że Twoja rekurencyjna funkcja przetwarza listę węzłów .

Listing kodu testowego (przy użyciu drzewa testowego @marco):

import org.scalatest.FlatSpec

import scala.collection.mutable

class Node(val value: Int) {

  private val _children: mutable.ArrayBuffer[Node] = mutable.ArrayBuffer.empty

  def add(child: Node): Unit = _children += child

  def children = _children.toList

  override def toString: String = s"$value"
}

class BfsTestScala extends FlatSpec {

  //            1
  //          / | \
  //        2   3   4
  //      / |       | \
  //    5   6       7  8
  //  / |           | \
  // 9  10         11  12
  def tree(): Node = {
    val root = new Node(1)
    root.add(new Node(2))
    root.add(new Node(3))
    root.add(new Node(4))
    root.children(0).add(new Node(5))
    root.children(0).add(new Node(6))
    root.children(2).add(new Node(7))
    root.children(2).add(new Node(8))
    root.children(0).children(0).add(new Node(9))
    root.children(0).children(0).add(new Node(10))
    root.children(2).children(0).add(new Node(11))
    root.children(2).children(0).add(new Node(12))
    root
  }

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

  "BFS" should "work" in {
    println(bfs(List(tree())))
  }
}

Wynik:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Oto implementacja Pythona:

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

def bfs(paths, goal):
    if not paths:
        raise StopIteration

    new_paths = []
    for path in paths:
        if path[-1] == goal:
            yield path

        last = path[-1]
        for neighbor in graph[last]:
            if neighbor not in path:
                new_paths.append(path + [neighbor])
    yield from bfs(new_paths, goal)


for path in bfs([['A']], 'D'):
    print(path)

Oto implementacja rekurencyjnego BFS w Scali 2.11.4. Poświęciłem optymalizację wywołań ogonowych dla zwięzłości, ale wersja TCOd jest bardzo podobna. Zobacz także post @snv .

import scala.collection.immutable.Queue

object RecursiveBfs {
  def bfs[A](tree: Tree[A], target: A): Boolean = {
    bfs(Queue(tree), target)
  }

  private def bfs[A](forest: Queue[Tree[A]], target: A): Boolean = {
    forest.dequeueOption exists {
      case (E, tail) => bfs(tail, target)
      case (Node(value, _, _), _) if value == target => true
      case (Node(_, l, r), tail) => bfs(tail.enqueue(List(l, r)), target)
    }
  }

  sealed trait Tree[+A]
  case class Node[+A](data: A, left: Tree[A], right: Tree[A]) extends Tree[A]
  case object E extends Tree[Nothing]
}

Poniższe wydaje mi się całkiem naturalne, używając Haskella. Iteruj rekurencyjnie po poziomach drzewa (tutaj zbieram nazwy w duży uporządkowany ciąg, aby pokazać ścieżkę przez drzewo):

data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
    where levelRecurser level = if length level == 0
                                then ""
                                else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])

Oto implementacja Pythona z rekurencyjnym przechodzeniem przez BFS, pracująca dla wykresu bez cyklu.

def bfs_recursive(level):
    '''
     @params level: List<Node> containing the node for a specific level.
    '''
    next_level = []
    for node in level:
        print(node.value)
        for child_node in node.adjency_list:
            next_level.append(child_node)
    if len(next_level) != 0:
        bfs_recursive(next_level)


class Node:
    def __init__(self, value):
        self.value = value
        self.adjency_list = []

Chciałbym dodać moje centy do górnej odpowiedzi, ponieważ jeśli język obsługuje coś takiego jak generator, bfs można wykonać ko-rekurencyjnie.

Na początek odpowiedź @ Tanzelax brzmi:

Przechodzenie wszerz tradycyjnie używa kolejki, a nie stosu. Charakter kolejki i stosu są prawie przeciwne, więc próba użycia stosu wywołań (który jest stosem, stąd nazwa) jako magazynu pomocniczego (kolejki) jest prawie skazana na niepowodzenie

Rzeczywiście, zwykły stos wywołań funkcji nie będzie zachowywał się jak zwykły stos. Ale funkcja generatora zawiesi wykonywanie funkcji, więc daje nam szansę na uzyskanie następnego poziomu dzieci węzłów bez zagłębiania się w głębsze potomstwo węzła.

Poniższy kod jest rekurencyjnym bfs w Pythonie.

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

Oto intuicja:

1. bfs first zwróci root jako pierwszy wynik
2. załóżmy, że mamy już sekwencję bfs, następny poziom elementów w bfs to bezpośrednie dzieci poprzedniego węzła w sekwencji
3. powtórz powyższe dwie procedury

Musiałem zaimplementować przemierzanie sterty, które generuje w kolejności BFS. W rzeczywistości nie jest to BFS, ale spełnia to samo zadanie.

private void getNodeValue(Node node, int index, int[] array) {
    array[index] = node.value;
    index = (index*2)+1;

    Node left = node.leftNode;
    if (left!=null) getNodeValue(left,index,array);
    Node right = node.rightNode;
    if (right!=null) getNodeValue(right,index+1,array);
}

public int[] getHeap() {
    int[] nodes = new int[size];
    getNodeValue(root,0,nodes);
    return nodes;
}

Niech v będzie wierzchołkiem początkowym

Niech G będzie danym wykresem

Poniżej znajduje się pseudokod bez użycia kolejki

Initially label v as visited as you start from v
BFS(G,v)
    for all adjacent vertices w of v in G:
        if vertex w is not visited:
            label w as visited
    for all adjacent vertices w of v in G:
        recursively call BFS(G,w)

BFS dla drzewa binarnego (lub n-arnego) można wykonać rekurencyjnie bez kolejek w następujący sposób (tutaj w Javie):

public class BreathFirst {

    static class Node {
        Node(int value) {
            this(value, 0);
        }
        Node(int value, int nChildren) {
            this.value = value;
            this.children = new Node[nChildren];
        }
        int value;
        Node[] children;
    }

    static void breathFirst(Node root, Consumer<? super Node> printer) {
        boolean keepGoing = true;
        for (int level = 0; keepGoing; level++) {
            keepGoing = breathFirst(root, printer, level);
        }
    }

    static boolean breathFirst(Node node, Consumer<? super Node> printer, int depth) {
        if (depth < 0 || node == null) return false;
        if (depth == 0) {
            printer.accept(node);
            return true;
        }
        boolean any = false;
        for (final Node child : node.children) {
            any |= breathFirst(child, printer, depth - 1);
        }
        return any;
    }
}

Przykładowy wydruk przechodzenia od 1 do 12 w kolejności rosnącej:

public static void main(String... args) {
    //            1
    //          / | \
    //        2   3   4
    //      / |       | \
    //    5   6       7  8
    //  / |           | \
    // 9  10         11  12

    Node root = new Node(1, 3);
    root.children[0] = new Node(2, 2);
    root.children[1] = new Node(3);
    root.children[2] = new Node(4, 2);
    root.children[0].children[0] = new Node(5, 2);
    root.children[0].children[1] = new Node(6);
    root.children[2].children[0] = new Node(7, 2);
    root.children[2].children[1] = new Node(8);
    root.children[0].children[0].children[0] = new Node(9);
    root.children[0].children[0].children[1] = new Node(10);
    root.children[2].children[0].children[0] = new Node(11);
    root.children[2].children[0].children[1] = new Node(12);

    breathFirst(root, n -> System.out.println(n.value));
}

#include <bits/stdc++.h>
using namespace std;
#define Max 1000

vector <int> adj[Max];
bool visited[Max];

void bfs_recursion_utils(queue<int>& Q) {
    while(!Q.empty()) {
        int u = Q.front();
        visited[u] = true;
        cout << u << endl;
        Q.pop();
        for(int i = 0; i < (int)adj[u].size(); ++i) {
            int v = adj[u][i];
            if(!visited[v])
                Q.push(v), visited[v] = true;
        }
        bfs_recursion_utils(Q);
    }
}

void bfs_recursion(int source, queue <int>& Q) {
    memset(visited, false, sizeof visited);
    Q.push(source);
    bfs_recursion_utils(Q);
}

int main(void) {
    queue <int> Q;
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(5);
    adj[2].push_back(6);

    adj[3].push_back(7);

    bfs_recursion(1, Q);
    return 0;
}

Oto implementacja JavaScript, która fałszuje Breadth First Traversal z rekursją Depth First. Przechowuję wartości węzłów na każdej głębokości wewnątrz tablicy, wewnątrz skrótu. Jeśli poziom już istnieje (mamy kolizję), po prostu wypychamy do tablicy na tym poziomie. Możesz użyć tablicy zamiast obiektu JavaScript, ponieważ nasze poziomy są numeryczne i mogą służyć jako indeksy tablic. Możesz zwrócić węzły, wartości, przekonwertować na listę połączoną lub cokolwiek chcesz. Zwracam wartości ze względu na prostotę.

BinarySearchTree.prototype.breadthFirstRec = function() {

    var levels = {};

    var traverse = function(current, depth) {
        if (!current) return null;
        if (!levels[depth]) levels[depth] = [current.value];
        else levels[depth].push(current.value);
        traverse(current.left, depth + 1);
        traverse(current.right, depth + 1);
    };

    traverse(this.root, 0);
    return levels;
};


var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:  
{ '0': [ 20 ],
  '1': [ 8, 22 ],
  '2': [ 4, 12, 24 ],
  '3': [ 10, 14 ] } */

Oto przykład rzeczywistego pierwszego przejścia szerokości przy użyciu podejścia iteracyjnego.

BinarySearchTree.prototype.breadthFirst = function() {

    var result = '',
        queue = [],
        current = this.root;

    if (!current) return null;
    queue.push(current);

    while (current = queue.shift()) {
        result += current.value + ' ';
        current.left && queue.push(current.left);
        current.right && queue.push(current.right);
    }
    return result;
};

console.log('Breadth First: ', bst.breadthFirst());
//Breadth First:  20 8 22 4 12 24 10 14

Poniżej znajduje się mój kod do całkowicie rekurencyjnej implementacji przeszukiwania wszerz dwukierunkowego wykresu bez używania pętli i kolejki.

public class Graph
{
    public int V;   
    public LinkedList<Integer> adj[];

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList<>();
    }

    void addEdge(int v,int w)
    {
        adj[v].add(w);
        adj[w].add(v);
    }

    public LinkedList<Integer> getAdjVerted(int vertex)
    {
        return adj[vertex];
    }

    public String toString()
    {
        String s = "";

        for (int i=0;i<adj.length;i++)
        {
            s = s +"\n"+i +"-->"+ adj[i] ;
        }
        return s;
    }
}

//BFS IMPLEMENTATION

public static void recursiveBFS(Graph graph, int vertex,boolean visited[], boolean isAdjPrinted[])
    {
        if (!visited[vertex])
        {
            System.out.print(vertex +" ");
            visited[vertex] = true;
        }

        if(!isAdjPrinted[vertex])
        {
            isAdjPrinted[vertex] = true;
            List<Integer> adjList = graph.getAdjVerted(vertex);
            printAdjecent(graph, adjList, visited, 0,isAdjPrinted);
        }
    }

    public static void recursiveBFS(Graph graph, List<Integer> vertexList, boolean visited[], int i, boolean isAdjPrinted[])
    {
        if (i < vertexList.size())
        {
            recursiveBFS(graph, vertexList.get(i), visited, isAdjPrinted);
            recursiveBFS(graph, vertexList, visited, i+1, isAdjPrinted);
        }
    }

    public static void printAdjecent(Graph graph, List<Integer> list, boolean visited[], int i, boolean isAdjPrinted[])
    {
        if (i < list.size())
        {
            if (!visited[list.get(i)])
            {
                System.out.print(list.get(i)+" ");
                visited[list.get(i)] = true;
            }
            printAdjecent(graph, list, visited, i+1, isAdjPrinted);
        }
        else
        {
            recursiveBFS(graph, list, visited, 0, isAdjPrinted);
        }
    }

Implementacja C # rekurencyjnego algorytmu wyszukiwania wszerz dla drzewa binarnego.

Wizualizacja danych drzewa binarnego

IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
    {"A", new [] {"B", "C"}},
    {"B", new [] {"D", "E"}},
    {"C", new [] {"F", "G"}},
    {"E", new [] {"H"}}
};

void Main()
{
    var pathFound = BreadthFirstSearch("A", "H", new string[0]);
    Console.WriteLine(pathFound); // [A, B, E, H]

    var pathNotFound = BreadthFirstSearch("A", "Z", new string[0]);
    Console.WriteLine(pathNotFound); // []
}

IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path)
{
    if (start == end)
    {
        return path.Concat(new[] { end });
    }

    if (!graph.ContainsKey(start)) { return new string[0]; }    

    return graph[start].SelectMany(letter => BreadthFirstSearch(letter, end, path.Concat(new[] { start })));
}

Jeśli chcesz, aby algorytm działał nie tylko z drzewem binarnym, ale z wykresami, które mogą mieć dwa i więcej węzłów wskazujących na ten sam inny węzeł, musisz uniknąć samokontroli, utrzymując listę już odwiedzonych węzłów. Implementacja może wyglądać tak.

Wizualizacja danych graficznych

IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
    {"A", new [] {"B", "C"}},
    {"B", new [] {"D", "E"}},
    {"C", new [] {"F", "G", "E"}},
    {"E", new [] {"H"}}
};

void Main()
{
    var pathFound = BreadthFirstSearch("A", "H", new string[0], new List<string>());
    Console.WriteLine(pathFound); // [A, B, E, H]

    var pathNotFound = BreadthFirstSearch("A", "Z", new string[0], new List<string>());
    Console.WriteLine(pathNotFound); // []
}

IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path, IList<string> visited)
{
    if (start == end)
    {
        return path.Concat(new[] { end });
    }

    if (!graph.ContainsKey(start)) { return new string[0]; }


    return graph[start].Aggregate(new string[0], (acc, letter) =>
    {
        if (visited.Contains(letter))
        {
            return acc;
        }

        visited.Add(letter);

        var result = BreadthFirstSearch(letter, end, path.Concat(new[] { start }), visited);
        return acc.Concat(result).ToArray();
    });
}

Zrobiłem program przy użyciu C ++, który działa również na wykresie połączonym i rozłącznym.

    #include <queue>
#include "iostream"
#include "vector"
#include "queue"

using namespace std;

struct Edge {
    int source,destination;
};

class Graph{
    int V;
    vector<vector<int>> adjList;
public:

    Graph(vector<Edge> edges,int V){
        this->V = V;
        adjList.resize(V);
        for(auto i : edges){
            adjList[i.source].push_back(i.destination);
            //     adjList[i.destination].push_back(i.source);
        }
    }
    void BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q);
    void BFSRecursivelyJointandDisjointGraph(int s);
    void printGraph();


};

void Graph :: printGraph()
{
    for (int i = 0; i < this->adjList.size(); i++)
    {
        cout << i << " -- ";
        for (int v : this->adjList[i])
            cout <<"->"<< v << " ";
        cout << endl;
    }
}


void Graph ::BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q) {
    if (q.empty())
        return;
    int v = q.front();
    q.pop();
    cout << v <<" ";
    for (int u : this->adjList[v])
    {
        if (!discovered[u])
        {
            discovered[u] = true;
            q.push(u);
        }
    }
    BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);

}

void Graph ::BFSRecursivelyJointandDisjointGraph(int s) {
    vector<bool> discovered(V, false);
    queue<int> q;

    for (int i = s; i < V; i++) {
        if (discovered[i] == false)
        {
            discovered[i] = true;
            q.push(i);
            BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);
        }
    }
}

int main()
{

    vector<Edge> edges =
            {
                    {0, 1}, {0, 2}, {1, 2}, {2, 0}, {2,3},{3,3}
            };

    int V = 4;
    Graph graph(edges, V);
 //   graph.printGraph();
    graph.BFSRecursivelyJointandDisjointGraph(2);
    cout << "\n";




    edges = {
            {0,4},{1,2},{1,3},{1,4},{2,3},{3,4}
    };

    Graph graph2(edges,5);

    graph2.BFSRecursivelyJointandDisjointGraph(0);
    return 0;
}