Algorithms : complete 03-algorithms_on_graphs 03-paths_in_graphs

1 files changed, 19 insertions, 3 deletions

diff --git a/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp b/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
index 5a6da4b..a411789 100644
--- a/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
+++ b/03-algorithms_on_graphs/03-paths_in_graphs/01-bfs/bfs.cpp
@@ -6,8 +6,24 @@ using std::vector;
 using std::queue;
 
 int distance(vector<vector<int> > &adj, int s, int t) {
-  //write your code here
-  return -1;
+  vector<int> d(adj.size(), -1);
+
+  queue<int> q;
+  q.push(s);
+  d[s] = 0;
+
+  while (!q.empty()) {
+      int v = q.front();
+      q.pop();
+      for (int i = 0; i < adj[v].size(); i++) {
+          int w = adj[v][i];
+          if (d[w] == -1) {
+              q.push(w);
+              d[w] = d[v] + 1;
+          }
+      }
+  }
+  return d[t];
 }
 
 int main() {
@@ -23,5 +39,5 @@ int main() {
   int s, t;
   std::cin >> s >> t;
   s--, t--;
-  std::cout << distance(adj, s, t);
+  std::cout << distance(adj, s, t) << '\n';
 }