Effectuer une première recherche en largeur de manière récursive

Supposons que vous vouliez implémenter une recherche en largeur dans un arbre binaire de manière récursive . Comment procéderiez-vous?

Est-il possible d'utiliser uniquement la pile d'appels comme stockage auxiliaire?

(Je suppose que c'est juste une sorte d'exercice de réflexion, ou même une question astucieuse pour les devoirs / entretien, mais je suppose que je pourrais imaginer un scénario bizarre dans lequel vous n'êtes pas autorisé à tout espace pour une raison quelconque [une très mauvaise coutume gestionnaire de mémoire? quelques problèmes d'exécution / OS bizarres?] pendant que vous avez toujours accès à la pile ...)

La traversée en largeur d'abord utilise traditionnellement une file d'attente, pas une pile. La nature d'une file d'attente et d'une pile est à peu près opposée, donc essayer d'utiliser la pile d'appels (qui est une pile, d'où son nom) comme stockage auxiliaire (une file d'attente) est à peu près voué à l'échec, sauf si vous le faites quelque chose de stupidement ridicule avec la pile d'appels que vous ne devriez pas être.

Dans le même ordre d'idées, la nature de toute récursivité sans queue que vous essayez d'implémenter consiste essentiellement à ajouter une pile à l'algorithme. Cela fait que la première recherche sur un arbre binaire n'est plus étendue, et par conséquent, le temps d'exécution et ainsi de suite pour les BFS traditionnels ne s'appliquent plus complètement. Bien sûr, vous pouvez toujours transformer trivialement n'importe quelle boucle en un appel récursif, mais ce n'est pas une sorte de récursivité significative.

Cependant, il existe des moyens, comme l'ont démontré d'autres, d'implémenter quelque chose qui suit la sémantique de BFS à un certain prix. Si le coût de la comparaison est cher mais que la traversée des nœuds est bon marché, alors comme @Simon Buchan l'a fait, vous pouvez simplement exécuter une recherche itérative en profondeur d'abord, ne traitant que les feuilles. Cela signifierait qu'aucune file d'attente croissante n'est stockée dans le tas, juste une variable de profondeur locale et que les piles sont construites encore et encore sur la pile d'appels au fur et à mesure que l'arbre est parcouru encore et encore. Et comme @Patrick l'a noté, un arbre binaire soutenu par un tableau est généralement stocké dans l'ordre de traversée en largeur d'abord, donc une recherche en largeur d'abord serait triviale, également sans avoir besoin d'une file d'attente auxiliaire.

Si vous utilisez un tableau pour sauvegarder l'arborescence binaire, vous pouvez déterminer algébriquement le nœud suivant. si iest un nœud, alors ses enfants peuvent être trouvés à 2i + 1(pour le nœud de gauche) et 2i + 2(pour le nœud de droite). Le prochain voisin d'un nœud est donné par i + 1, sauf si iune puissance de2

Voici le pseudocode pour une implémentation très naïve de la première recherche en largeur sur un arbre de recherche binaire basé sur un tableau. Cela suppose un tableau de taille fixe et donc un arbre de profondeur fixe. Il examinera les nœuds sans parents et pourrait créer une pile d'une grande taille impossible à gérer.

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)        

Je n'ai pas pu trouver un moyen de le faire complètement récursif (sans aucune structure de données auxiliaire). Mais si la file d'attente Q est passée par référence, vous pouvez avoir la fonction récursive de queue idiote suivante:

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

     BFS(Q)
}

La méthode suivante a utilisé un algorithme DFS pour obtenir tous les nœuds dans une profondeur particulière - ce qui revient à faire BFS pour ce niveau. Si vous trouvez la profondeur de l'arbre et faites cela pour tous les niveaux, les résultats seront les mêmes que ceux d'un 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);
}

Trouver la profondeur d'un arbre est un jeu d'enfant:

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

Une simple récursivité BFS et DFS en Java: il
suffit de pousser / proposer le nœud racine de l'arborescence dans la pile / file d'attente et d'appeler ces fonctions.

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);
}

J'ai trouvé un très bel algorithme de traversée récursif (même fonctionnel) lié à la largeur d'abord. Ce n'est pas mon idée, mais je pense que cela devrait être mentionné dans ce sujet.

Chris Okasaki explique très clairement son algorithme de numérotation en largeur de ICFP 2000 à http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html avec seulement 3 images.

