diff options
Cleanup
16 files changed, 0 insertions, 752 deletions
| -rw-r--r-- | Seminar11/DFS-Additional.cpp | 200 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp | 82 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h | 50 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp | 19 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp | 97 | ||||
| -rw-r--r-- | Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h | 52 | ||||
| -rw-r--r-- | Seminar11/README.md | 187 | ||||
| -rw-r--r-- | Seminar11/bfs-dfs.cpp | 65 | ||||
| -rw-r--r-- | Seminar11/media/dfs-example.gif | bin | 611116 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/dir-graph.png | bin | 10387 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/graph.png | bin | 10829 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/matrix.png | bin | 26595 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/weighted-dirscted-graph (1).png | bin | 19387 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/weighted-graph.png | bin | 16585 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/media/weighted-list.png | bin | 42035 -> 0 bytes | |||
| -rw-r--r-- | Seminar11/package.json | 0 |
diff --git a/Seminar11/DFS-Additional.cpp b/Seminar11/DFS-Additional.cpp deleted file mode 100644 index a5022e3..0000000 --- a/Seminar11/DFS-Additional.cpp +++ /dev/null @@ -1,200 +0,0 @@ -// Малко допълнителни неща покрай дфс ако ви е интересно. -#include<iostream> -#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h" -#include"Graph-Impl/MatrixGraph/MatrixGraph.h" -#include<vector> -#include<algorithm> - -using std::vector; -using vertex_t = AdjListGraph::vertex_t; // Типа представящ връх в графа - -class DFSExamples { -private: - vector<size_t> in; - vector<size_t> out; - vector<vertex_t> parent; - -public: - -void DFS_Visit(const AdjListGraph& g, size_t& time, vertex_t s) { - in[s] = time; - time++; - - const auto& adj = g.adjacent(s); - - for(const auto& v : adj) { - if(in[v.to] == -1) { - parent[v.to] = s; - DFS_Visit(g, time, v.to); - } - } - - time++; - out[s] = time; -} - -void DFS(const AdjListGraph& g, bool showDetails) { - // Нека си представим, че имаме време. Всяка стъпка на алгоритъма отнема една единица време. - size_t time = 0; - - // Всеки връх бива открит в някакво време. Нека в този масив записваме кога е бил открит всеки връх. - in = vector(g.vertexCount(), (size_t)(-1)); - - // С всеки връх приключваме по някое време. Той няма повече непосетени съседи и спираме да се интересуваме от него. - // Нека в този масив записваме кога се случва това. - out = vector(g.vertexCount(), (size_t)(-1)); - - // std::vector<bool> visited(g.vertexCount(), false); - // - от този масив вече нямаме нужда. Връх v e посетен когато in[v] != -1. - - // Също така в примера видяхме, че DFS прави дърво. Нека си запазим това дърво. - // Тук стандартното представяне на дърво е неудобно, затова ще представяме дървото като масив от бащите. - // Примомняне: Ако v e връх parent[v] е бащата на v или -1 ако v e корен. - parent = vector(g.vertexCount(), (vertex_t)(-1)); - - // За всеки връх - for (vertex_t i = 0; i < g.vertexCount(); i++) - if(in[i] == -1) // Ако не е посетен - DFS_Visit(g, time, i); // Посети го и посети всички върхове достижими от него - - // Да видим какво имаме - if(showDetails) { - for (vertex_t i = 0; i < g.vertexCount(); i++) { - std::cout << "Vertex " << i << std::endl; - std::cout - << "Discovered at: " << in[i] << std::endl - << "Finished at: " << out[i] << std::endl - << "Parent: " << parent[i] << std::endl << std::endl; - } - } -} - -void DFS_Visit_Tsort(const MatrixGraph g, size_t& time, vertex_t s) { - in[s] = time; - time++; - - const auto& adj = g.adjacent(s); - - for(const auto& v : adj) { - if(in[v] == -1) { - parent[v] = s; - DFS_Visit_Tsort(g, time, v); - } - } - - time++; - out[s] = time; -} - -// Топологически сортировки, Job scheduling -// Защо са ни тези масиви in и out? Те ни дават информация, която можем да използваме за други интересни алгоритми. -// Ще оставим подробното им разглеждане на други курсове, тук само ще разгледаме един бърз пример. - -// Нека си представим, че имаме някакви задачи за вършене. Абсолютно вероятно е някои от тези задачи да зависят от други. -// Примерно, не мога да кандидатствам за университет ако преди това нямам диплома за завършен 12 клас -// (въпреки, че май е възможно в някои нови български университети). -// -// Можем да си представим задачите като върхове, а това, че задача А трябва да се изпълни преди задача Б да -// бележим чрез ориентирано ребро А -> Б. -// -// Искам така да си подредя задачите, че да ги изпълня без да нарушавам зависимостите. -// -// Твърдя, че ако пусна DFS, и сортирам върховете по out стойности в намаляващ ред това решава задачата ми. -// -// Накратко, защо това е вярно? -// Нека имам V -> U. Има два случая, или да открия V преди U или да открия U преди V. -// -// 1. Откривам V преди U. Да де, но имам ребро от V към U, Следователно ще открия и финализирам U преди да финализирам V. -// Сега out[U] > out[V] и не нарушавам зависимостите. -// 2. Ако открия U преди V, ще финализирам U преди да стигна до V. В графа няма цикли и ако имаше път от U -> V това би затворило цикъл. -// Тоест ще финализирам U преди да открия V. От тук следва, че out[U] > in[V] > out[V], което отново влече наредба, която не нарушава зависимостите. -// Няма други случаи. - -void DFS_Tsort(const MatrixGraph& g) { - size_t time = 0; - - in = vector(g.vertexCount(), (size_t)(-1)); - out = vector(g.vertexCount(), (size_t)(-1)); - parent = vector(g.vertexCount(), (vertex_t)(-1)); - - for (vertex_t i = 0; i < g.vertexCount(); i++) - if(in[i] == -1) - DFS_Visit_Tsort(g, time, i); - - std::vector<std::pair<vertex_t, size_t>> result(g.vertexCount()); - - for (vertex_t i = 0; i < g.vertexCount(); i++) - result[i] = {i, out[i]}; - - auto comp = [](std::pair<vertex_t, size_t>& fst, std::pair<vertex_t, size_t>& snd) -> bool { - return fst.second > snd.second; - }; - - std::sort(result.begin(), result.end(), comp); - - for(const auto& vertexOutPair : result) - std::cout << vertexOutPair.first << " "; -} - -// Използвам матричния, понеже той е ориентиран. -void tsort(const MatrixGraph& g) { - size_t time = 0; - - // Нулираме масивите - in = vector(g.vertexCount(), (size_t)(-1)); - out = vector(g.vertexCount(), (size_t)(-1)); - parent = vector(g.vertexCount(), (vertex_t)(-1)); - - DFS_Tsort(g); -} -}; - -int main() { - DFSExamples d; - - // Нека си вземем графа от примера - // Там върховете са номерирани от 1 до 12 - // Тук от 0 до 11 - AdjListGraph g(12); - - g.addEdge(0, 2, 1); - g.addEdge(0, 4, 1); - g.addEdge(0, 5, 1); - g.addEdge(0, 8, 1); - - g.addEdge(1, 7, 1); - g.addEdge(1, 3, 1); - - g.addEdge(2, 4, 1); - g.addEdge(2, 5, 1); - g.addEdge(2, 6, 1); - g.addEdge(2, 7, 1); - - g.addEdge(3, 9, 1); - - g.addEdge(4, 6, 1); - - g.addEdge(8, 11, 1); - g.addEdge(8, 10, 1); - - g.addEdge(10, 11, 1); - - d.DFS(g, true); - - // Пример за топосортировка - MatrixGraph tsort(9); - - - // https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/mit6_006f11_lec14_orig/ - // Този граф е взет от линка и е на страница 5. - tsort.addDirectedEdge(5, 3, 1); - tsort.addDirectedEdge(4, 3, 1); - tsort.addDirectedEdge(4, 2, 1); - tsort.addDirectedEdge(2, 1, 1); - tsort.addDirectedEdge(1, 0, 1); - tsort.addDirectedEdge(7, 2, 1); - tsort.addDirectedEdge(7, 6, 1); - tsort.addDirectedEdge(6, 1, 1); - - d.DFS_Tsort(tsort); -}
\ No newline at end of file diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp deleted file mode 100644 index 3cbbdd0..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include"AdjListGraph.h" - -using vertex_t = AdjListGraph::vertex_t; -using weight_t = AdjListGraph::weight_t; - -AdjListGraph::AdjListGraph(size_t vertexCount) { - data = std::vector<std::list<Edge>>(vertexCount, std::list<Edge>()); -} - -void AdjListGraph::addVertex() { - data.push_back(std::list<Edge>()); -} - -void AdjListGraph::removeVertex(vertex_t v) { - if(!validVertex(v)) - throw "Invalid vertex"; - - // Премахва самия връх - data.erase(data.begin() + v); - - // За всеки от останалите върхове ако - // има елемент, който сочи към него трябва да се изтрие - // ако има елемент, който е по - голям от него трябва да се намали с 1 - - for(auto& vertexList : data) { - vertexList.remove_if([&](Edge e) -> bool { return e.to == v; }); - - for(Edge& e : vertexList) - if(e.to > v) - e.to--; - } -} - -bool AdjListGraph::validVertex(vertex_t v) const { - return v < data.size(); -} - -void AdjListGraph::addEdge(vertex_t from, vertex_t to, weight_t w) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from].push_back( {to, w} ); - data[to].push_back( {from, w} ); -} - -void AdjListGraph::removeEdge(vertex_t from, vertex_t to) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from].remove_if([&](Edge e) -> bool {return e.to == to; }); - data[to].remove_if([&](Edge e) -> bool {return e.to == from; }); -} - -bool AdjListGraph::hasEdge(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - for(const Edge& e : data[from]) - if(e.to == to) - return true; - - return false; -} - -weight_t AdjListGraph::getWeight(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - for(const Edge& e : data[from]) - if(e.to == to) - return e.weight; - - return 0; -} - -std::vector<AdjListGraph::Edge> AdjListGraph::adjacent(vertex_t v) const { - return std::vector<Edge>(data[v].begin(), data[v].end()); -} - -size_t AdjListGraph::vertexCount() const { - return data.size(); -}
\ No newline at end of file diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h b/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h deleted file mode 100644 index 40446fd..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/AdjListGraph.h +++ /dev/null @@ -1,50 +0,0 @@ -/* -Тегловен неориентиран граф представен чрез списъци на съседство. - -Предимства: -* Паметта която използваме е вече O(|V| + |E|) -* Вземането на всички съседи е по - бързо - -Недостатъци: -* Да проверим дали има ребро между два върха вече не е O(1) - -*/ -#ifndef ADJ_LIST_GRAPH_IMPL -#define ADJ_LIST_GRAPH_IMPL - -#include<vector> -#include<list> -#include<algorithm> - -class AdjListGraph { - public: - using vertex_t = unsigned int; - using weight_t = unsigned int; - - private: - struct Edge { - vertex_t to; - weight_t weight; - }; - - std::vector<std::list<Edge>> data; - - public: - AdjListGraph(size_t n); - - void addVertex(); - void removeVertex(vertex_t); - bool validVertex(vertex_t) const; - - void addEdge(vertex_t, vertex_t, weight_t); - void removeEdge(vertex_t, vertex_t); - - weight_t getWeight(vertex_t, vertex_t) const; - bool hasEdge(vertex_t, vertex_t) const; - - size_t vertexCount() const; - - std::vector<Edge> adjacent(vertex_t) const; -}; - -#endif
\ No newline at end of file diff --git a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp b/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp deleted file mode 100644 index b0484e0..0000000 --- a/Seminar11/Graph-Impl/AdjacencyListGraph/src.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include<iostream> -#include<list> -#include<algorithm> -#include"AdjListGraph.h" - -int main() { - AdjListGraph g(10); - - g.addEdge(0, 1, 1); - g.addEdge(0, 2, 1); - g.addEdge(0, 3, 1); - g.addEdge(0, 4, 1); - - auto res = g.adjacent(1); - - for(auto i : res) { - std::cout << i.to << " "; - } -}
\ No newline at end of file diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp deleted file mode 100644 index b5835f8..0000000 --- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp +++ /dev/null @@ -1,97 +0,0 @@ -#include"MatrixGraph.h" - -using vertex_t = MatrixGraph::vertex_t; -using weight_t = MatrixGraph::weight_t; - -MatrixGraph::MatrixGraph(size_t v) { - data = std::vector<std::vector<weight_t>>(v, std::vector<weight_t>(v, 0)); -} - -bool MatrixGraph::validVertex(vertex_t v) const { - return v < data.size(); -} - -bool MatrixGraph::adjacent(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - return data[from][to] > 0; -} - -void MatrixGraph::addDirectedEdge(vertex_t from, vertex_t to, weight_t w) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from][to] = w; -} - -void MatrixGraph::addEdge(vertex_t from, vertex_t to, weight_t w) { - addDirectedEdge(from, to, w); - addDirectedEdge(to, from, w); -} - -void MatrixGraph::addVertex() { - for(auto& v : data) - v.push_back(0); - - data.push_back(std::vector<weight_t>()); -} - -void MatrixGraph::removeEdge(vertex_t from, vertex_t to) { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - data[from][to] = 0; -} - -void MatrixGraph::removeVertex(vertex_t v) { - if(!validVertex(v)) - throw "Invalid vertex"; - - data.erase(data.begin() + v); - - for(auto& vertex : data) - vertex.erase(vertex.begin() + v); -} - -weight_t MatrixGraph::getWeight(vertex_t from, vertex_t to) const { - if(!validVertex(from) || !validVertex(to)) - throw "Invalid vertex"; - - return data[from][to]; -} - -std::vector<vertex_t> MatrixGraph::getSuccessors(vertex_t from) const { - if(!validVertex(from)) - throw "Invalid vertex"; - - std::vector<vertex_t> result; - - for (size_t i = 0; i < data.size(); i++) - if(data[from][i] > 0) - result.push_back(i); - - return result; -} - -std::vector<vertex_t> MatrixGraph::getPredecessors(vertex_t from) const { - if(!validVertex(from)) - throw "Invalid vertex"; - - std::vector<vertex_t> result; - - for (size_t i = 0; i < data.size(); i++) - if(data[i][from] > 0) - result.push_back(i); - - return result; -} - -std::vector<vertex_t> MatrixGraph::adjacent(vertex_t from) const { - return getSuccessors(from); -} - - -size_t MatrixGraph::vertexCount() const { - return data.size(); -}
\ No newline at end of file diff --git a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h deleted file mode 100644 index aade1a1..0000000 --- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h +++ /dev/null @@ -1,52 +0,0 @@ -/* -Ориентиран тегловен граф представен чрез матрица на съседство. - -Плюсове: -* Лесна имплементация -* Проверка за ребро, премахване на ребро, добавяне на ребро са 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; - // Same as getSuccessors, here for interface purposes. - std::vector<vertex_t> adjacent(vertex_t) const; -}; - -#endif
\ No newline at end of file diff --git a/Seminar11/README.md b/Seminar11/README.md deleted file mode 100644 index eac0759..0000000 --- a/Seminar11/README.md +++ /dev/null @@ -1,187 +0,0 @@ -# Графи - -## Определение -``` -Граф е наредена двойка G = (V, E), където V e непразно множество, чиито елементи се наричат върхове. Множеството E е крайно множество от ребра. Ребро наричаме двуелементно множество {v1, v2}, където v1 и v2 са елементи на V. -``` -Графите, както подсказва името, могат да бъдат изобразени "графично". Важно е да не се бърка рисунката на граф със самия граф. Един граф може да има безброй много рисунки. - -Примерно, нека V = {v1, v2, v3}, E = {{v1, v2}, {v2, v3}, {v3, v1}}. Този граф може да се нарисува като: - - - -## Видове графи - -### Ориентирани и неориентирани графи -Графът, който видяхте на първия пример е неориентиран. Когато говорим за граф, и не поясним дали е ориентиран или не, става въпрос за неориентиран граф. Понякога е удобно да различаваме дали реброто e от v към u или от u към v. За ребрата на ориентирания граф вече може да си мислим не като за двуелементни множества от върхове а за **наредени двойки от върхове**. - -``` -Припомняне: -Когато имаме двуелементно множество {v1, v2} е вярно, че {v1, v2} = {v2, v1}. При наредените двойки това не е вярно. За v1 != v2 имаме (v1, v2) != (v2, v1). -Наредената двойка (a, b) e множеството {{a}, {a, b}}. Да твърдим, че (a, b) = (b, a) e същото като да твърдим, че {{a}, {a, b}} = {{b}, {a, b}}. Това става единствено когато a = b. -``` - -Сега, разглеждаме ребрата на графа като наредени двойки. -Нека V = {v1, v2, v3} и E = {(v1, v2), (v2, v3), (v2, v1)}. -Този граф би изглеждал така: - - - - - -### Тегловен граф -Често е полезно да "закачим" някакви тегла на ребрата. Примерно, ако върховете на графа представляват някакви забележителности, а ребрата са пътища между тях, теглата могат да представляват времето в минути, което отнема да стигнем от v1 до v2. - -Примерно, това е **рисунка** на тегловен граф: - - - - -Можем да имаме и тегловни ориентирани графи. - - -.png) - -### Мултиграфи -Неформално, в мултиграфа позволяваме да има много ребра с краища едни и същи два върха. Отново може да имаме тегловни и нетегловни мултиграфи. Може да имаме ориентирани и неориентирани мулти графи, нищо не ни спира. - -## Дефиниции -| Понятие | Дефиниция -| :--- | :----: -| Примка в граф | Ребро от типа {v, v} -| Път в граф | Редица от върхове (v_1, v_2, ..., v_n) за които е в сила {v_i, v_{i+1}} е елемент на E. -| Цикъл в граф | Път **p** за който v_1 = v_n се нарича цикъл. -| Прост път | Път **p** e прост ако всички елементи в редицата са уникални. -| Дължина на път | Дължината на пътя е **броя на ребрата в него**. -| Ацикличен граф | Граф, в който няма цикъл. Ако в графът има цикъл то той се нарича цикличен. -| Свързан граф | Граф е свързан ако за всеки два върха u, v има път между u и v. -| Силно свързани върхове | В **ориентиран граф** казваме, че върхове u, v са силно свързани ако съществува път от u до v и от v до u -| Силно свързан граф | Силно свързан граф е **ориентиран** граф, за който всеки два върха са силно свързани. - -# Основни операции върху графи: -Графите (като абстрактен тип данни) трябва да поддържат (част) от следните операции: - -- **addVertex** - добавяне на нов връх -- **removeVertex** - премахване на връх -- **addEdge** - добавяне на ново ребро -- **removeEdge** - премахване на ребро -- **getSuccessors** - взимане на наследниците на връх (при ориентирани графи) -- **getPredecessors** - взимане на предшествениците на връх (при ориентирани графи) -- **adjacent** - взимане на съседните върхове на даден връх (при неориентирани графи) - -# Представяне на графи -Графите намират огромно приложение в програмирането. Ако обаче започнем да представяме граф като множество от върхове и второ множество от двуелементни множества, това представяне би било бавно. - -Ние искаме да решаваме задачи върху графи с компютър. Представете си, че върховете на графа са именувани с етикети от 0 до |V| - 1. - -Наистина, няма значение как именуваме върховете, дали ще е {0, 1..., |V| - 1} дали ще е {v1, v2...} просто имаме нужда от начин, по който да се обръщаме към тях. - -## Матрици на съседство -Нека си представим булева матрица |V|x|V|. Разбрахме, се че имената на върховете са между 0 и |V| - 1. Ако има ребро между v и u то в нашата матрица това ще отбелязваме с true. Ако няма ребро го отбелязваме с false. - -Нека разгледаме матрицата: -``` -{ - {0, 1, 1}, - {1, 0, 1}, - {1, 1, 0} -} -``` -Това е точно матрицата, която представя графът от пример 1, ако си мислим за v1 = 0, v2 = 1, v3 = 2. - -Ако матрицата представя неориентиран граф, то тя е симетрична спрямо главния диагонал. - -Ако матрицата представя ориентиран граф и примерно имаме ребро от 5 към 7, но не и от 7 към 5, ще е вярно, че - -``` -matrix[5][7] = true -matrix[7][5] = false -``` - -Можем да представяме тегловни графи чрез матрица на съседство. Тази матрица вече няма да е булева понеже ще искаме да записваме някъде теглата на ребрата. - -Може да направим матрица от тип int, в която ако matrix[i][j] = 0 нямаме ребро между i и j а в противен случай стойността на matrix[i][j] e теглото на реброто започващо от i и завършващо в j. - -Но какво става ако искаме да имаме ребра с тежест 0? Тогава трябва да изберем друга стойност, която да ни представя липсата на ребро, примерно INT_MIN или INT_MAX. - -Предимствата на това представяне са, че можем да проверим, дали има ребро от който и да е връх до който и да е връх за константно време. Също така за линейно време за някой възел можем да вземем всички негови съседни ребра. - -Проблемът е, че често това представяне заема твърде много памет (O(|V|^2)). Ако графът има твърде много върхове а твърде малко ребра, матрицата ще има много нули (така наречената разредена матрица). Така ще ни се наложи да представяме малко информация с много памет. - -|Операция|Сложност|| -|--|--|--| -|addVertex|O(n)|| -|removeVertex|O(n)|| -|addEdge|O(1)| -|removeEdge|O(1)| -|getSuccessors|O(n)|| -|getPredecessors|O(n)|| - - - -* Тук може да си мислите за A = 0, B = 1 и тн. - -## Списък от списъци -Друг начин е да държим някакъв списък (или масив) от |V| списъка. Вярно е, че списъкът на позиция i съдържа всички наследници на връх i. - -Примерно, графът от пример 1 ще се представи по следния начин: - -``` -0: 1 -> 2 -1: 0 -> 2 -2: 1 -> 2 -``` - -Сега, ако искам да видя дали има ребро между връх i и връх j това е еквивалентно на lists[i].contains(j); - -Тегловни графи можем да представим, като вече списъците не са от числа а от двойки (Връх, Тегло). - - - -* Отново, тук индексацията започва от 1. Без никакъв проблем можем да я направим да започва от 0. - -Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|). - -Част от материалите са взаимствани от [тук](https://github.com/MariaGrozdeva/Data_structures_and_algorithms_FMI/tree/main/Sem_10) - -## BFS -Breadth-first search е сравнително прост алгоритъм за търсене в граф, но върху идеята, която той носи се базират други алгоритми върху графи. Примерно, алгоритъмът на Прим за минимално покриващо дърво, алгоритъмът на Dijkstra за най - къси пътища се базират на идеи подобни на тази на BFS. - -Като вход получаваме граф G = (V, E) и връх s BFS систематично открива всички върхове, които са достижими от s. Чрез него можем да изчислим разстоянието (най - малкия брой ребра) от s до всеки друг връх. Алгоритъма работи за ориентирани и неориентирани графи. - -BFS използва структурата от данни опашка за да работи коректно. Самата идея е следната. Имаме начален връх, той ще бъде първия посетен. Добри кандидати да бъдат посетени след това са неговите съседи. Имаме функция adjacent (за ориентирани графи successors), та знаем кои са те. Добавяме ги в опашката, където чакат да бъдат посетени. След това последователно ги изваждаме от нея, и отново слагаме всички техни непосетени съседи в опашката, където чакат да бъдат посетени. - -Трябва ни обаче някакъв начин чрез който да разбираме дали даден връх е бил посетен. Ако нямаме тази информация зацикляме. С този проблем лесно се справяме правейки масив в който записваме дали даден връх е посетен или не. - -``` -BFS(G = (V, E), s начален връх) - Създай опашка q и добави s вътре. - Създай булев масив visited[0..|V| - 1] със стойности false. - - q.push(s). - - while(!q.empty()) - Нека cVertex е q.top(). - q.pop(). - Посети cVertex. - Добави в q всеки съсед на cVertex, който не е посетен. -``` - -Ако графът не е тегловен BFS може да се използва за намирането на най - къс път между два върха. Припомнете си задача втора от трети семинар и решението ѝ. Задача първа също използва идея, подобна на бфс. - -## DFS -BFS обхожда графа ниво по ниво. DFS използва различна стратегия, наподобяваща обхождането на лабиринт. Вървим по път докато не "стигнем до края на този път" (нямаме накъде да отидем повече). След това се връщаме назад, докато не стигнем връх, който има непосетен съсед. Рекурсивно повтаряме тази стратегия върху непосетения съсед и внимаваме да не повторим връх два пъти. - - - -DFS използва структурата от данни stack за да работи коректно. Важно е да се отбележи, че замяната на опашката със стек в DFS алгоритъма **не влече** кректен DFS. За наше улеснение ще направим функцията рекурсивна и ще използваме системния стек. - -На примера виждаме едно DFS обхождане на граф. - -Може да видите, че след като обхождането приключи, ребрата, които използваме да посетим връх за пръв път образуват дърво. Това до някаква степен е очаквано, DFS не повтаря върхове и открива всички върхове достижими от началния, тоест графа, който ще е обходен ще е свързан. - -DFS посещава всеки връх и всяко ребро точно един път, което води до сложност O(|V| + |E|). - -DFS има много приложения, използва се за намиране на цикъл в граф, топологично сортиране на DAG (directet acyclic graph), търсене на пътища и др. - -Във файла DFS-Additional има интересни/допълнителни неща около DFS. diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp deleted file mode 100644 index 75a6f3d..0000000 --- a/Seminar11/bfs-dfs.cpp +++ /dev/null @@ -1,65 +0,0 @@ -#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& currentVertex : successors) { - if(!visited[currentVertex]) - q.push(currentVertex); - } - } -} - -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); - - DFS(g, 0); -}
\ No newline at end of file diff --git a/Seminar11/media/dfs-example.gif b/Seminar11/media/dfs-example.gif Binary files differdeleted file mode 100644 index 463d476..0000000 --- a/Seminar11/media/dfs-example.gif +++ /dev/null diff --git a/Seminar11/media/dir-graph.png b/Seminar11/media/dir-graph.png Binary files differdeleted file mode 100644 index 5aaefed..0000000 --- a/Seminar11/media/dir-graph.png +++ /dev/null diff --git a/Seminar11/media/graph.png b/Seminar11/media/graph.png Binary files differdeleted file mode 100644 index 194cab6..0000000 --- a/Seminar11/media/graph.png +++ /dev/null diff --git a/Seminar11/media/matrix.png b/Seminar11/media/matrix.png Binary files differdeleted file mode 100644 index a2af53b..0000000 --- a/Seminar11/media/matrix.png +++ /dev/null diff --git a/Seminar11/media/weighted-dirscted-graph (1).png b/Seminar11/media/weighted-dirscted-graph (1).png Binary files differdeleted file mode 100644 index e251ebf..0000000 --- a/Seminar11/media/weighted-dirscted-graph (1).png +++ /dev/null diff --git a/Seminar11/media/weighted-graph.png b/Seminar11/media/weighted-graph.png Binary files differdeleted file mode 100644 index ed5d0b9..0000000 --- a/Seminar11/media/weighted-graph.png +++ /dev/null diff --git a/Seminar11/media/weighted-list.png b/Seminar11/media/weighted-list.png Binary files differdeleted file mode 100644 index 9d795e9..0000000 --- a/Seminar11/media/weighted-list.png +++ /dev/null diff --git a/Seminar11/package.json b/Seminar11/package.json deleted file mode 100644 index e69de29..0000000 --- a/Seminar11/package.json +++ /dev/null |
