- BFS: Shortest Reach in a Graph
- Discussions
BFS: Shortest Reach in a Graph
BFS: Shortest Reach in a Graph
+ 0 comments Below is the simple C++ solution
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> using namespace std; void BFS(vector<int> adj[], int visited[], int s) { queue<int> Q; Q.push(s); visited[s] = 0; while(!Q.empty()) { int node = Q.front(); Q.pop(); for(int i = 0; i < adj[node].size(); ++i) { if(visited[adj[node][i]] == -1) { visited[adj[node][i]] = 0; visited[adj[node][i]] = 6 + visited[node]; Q.push(adj[node][i]); // Pushing all the neighbouring nodes to the queue } } } } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int q; cin >> q; for(int i = 0; i < q; ++i) { int n, m, u, v, s; cin >> n >> m; vector<int> adj[n+1]; for(int j = 1; j <= m; ++j) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } cin >> s; int visited[n+1]; for(int i = 1; i <= n; ++i) visited[i] = -1; BFS(adj, visited, s); for(int i = 1; i <= n ; ++i) { if(visited[i] != 0) cout << visited[i] << " "; } cout << endl; } return 0; }
+ 0 comments Easy to understand python3
from collections import defaultdict class Graph: def __init__(self, n): self.graph = defaultdict(list) self.n_nodes = n def connect(self, u, v): self.graph[u].append(v) self.graph[v].append(u) def bfs(self, s): queue = [s] dists = {s: 0} while queue: n = queue.pop(0) for i in self.graph[n]: if i not in dists: dists[i] = dists[n] + 6 queue.append(i) return dists def find_all_distances(self, s): dists = self.bfs(s) ans = [] for node in range(self.n_nodes): if node == s: continue elif node not in dists: ans.append(-1) else: ans.append(dists[node]) print(" ".join(map(str, ans)))
+ 0 comments Consider an undirected graph consisting of nodes where each node is labeled from to and the edge between any two nodes is always of length . We define node to be the starting position for a BFS. Given a graph, determine the distances from the start node to each of its descendants and return the list in node number order, ascending. If a node is disconnected, it's distance should be .
For example, there are nodes in the graph with a starting node . The list of , and each has a weight of .
image
Starting from node and creating a list of distances, for nodes through we have .
Function Description
Define a Graph class with the required methods to return a list of distances.
Input Format
The first line contains an integer, , the number of queries.
Each of the following sets of lines is as follows:
The first line contains two space-separated integers, and , the number of nodes and the number of edges. Each of the next lines contains two space-separated integers, and , describing an edge connecting node to node . The last line contains a single integer, , the index of the starting node. Constraints
Output Format
For each of the queries, print a single line of space-separated integers denoting the shortest distances to each of the other nodes from starting position . These distances should be listed sequentially by node number (i.e., ), but should not include node . If some node is unreachable from , print as the distance to that node.
Sample Input
2 4 2 1 2 1 3 1 3 1 2 3 2 Sample Output
6 6 -1 -1 6 Explanation
We perform the following two queries:
The given graph can be represented as: image where our start node, , is node . The shortest distances from to the other nodes are one edge to node , one edge to node , and there is no connection to node . The given graph can be represented as: image where our start node, , is node . There is only one edge here, so node is unreachable from node and node has one edge connecting it to node . We then print node 's distance to nodes and (respectively) as a single line of space-separated integers: -1 6.
Note: Recall that the actual length of each edge is , and we print as the distance to any node that's unreachable from .
Language C++
More 16171819202122910111213141583456712
include
include
include
include
include
using namespace std;
class Graph { public: Graph(int n) {
Line: 3 Col: 18
Submit Code
Run Code
Upload Code as File
Test against custom input BlogScoringEnvironment
+ 0 comments The same code works in Python but fails in JavaScript for being slow in test case 5. Disappointing!
function processData(input) { //Enter your code here input = input.split('\n') let q = parseInt(input.shift()) for (let query = 0; query < q; query++) { let nm = input.shift() let n = parseInt(nm.split(' ')[0]) let m = parseInt(nm.split(' ')[1]) let edges = [] for (let i = 0; i < n + 1; i++) { edges.push([]) } for (let i = 0; i < m; i++) { let edge = input.shift().split(' ').map(e => parseInt(e)) edges[edge[0]].push(edge[1]) edges[edge[1]].push(edge[0]) } let root = parseInt(input.shift()) let feelers = [root] let distances = Array(n + 1).fill(-1) distances[root] = 0 while (feelers.length > 0) { let length = feelers.length for (let i = 0; i < feelers.length; i++) { let feeler = feelers[i] for (let connected of edges[feeler]) { if (distances[connected] != -1) { continue } distances[connected] = distances[feeler] + 6 feelers.push(connected) } } feelers = feelers.slice(length) } distances = [...distances.slice(1, root), ...distances.slice(root + 1)] console.log(distances.join(' ')) } } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); });
+ 0 comments
Sort 305 Discussions, By:
Please Login in order to post a comment