We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- BFS: Shortest Reach in a Graph
- Discussions
BFS: Shortest Reach in a Graph
BFS: Shortest Reach in a Graph
Sort by
recency
|
307 Discussions
|
Please Login in order to post a comment
Kotlin code
JAva code
Below is the simple C++ solution
Easy to understand python3
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