Поиск в ширину или BFS для графика

// Программа для печати обхода BFS из заданного
// исходная вершина. BFS (int s) пересекает вершины
// достижим от s.
#include<iostream>
#include <list>

using namespace std;

  
// Этот класс представляет ориентированный граф, используя
// представление списка смежности

class Graph

{

    int V;    // Количество вершин

    // Указатель на массив, содержащий смежность

    // списки

    list<int> *adj;   

public:

    Graph(int V);  // Конструктор

    // функция для добавления ребра на график

    void addEdge(int v, int w); 

    // печатает прохождение BFS из заданного источника

    void BFS(int s);  

};

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

}

void Graph::BFS(int s)

{

    // Пометить все вершины как не посещенные

    bool *visited = new bool[V];

    for(int i = 0; i < V; i++)

        visited[i] = false;

    // Создать очередь для BFS

    list<int> queue;

    // Помечаем текущий узел как посещенный и ставим его в очередь

    visited[s] = true;

    queue.push_back(s);

    // 'i' будет использоваться для получения всех соседних

    // вершины вершины

    list<int>::iterator i;

    while(!queue.empty())

    {

        // Удаление вершины из очереди и печать ее

        s = queue.front();

        cout << s << " ";

        queue.pop_front();

        // Получить все смежные вершины исключенного из очереди

        // вершина s. Если соседний не был посещен,

        // затем помечаем его как посещенный и ставим в очередь

        for (i = adj[s].begin(); i != adj[s].end(); ++i)

        {

            if (!visited[*i])

            {

                visited[*i] = true;

                queue.push_back(*i);

            }

        }

    }

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(4);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 2);

    g.addEdge(2, 0);

    g.addEdge(2, 3);

    g.addEdge(3, 3);

    cout << "Following is Breadth First Traversal "

         << "(starting from vertex 2) \n";

    g.BFS(2);

    return 0;

}

// Java-программа для печати обхода BFS из заданной исходной вершины.
// BFS (int s) пересекает вершины, достижимые из s.

import java.io.*;

import java.util.*;

  
// Этот класс представляет ориентированный граф, используя список смежности
// представление

class Graph

{

    private int V;   // Количество вершин

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

    }

    // печатает прохождение BFS из заданного источника

    void BFS(int s)

    {

        // Пометить все вершины как не посещенные (по умолчанию

        // устанавливается как ложное)

        boolean visited[] = new boolean[V];

        // Создать очередь для BFS

        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Помечаем текущий узел как посещенный и ставим его в очередь

        visited[s]=true;

        queue.add(s);

        while (queue.size() != 0)

        {

            // Удаление вершины из очереди и печать ее

            s = queue.poll();

            System.out.print(s+" ");

            // Получаем все смежные вершины удаленной вершины s

            // Если соседний объект не был посещен, отметьте его

            // посетили и поставили в очередь

            Iterator<Integer> i = adj[s].listIterator();

            while (i.hasNext())

            {

                int n = i.next();

                if (!visited[n])

                {

                    visited[n] = true;

                    queue.add(n);

                }

            }

        }

    }

    // Метод драйвера для

    public static void main(String args[])

    {

        Graph g = new Graph(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal "+

                           "(starting from vertex 2)");

        g.BFS(2);

    }

}
// Этот код предоставлен Aakash Hasija

# Python3 Программа для печати обхода BFS
# из заданной исходной вершины. BFS (int s)
# проходит через вершины, достижимые из s.

from collections import defaultdict

  
# Этот класс представляет ориентированный граф
# использование представления списка смежности

class Graph:

    # Конструктор

    def __init__(self):

        # словарь по умолчанию для хранения графика

        self.graph = defaultdict(list)

    # функция для добавления ребра на график

    def addEdge(self,u,v):

        self.graph[u].append(v)

    # Функция для печати BFS графа

    def BFS(self, s):

        # Отметить все вершины как не посещенные

        visited = [False] * (len(self.graph))

        # Создать очередь для BFS

        queue = []

        # Отметить исходный узел как

        # посетил и поставил в очередь

        queue.append(s)

        visited[s] = True

        while queue:

            # Удаление вершины из

            # очередь и распечатать

            s = queue.pop(0)

            print (s, end = " ")

            # Получить все смежные вершины

            # удаленная вершина s. Если рядом

            # не был посещен, отметьте его

            # посетил и поставил в очередь

            for i in self.graph[s]:

                if visited[i] == False:

                    queue.append(i)

                    visited[i] = True

  
# Код драйвера

  
# Создать график, указанный в
# приведенная выше диаграмма

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

print ("Following is Breadth First Traversal"

                  " (starting from vertex 2)")

g.BFS(2)

  
# Этот код предоставлен Neelam Yadav