Module: bfs. advanced course


Problem

1/3

0-1 BFS: Beginning (C++)

Theory Click to read/hide

0-1 BFS
To solve this problem, we modify the standard BFS algorithm using deques ( deque ): if the considered edge has a weight of 0, then we will add a vertex to the beginning, otherwise to the end. 
Thus, at the beginning of the deque there will always be a vertex, the distance to which is less than or equal to the distance to the other vertices of the deque, and the requirement to arrange elements in the deque in non-decreasing order is preserved.
For the implementation of the 0-1 BFS algorithm, see the problem itself.

Problem

Given an image of an undirected graph (has edges of weight 0 and 1), print a list of the shortest distances from vertex 0 to all others.
 
Input 
An image of an undirected graph with edges 0 and 1 is given.
 
Output
In your answer, output a list of shortest paths from vertex 0.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the 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;
}

     

Program check result

To check the solution of the problem, you need to register or log in!