add Seminar11

1 files changed, 64 insertions, 0 deletions

diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
new file mode 100644
index 0000000..a19abcd
--- /dev/null
+++ b/Seminar11/bfs-dfs.cpp
@@ -0,0 +1,64 @@
+#include<iostream>
+#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h"
+#include"Graph-Impl/MatrixGraph/MatrixGraph.h"
+#include<queue>
+
+void BFS(const MatrixGraph& g, MatrixGraph::vertex_t start) {
+    std::vector<bool> visited(g.vertexCount(), false);
+
+    std::queue<MatrixGraph::vertex_t> q;
+
+    q.push(start);
+
+    while(!q.empty()) {
+        MatrixGraph::vertex_t current = q.front();
+        q.pop();
+
+        if(visited[current])
+            continue;
+        
+        visited[current] = true;
+
+        std::cout << current << " ";
+
+        auto successors = g.getSuccessors(current);
+
+        for(const auto& edge : successors) {
+            if(!visited[edge])
+                q.push(edge);
+        }
+    }
+}
+
+void DFSRec(std::vector<bool>& visited, const AdjListGraph& g, AdjListGraph::vertex_t start) {
+    visited[start] = true;
+
+    auto child = g.adjacent(start);
+
+    std::cout << "Visited " << start << std::endl;
+
+    for(const auto& currChild : child) {
+        if(!visited[currChild.to]) {
+            DFSRec(visited, g, currChild.to);
+        }
+    }
+}
+
+void DFS(const AdjListGraph& g, AdjListGraph::vertex_t start) {
+    std::vector<bool> visited(g.vertexCount(), false);
+    DFSRec(visited, g, start);
+}
+
+int main() {
+    MatrixGraph g(5);
+    // AdjListGraph g(5);
+    g.addEdge(0, 2, 1);
+    g.addEdge(0, 3, 1);
+    g.addEdge(0, 1, 1);
+    g.addEdge(2, 3, 1);
+    g.addEdge(1, 4, 1);
+    g.addEdge(3, 4, 1);
+    g.addEdge(1, 3, 1);
+
+    BFS(g, 0);
+}
\ No newline at end of file