Рубрики

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

Первый обход по ширине (или поиск) для графика аналогичен первому обходу по ширине дерева (см. Способ 2 этого поста ). Единственный улов здесь, в отличие от деревьев, графы могут содержать циклы, поэтому мы можем снова прийти к одному и тому же узлу. Чтобы избежать обработки узла более одного раза, мы используем логический массив посещений. Для простоты предполагается, что все вершины достижимы из начальной вершины.
Например, на следующем графике мы начинаем обход с вершины 2. Когда мы подходим к вершине 0, мы ищем все смежные ее вершины. 2 также является смежной вершиной 0. Если мы не пометим посещенные вершины, то 2 будет обработан снова, и он станет непрерывным процессом. Первым обходом по ширине следующего графика является 2, 0, 3, 1.

Ниже приведены реализации простого обхода в ширину из данного источника.

Реализация использует представление списка смежности графов. Контейнер списка STL используется для хранения списков соседних узлов и очередей узлов, необходимых для обхода BFS.

C ++

// Программа для печати обхода 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

# 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


Выход:

Following is Breadth First Traversal (starting from vertex 2)
2 0 3 1

Иллюстрация:




Обратите внимание, что приведенный выше код пересекает только вершины, достижимые из данной исходной вершины. Все вершины могут быть недоступны из данной вершины (например, отключенный граф). Чтобы напечатать все вершины, мы можем изменить функцию BFS, чтобы она выполняла обход, начиная со всех узлов один за другим (как в модифицированной версии DFS ).

Сложность времени: O (V + E), где V — количество вершин в графе, а E — количество ребер в графе.

Вы можете также увидеть ниже:

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes