Рубрики

0-1 BFS (кратчайший путь в бинарном графике веса)

Для данного графа вес каждого ребра равен 0 или 1. В графе также указана исходная вершина. Найдите кратчайший путь от исходной вершины до любой другой вершины.
Пример:

Input : Source Vertex = 0 and below graph 


Output : Shortest distances from given source
         0 0 1 1 2 1 2 1 2

Explanation : 
Shortest distance from 0 to 0 is 0
Shortest distance from 0 to 1 is 0
Shortest distance from 0 to 2 is 1
..................

В обычной BFS графа все ребра имеют одинаковый вес, но в 0-1 BFS некоторые ребра могут иметь 0 весов, а некоторые — 1 вес. В этом мы не будем использовать массив bool для маркировки посещенных узлов, но на каждом шаге мы будем проверять условие оптимального расстояния. Мы используем двустороннюю очередь для хранения узла. При выполнении BFS, если найден ребро с весом = 0, узел помещается впереди двухсторонней очереди, а если найдено ребро, имеющее вес = 1, он перемещается в конец двухсторонней очереди.

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

Вышеприведенная идея работает во всех случаях, когда всплывают вершины (например, Дейкстры), это минимальная весовая вершина среди оставшихся вершин. Если к нему примыкает 0 весовая вершина, то эта соседняя имеет такое же расстояние. Если есть смежный вес 1, то у этого смежного есть максимальное расстояние среди всех вершин в очереди (потому что все другие вершины либо смежны с текущей вытолкнутой вершиной, либо смежны с ранее вытолкнутыми вершинами).

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для реализации одного источника
// кратчайший путь для двоичного графа
#include<bits/stdc++.h>

using namespace std;

  
/ * нет вершин * /
#define V 9

  
// структура для представления ребер

struct node

{

    // две переменные одна обозначают узел

    // и другой вес

    int to, weight;

};

  
// вектор для хранения ребер
vector <node> edges[V];

  
// Печатает кратчайшее расстояние от данного источника до
// каждая вторая вершина

void zeroOneBFS(int src)

{

    // Инициализировать расстояния от заданного источника

    int dist[V];

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

        dist[i] = INT_MAX;

  

    // удваиваем очередь для выполнения BFS.

    deque <int> Q;

    dist[src] = 0;

    Q.push_back(src);

  

    while (!Q.empty())

    {

        int v = Q.front();

        Q.pop_front();

  

        for (int i=0; i<edges[v].size(); i++)

        {

            // проверка на оптимальное расстояние

            if (dist[edges[v][i].to] > dist[v] + edges[v][i].weight)

            {

                dist[edges[v][i].to] = dist[v] + edges[v][i].weight;

  

                // Поместить 0 ребер веса вперед и 1 вес

                // ребра назад, чтобы вершины обрабатывались

                // в порядке возрастания весов.

                if (edges[v][i].weight == 0)

                    Q.push_front(edges[v][i].to);

                else

                    Q.push_back(edges[v][i].to);

            }

        }

    }

  

    // печать кратчайших расстояний

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

        cout << dist[i] << " ";

}

  

void addEdge(int u, int v, int wt)

{

   edges[u].push_back({v, wt});

   edges[v].push_back({u, wt});

}

  
// Функция драйвера

int main()

{

    addEdge(0, 1, 0);

    addEdge(0, 7, 1);

    addEdge(1, 7, 1);

    addEdge(1, 2, 1);

    addEdge(2, 3, 0);

    addEdge(2, 5, 0);

    addEdge(2, 8, 1);

    addEdge(3, 4, 1);

    addEdge(3, 5, 1);

    addEdge(4, 5, 1);

    addEdge(5, 6, 1);

    addEdge(6, 7, 1);

    addEdge(7, 8, 1);

    int src = 0;// исходный узел

    zeroOneBFS(src);

    return 0;

}

Джава

// Java-программа для реализации 0-1 BFS

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Deque;

  

public class ZeroOneBFS {

    private static class Node {

        int to; // конечная вершина

        int weight; // вес ребра

          

        public Node(int to, int wt) {

            this.to = to;

            this.weight = wt;

        }

    }

      

    private static final int numVertex = 9;

    private ArrayList<Node>[] edges = new ArrayList[numVertex];

      

    public ZeroOneBFS() {

        for (int i = 0; i < edges.length; i++) {

            edges[i] = new ArrayList<Node>();

        }

    }

      

    public void addEdge(int u, int v, int wt) {

        edges[u].add(edges[u].size(), new Node(v, wt));

        edges[v].add(edges[v].size(), new Node(u, wt));

    }

      

