DSA-Assignments

commit 07e5310a636c1b10046a36d5f2508500a0ae62e6
parent 52791360aa5492422d34f881077c2b1a77596d16
Author: VictorAdamson <Vall37mo>
Date:   Mon,  4 Dec 2023 12:17:39 +0100

Changed BFS funcion and added beginning for shortest path function

Diffstat:
M
Problem2/Problem2.cpp
 | 
24
+++++++++++++++++++++---

1 file changed, 21 insertions(+), 3 deletions(-)
diff --git a/Problem2/Problem2.cpp b/Problem2/Problem2.cpp
@@ -21,7 +21,8 @@ public:
     bool isEdge(int v, int w);
     int getNumNodes();
     void printGraph();
-    void BFS(int v);
+    bool BFS(int v, int w, int dist[]);
+    void printShortPath(int v, int w);
 };
 
 Graph::Graph(int V) {
@@ -31,6 +32,7 @@ Graph::Graph(int V) {
 
 void Graph::addEdge(int v, int w) {
     adj[v].push_back(w);
+    adj[w].push_back(v);
 }
 
 bool Graph::isEdge(int v, int w) {
@@ -56,14 +58,21 @@ void Graph::printGraph() {
         }
     }
 }
-void Graph::BFS(int v)
+bool Graph::BFS(int v, int w, int dist[])
 {
     vector<bool> visited;
     visited.resize(V, false);
 
     list<int> queue;
 
+    for (int i = 0; i < V; i++) {
+        visited[i] = false;
+        dist[i] = INT_MAX;
+
+    }
+
     visited[v] = true;
+    dist[v] = 0;
     queue.push_back(v);
 
     while (!queue.empty()) {
@@ -73,10 +82,19 @@ void Graph::BFS(int v)
         for (auto adjacent : adj[v]) {
             if (!visited[adjacent]) {
                 visited[adjacent] = true;
+                dist[v] = dist[v] + 1;
                 queue.push_back(adjacent);
+                if (adjacent == w) {
+                    return true;
+                }
             }
         }
     }
+    return false;
+}
+
+void Graph::printShortPath(int v, int w) {
+    
 }
 
 int main(){
@@ -92,7 +110,7 @@ int main(){
     list<int> nodes[4];
     cout << "\n" << "Number of nodes: " << i << "\n";
     cout << "Breadth First Traversal from A: \n";
-    network.BFS(0); //Traversal from 0 = A, 1 = B, 2 = C, 3 = D
+    //network.BFS(0, 3); //Traversal from source to destination (0 = A, 1 = B, 2 = C, 3 = D)
 }
 
 vector<int> findFriends(Graph network) {