0-1 BFS and bipartite checks

Questions 1 to 5 of 7

1. 1. What does this program print? It runs 0-1 BFS from node 0 on a graph with six nodes. ``cpp #include <cstddef> #include <deque> #include <iostream> #include <limits> #include <vector> struct Edge { int to; int cost; }; using Graph = std::vector<std::vector<Edge>>; std::vector<int> zeroOneBfs(const Graph& graph, int source) { constexpr int kInf = std::numeric_limits<int>::max(); std::vector<int> dist(graph.size(), kInf); std::deque<int> queue; dist[source] = 0; queue.push_back(source); while (!queue.empty()) { int node = queue.front(); queue.pop_front(); for (const Edge& edge : graph[node]) { int candidate = dist[node] + edge.cost; if (candidate < dist[edge.to]) { dist[edge.to] = candidate; if (edge.cost == 0) queue.push_front(edge.to); else queue.push_back(edge.to); } } } return dist; } int main() { Graph g(6); g[0] = {{1, 1}, {3, 0}}; g[1] = {{2, 1}}; g[3] = {{2, 0}, {4, 1}}; g[2] = {{4, 1}}; g[4] = {{5, 0}}; std::vector<int> dist = zeroOneBfs(g, 0); for (std::size_t i = 0; i < dist.size(); ++i) { if (i > 0) std::cout << ' '; std::cout << dist[i]; } std::cout << '\n'; } ``

   0 1 2 1 2 20 1 1 0 2 20 1 0 0 1 10 1 0 1 1 2
2. 2. What does this program print? It colours a graph with two colours, starting a new search at each uncoloured node. ``cpp #include <iostream> #include <optional> #include <queue> #include <vector> using Graph = std::vector<std::vector<int>>; std::optional<std::vector<int>> twoColorBfs(const Graph& graph) { const int n = static_cast<int>(graph.size()); std::vector<int> color(n, -1); for (int start = 0; start < n; ++start) { if (color[start] != -1) continue; color[start] = 0; std::queue<int> queue; queue.push(start); while (!queue.empty()) { int node = queue.front(); queue.pop(); for (int next : graph[node]) { if (color[next] == -1) { color[next] = 1 - color[node]; queue.push(next); } else if (color[next] == color[node]) { return std::nullopt; } } } } return color; } int main() { Graph g(5); auto addRival = [&](int a, int b) { g[a].push_back(b); g[b].push_back(a); }; addRival(1, 2); addRival(2, 3); addRival(3, 4); auto result = twoColorBfs(g); if (!result) { std::cout << "not bipartite\n"; return 0; } for (std::size_t i = 0; i < result->size(); ++i) { if (i > 0) std::cout << ' '; std::cout << (*result)[i]; } std::cout << '\n'; } ``

   0 1 0 1 00 0 1 0 11 0 1 0 10 0 1 1 0
3. 3. In 0-1 BFS, which rule for pushing a neighbour keeps the deque sorted by distance?

   Cost 0 edges go to the front and cost 1 edges go to the backCost 0 edges go to the back and cost 1 edges go to the frontEvery edge goes to the front, so the newest node is served firstEvery edge goes to the back, which gives different final distances
4. 4. Why must the bipartite check also run when a neighbour already has a colour?

   Coloured nodes are always the wrong colour, so they must be recolouredA clash can appear on an edge that closes a loop, such as the last edge of a triangle, so the check must run for coloured neighbours tooIt makes the search start again from node 0It counts how many components the graph has
5. 5. What happens to 0-1 BFS when one edge costs -1, and that edge sits in a loop whose total cost is negative?

   It stops after one pass with correct distances, because a single -1 edge is harmlessIt stops early with wrong distances, because the deque is no longer sortedIt never stops, because each trip round the loop lowers a distance againIt stops with an error message, because the code checks that every cost is 0 or 1