    public void zeroOneBFS(int src) {

  

        // инициализировать расстояния от заданного источника

        int[] dist = new int[numVertex];

        for (int i = 0; i < numVertex; i++) {

            dist[i] = Integer.MAX_VALUE;

        }

          

        // двусторонняя очередь для выполнения BFS

        Deque<Integer> queue = new ArrayDeque<Integer>();

        dist[src] = 0;

        queue.addLast(src);

          

        while (!queue.isEmpty()) {

            int v = queue.removeFirst();

            for (int i = 0; i < edges[v].size(); i++) {

  

                // проверка на оптимальное расстояние

                if (dist[edges[v].get(i).to] > 

                        dist[v] + edges[v].get(i).weight) {

  

                    // обновляем расстояние

                    dist[edges[v].get(i).to] =

                          dist[v] + edges[v].get(i).weight;

  

                    // поместим 0 весовых граней вперед и 1

                    // вес ребер назад, чтобы вершины

                    // обрабатываются в порядке возрастания веса

                    if (edges[v].get(i).weight == 0) {

                        queue.addFirst(edges[v].get(i).to);

                    } else {

                        queue.addLast(edges[v].get(i).to);

                    }

                }

            }

        }

          

        for (int i = 0; i < dist.length; i++) {

            System.out.print(dist[i] + " ");

        }

    }

      

    public static void main(String[] args) {

        ZeroOneBFS graph = new ZeroOneBFS();

        graph.addEdge(0, 1, 0);

        graph.addEdge(0, 7, 1);

        graph.addEdge(1, 7, 1);

        graph.addEdge(1, 2, 1);

        graph.addEdge(2, 3, 0);

        graph.addEdge(2, 5, 0);

        graph.addEdge(2, 8, 1);

        graph.addEdge(3, 4, 1);

        graph.addEdge(3, 5, 1);

        graph.addEdge(4, 5, 1);

        graph.addEdge(5, 6, 1);

        graph.addEdge(6, 7, 1);

        graph.addEdge(7, 8, 1);

        int src = 0;// исходный узел

        graph.zeroOneBFS(src);

        return;

    }

}

python3

# Python3 программа для реализации одного источника
# кратчайший путь для двоичного графа

from sys import maxsize as INT_MAX

from collections import deque

  
# № вершин

V = 9

  
# структура для представления ребер

class node:

    def __init__(self, to, weight):

  

        # две переменные one обозначают узел

        # и другие веса

        self.to = to

        self.weight = weight

  
# вектор для хранения ребер

edges = [0] * V

for i in range(V):

    edges[i] = []

  
# Печать кратчайшего расстояния от
# данный источник для каждой другой вершины

def zeroOneBFS(src: int):

  

    # Инициализировать расстояния от заданного источника

    dist = [0] * V

    for i in range(V):

        dist[i] = INT_MAX

  

    # двойная очередь для выполнения BFS.

    Q = deque()

    dist[src] = 0

    Q.append(src)

  

    while Q:

        v = Q[0]

        Q.popleft()

  

        for i in range(len(edges[v])):

  

            # проверка оптимального расстояния

            if (dist[edges[v][i].to] > 

                dist[v] + edges[v][i].weight):

                dist[edges[v][i].to] = dist[v] + edges[v][i].weight

  

                # Поместите 0 ребер веса вперед и 1 вес

                # ребра к спине, чтобы вершины обрабатывались

                # в порядке возрастания веса.

                if edges[v][i].weight == 0:

                    Q.appendleft(edges[v][i].to)

                else:

                    Q.append(edges[v][i].to)

  

    # печать кратчайших расстояний

    for i in range(V):

        print(dist[i], end = " ")

    print()

  

def addEdge(u: int, v: int, wt: int):

    edges[u].append(node(v, wt))

    edges[u].append(node(v, wt))

  
Код водителя

if __name__ == "__main__":

  

    addEdge(0, 1, 0)

    addEdge(0, 7, 1)

    addEdge(1, 7, 1)

    addEdge(1, 2, 1)

    addEdge(2, 3, 0)

    addEdge(2, 5, 0)

    addEdge(2, 8, 1)

    addEdge(3, 4, 1)

    addEdge(3, 5, 1)

    addEdge(4, 5, 1)

    addEdge(5, 6, 1)

    addEdge(6, 7, 1)

    addEdge(7, 8, 1)

  

    # исходный узел

    src = 0

    zeroOneBFS(src)

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


Выход:

0 0 1 1 2 1 2 1 2 

Эта проблема также может быть решена с помощью Дейкстры, но сложность по времени будет O (E + V Log V), тогда как по BFS это будет O (V + E).

Ссылка :
http://codeforces.com/blog/entry/22276

Эта статья предоставлена Аюшем Джа . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

0-1 BFS (кратчайший путь в бинарном графике веса)

0.00 (0%) 0 votes