L'implémentation Scala de Debasish Ghosh, que j'ai trouvée sur http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html , est:

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
}

La manière stupide:

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;
}

Voici une courte solution Scala :

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

L'idée d' utiliser la valeur de retour comme accumulateur est bien adaptée. Peut être implémenté dans d'autres langages de la même manière, assurez-vous simplement que votre fonction récursive traite la liste des nœuds .

Liste des codes de test (en utilisant l'arbre de test @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())))
  }
}

Production:

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

Voici une implémentation python:

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)

Voici une implémentation Scala 2.11.4 de BFS récursif. J'ai sacrifié l'optimisation des appels de fin pour la brièveté, mais la version TCOd est très similaire. Voir aussi la publication de @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]
}

Ce qui suit me semble assez naturel, en utilisant Haskell. Itérer de manière récursive sur les niveaux de l'arbre (ici, je rassemble les noms dans une grande chaîne ordonnée pour montrer le chemin à travers l'arbre):

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])

Voici une implémentation Python de traversée récursive BFS, fonctionnant pour un graphe sans cycle.

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 = []

Je voudrais ajouter mes centimes à la réponse du haut en ce que si le langage prend en charge quelque chose comme générateur, bfs peut être fait de manière co-récursive.

Pour commencer, la réponse de @ Tanzelax se lit comme suit:

La traversée en largeur d'abord utilise traditionnellement une file d'attente, pas une pile. La nature d'une file d'attente et d'une pile est à peu près opposée, donc essayer d'utiliser la pile d'appels (qui est une pile, d'où son nom) comme stockage auxiliaire (une file d'attente) est à peu près voué à l'échec

En effet, la pile d'un appel de fonction ordinaire ne se comportera pas comme une pile normale. Mais la fonction de générateur suspendra l'exécution de la fonction, ce qui nous donne la possibilité de produire le niveau suivant d'enfants des nœuds sans plonger dans les descendants plus profonds du nœud.

Le code suivant est bfs récursif en Python.

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

L'intuition ici est:

1. bfs retournera d'abord la racine comme premier résultat
2. supposons que nous ayons déjà la séquence bfs, le niveau suivant d'éléments dans bfs est les enfants immédiats du nœud précédent dans la séquence
3. répétez les deux procédures ci-dessus

J'ai dû implémenter une traversée de tas qui sort dans un ordre BFS. Ce n'est pas réellement BFS mais accomplit la même tâche.

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;
}

Soit v le sommet de départ

Soit G le graphe en question

Ce qui suit est le pseudo code sans utiliser la file d'attente

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)

Le BFS pour un arbre binaire (ou n-aire) peut être effectué de manière récursive sans files d'attente comme suit (ici en Java):

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;
    }
}

Un exemple de traversée imprimant les numéros 1 à 12 dans l'ordre croissant:

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;
}

Voici une implémentation JavaScript qui simule une traversée en largeur d'abord avec une récursivité en profondeur d'abord. Je stocke les valeurs de nœud à chaque profondeur dans un tableau, à l'intérieur d'un hachage. Si un niveau existe déjà (nous avons une collision), nous allons donc simplement pousser vers le tableau à ce niveau. Vous pouvez également utiliser un tableau au lieu d'un objet JavaScript puisque nos niveaux sont numériques et peuvent servir d'indices de tableau. Vous pouvez renvoyer des nœuds, des valeurs, les convertir en liste liée ou tout ce que vous voulez. Je renvoie juste des valeurs par souci de simplicité.

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 ] } */

Voici un exemple de traversée réelle de largeur en premier utilisant une approche itérative.

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

Voici mon code pour une implémentation complètement récursive de la recherche en largeur d'abord d'un graphe bidirectionnel sans utiliser de boucle ni de file d'attente.

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);
        }
    }

Implémentation C # d'un algorithme de recherche récursif en largeur d'abord pour un arbre binaire.

Visualisation de données d'arbre binaire

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 })));
}

Si vous voulez que l'algorithme fonctionne non seulement avec un arbre binaire, mais avec des graphiques, ce qui peut avoir deux nœuds et plus qui pointent vers le même autre nœud, vous devez éviter l'auto-cycle en tenant la liste des nœuds déjà visités. La mise en œuvre peut ressembler à ceci.

Visualisation des données graphiques

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();
    });
}

J'ai fait un programme utilisant C ++ qui fonctionne aussi dans le graphe joint et disjoint.

    #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;
}