From 63f4cb943f81c257e78ebeef828edbc04e78264b Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 4 Jan 2023 15:07:15 +0200 Subject: Add seminar 12 --- Seminar11/DFS-Additional.cpp | 200 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 200 insertions(+) create mode 100644 Seminar11/DFS-Additional.cpp (limited to 'Seminar11/DFS-Additional.cpp') diff --git a/Seminar11/DFS-Additional.cpp b/Seminar11/DFS-Additional.cpp new file mode 100644 index 0000000..a5022e3 --- /dev/null +++ b/Seminar11/DFS-Additional.cpp @@ -0,0 +1,200 @@ +// Малко допълнителни неща покрай дфс ако ви е интересно. +#include +#include"Graph-Impl/AdjacencyListGraph/AdjListGraph.h" +#include"Graph-Impl/MatrixGraph/MatrixGraph.h" +#include +#include + +using std::vector; +using vertex_t = AdjListGraph::vertex_t; // Типа представящ връх в графа + +class DFSExamples { +private: + vector in; + vector out; + vector 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 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> result(g.vertexCount()); + + for (vertex_t i = 0; i < g.vertexCount(); i++) + result[i] = {i, out[i]}; + + auto comp = [](std::pair& fst, std::pair& 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 -- cgit v1.3.1-26-gb76a