0-1 BFS: Начало - BFS. Продвинутый курс

Для решения этой задачи модицифируем стандартный алгоритм BFS с помощью дек ( deque ):
если рассматриваемое ее ребро имеет вес 0, то будем добавлять вершину в начало, а иначе в конец.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и требование расположения элементов в деке в порядке неубывания сохраняется.

Task

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

Входные данные

Дано изображение неориентированного графа с ребрами 0 и 1.

Выходные данные

В ответе выведите список кратчайших путей от вершины 0.

C++

Write a program below
#include <iostream> #include <vector> #include <deque> #include <vector> #include <limits> #define V 9 using namespace std; struct node { int to, weight; }; vector <node> edges[V]; void bfs_0_1(int start) { int INF = numeric_limits<int>::max(); deque <int > Q; vector <int > dist(V, INF); dist[start] = 0; Q.push_back(start); while (!Q.empty()) { int u = Q.front(); Q.pop_front(); for (auto edge : edges[u]) { if (dist[edge.to] > dist[u] + edge.weight) { dist[edge.to] = dist[u] + edge.weight; if(edge.weight == 0 ) Q.push_front(edge.to) else Q.push_back(edge.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); //остальные ребра добавьте сами сами

bfs_0_1(0); return 0; }

Write a program below

#include <iostream>
#include <vector>
#include <deque>
#include <vector>
#include <limits>

#define V 9 

using namespace std;

struct node
{
	int to, weight;
};

vector <node> edges[V];
void bfs_0_1(int start) {
	int INF = numeric_limits<int>::max();
	deque <int > Q;
	vector <int > dist(V, INF);
	dist[start] = 0;
	Q.push_back(start);
	while (!Q.empty()) {
		int u = Q.front();
		Q.pop_front();
		for (auto edge : edges[u]) {
			if (dist[edge.to] > dist[u] + edge.weight) {
				dist[edge.to] = dist[u] + edge.weight;
				if(edge.weight == 0 )
                                         Q.push_front(edge.to) 
                                 else
                                         Q.push_back(edge.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);
	//остальные ребра добавьте сами сами

        bfs_0_1(0);
	return 0;
}

Your last submission is saved in the editor window.

Results:

All results:

Education

My Account

About us

№ 1/3 0-1 BFS: Начало

All results:

Education

My Account

About us