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.
Breadth First Search: Shortest Reach
Breadth First Search: Shortest Reach
+ 0 comments easy c++ solution using priority_queue:
vector bfs(int n, int m, vector> edges, int s) {
int dist[n]; map<int,vector<int>>mp; for(auto x:edges) { mp[x[0]].push_back(x[1]); mp[x[1]].push_back(x[0]); } for (int i=1;i<=n;i++){ dist[i] = INT_MAX; } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq; pq.push({0,s}); dist[s] = 0; while(!pq.empty()) { int cost = pq.top().first; int src = pq.top().second; pq.pop(); for(auto x: mp[src]) { if(dist[x] > cost +6) { dist[x] = cost+6; pq.push({dist[x],x}); } } } vector<int>ans; for(int i=1;i<=n;i++) { if(i==s) { continue; } else if(dist[i] == INT_MAX) { ans.push_back(-1); } else { ans.push_back(dist[i]); } } return ans;
} } } return ans; }
+ 0 comments ez c++ solution
vector<int> bfs(int n, int m, vector<vector<int>> edges, int s) { vector<int> res; cout<<res.size()<<endl; map<int,bool> marked; map<int,vector<int>> adj; for (int i =0;i<edges.size();i++){ vector<int> par = edges[i]; adj[par[0]].push_back(par[1]); adj[par[1]].push_back(par[0]); } for (auto x: adj){ marked[x.first] = false; } map<int,int> res2; queue<pair<int,int>> q; q.push({s,0}); marked[s] = true; while(!q.empty()){ pair<int,int> fr = q.front(); q.pop(); if (fr.second>0){ res2[fr.first] = fr.second; } for (int x : adj[fr.first]){ if (!marked[x]){ marked[x] = true; q.push({x,fr.second+6}); } } } for (int i =1;i<=n;i++){ if (i!=s){ if (marked[i]) res.push_back(res2[i]); else res.push_back(-1); } } return res; }
+ 0 comments JAVA 8:
public static List bfs(int n, int m, List> edges, int s) {
List<List<Integer>> l=new ArrayList<>(); while(n-->0) l.add(new ArrayList<Integer>()); for(int i=0;i<edges.size();i++) { int a=edges.get(i).get(0); int b=edges.get(i).get(1); List<Integer> temp = (l.get(a-1)); if(!temp.contains(b-1)) { temp.add(b-1); l.remove(a-1); l.add(a-1,temp); } temp = (l.get(b-1)); if(!temp.contains(a-1)) { temp.add(a-1); l.remove(b-1); l.add(b-1,temp); } } int[] d=new int[l.size()]; Arrays.fill(d,0); Boolean[] v=new Boolean[l.size()]; Arrays.fill(v,false); Queue<Integer> q=new LinkedList<Integer>(); q.add(s-1); v[s-1]=true; while(!q.isEmpty()){ int p=q.poll(); for(int i:l.get(p)){ if(v[i]==false) { v[i]=true; q.add(i); d[i]=6+d[p]; } } } List<Integer> r=new ArrayList<>(); for(int i=0;i<d.length;i++){ if(i==s-1) continue; else if(d[i]==0) r.add(-1); else r.add(d[i]); } return r; }
}
+ 0 comments C++ Solution vector bfs(int n, int m, vector> edges, int s) { unordered_map> adj;
for(auto edge: edges){ int u = edge[0]; int v = edge[1]; adj[u].push_back(v); adj[v].push_back(u); } unordered_map<int,bool> visited; queue<int> que; que.push(s); visited[s] = true; vector<int> dist(n+1,INT_MAX); dist[s] = 0; while(!que.empty()){ int temp = que.front(); que.pop(); for(auto v: adj[temp]){ if(!visited[v]){ que.push(v); visited[v] = true; dist[v] = dist[temp]+6; } } } vector<int> res; for(int i=1;i<=n;i++){ if(i == s){ continue; } if(dist[i] == INT_MAX){ res.push_back(-1); } else{ res.push_back(dist[i]); } } return res;
}
+ 0 comments Simple BFS solution (explained)Intuition behind the solution:
- The problem requires finding the shortest distance from a given starting node to all other nodes in an undirected graph.
- The breadth-first search (BFS) algorithm is well-suited for this task as it explores the nodes level by level, guaranteeing that the shortest path is found when a node is visited.
- By initializing the distances to all nodes as -1, except the starting node with a distance of 0, and using a queue to keep track of nodes to visit, we can gradually update the distances as we explore the graph.
Approach of the solution:
- Create a graph representation using a defaultdict of lists to store the adjacency list for each node.
- Initialize a distances list with -1 for all nodes, except the starting node which is set to 0.
- Use a deque (double-ended queue) to implement the BFS traversal.
- Start from the given starting node and enqueue it.
- While the queue is not empty, dequeue a node and explore its neighbors.
- For each unvisited neighbor, update its distance if it is -1 (indicating unvisited) and enqueue it.
- Repeat the process until all nodes have been visited.
- Remove the distance to the starting node from the distances list.
- Return the distances list.
Time complexity:
- Constructing the graph takes O(m) time, where m is the number of edges.
- The BFS traversal visits each node and edge once, resulting in a time complexity of O(n + m), where n is the number of nodes.
- Overall, the time complexity is O(n + m).
Space complexity:
- The space complexity is determined by the graph representation and the queue used in BFS.
- The graph representation requires O(n + m) space to store the adjacency lists.
- The queue can have a maximum size of n (in case all nodes are connected), resulting in O(n) space.
- Additionally, the distances list requires O(n) space.
- Overall, the space complexity is O(n + m).
from collections import defaultdict, deque def bfs(n, edges, s): graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) distances = [-1] * n distances[s-1] = 0 queue = deque([s]) while queue: node = queue.popleft() for neighbor in graph[node]: if distances[neighbor-1] == -1: distances[neighbor-1] = distances[node-1] + 6 queue.append(neighbor) distances.pop(s-1) return distances
Load more conversations
Sort 664 Discussions, By:
Please Login in order to post a comment