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

// 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 программа для реализации одного источника
# кратчайший путь для двоичного графа

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