add Seminar11

1 files changed, 50 insertions, 0 deletions

diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
new file mode 100644
index 0000000..1e4ec71
--- /dev/null
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
@@ -0,0 +1,50 @@
+/*
+Ориентиран тегловен граф представен чрез матрица на съседство.
+
+Плюсове:
+* Лесна имплементация
+* Проверка за ребро, премахване на ребро, добавяне на ребро са O(1)
+
+Минуси:
+* Паметта винаги е O(|V|^2)
+* Намирането на предшественици (наследници) или в неориентирания случай на съседи отнема O(|V|) време.
+
+weight_t => тип, чрез който представяме тежест
+vertex_t => тип, чрез който представяме връх
+*/
+
+#ifndef GRAPH_IMPL_H
+#define GRAPH_IMPL_H
+
+#include<vector>
+#include<cstddef>
+
+class MatrixGraph {
+    public:
+    using vertex_t = unsigned int;
+    using weight_t = unsigned int;
+
+    private:
+    std::vector<std::vector<weight_t>> data;
+
+    public:
+    MatrixGraph(size_t);
+
+    void addVertex();
+    void removeVertex(vertex_t);
+
+    void addDirectedEdge(vertex_t from, vertex_t to, weight_t w);
+    void addEdge(vertex_t from, vertex_t to, weight_t w);
+    void removeEdge(vertex_t from, vertex_t to);
+
+    bool validVertex(vertex_t) const;
+    weight_t getWeight(vertex_t, vertex_t) const;
+
+    size_t vertexCount() const;
+    bool adjacent(vertex_t from, vertex_t to) const;
+
+    std::vector<vertex_t> getSuccessors(vertex_t) const;
+    std::vector<vertex_t> getPredecessors(vertex_t) const;
+};
+
+#endif
\ No newline at end of file