Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar11
diff options
context:
space:
mode:
Commit63f4cb943f81c257e78ebeef828edbc04e78264b (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 15:07:15 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-01-04 15:07:15 +0200
Files2a9972460ab6719f392f56f84f1edc2f568b85b8 /Seminar11
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.tar
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.tar.gz
Data-structures-and-algorithms-63f4cb943f81c257e78ebeef828edbc04e78264b.zip
Parentfcb06959d4425310eadee643f3fab68604063f51 (diff)
Add seminar 12
6 files changed, 254 insertions, 4 deletions
-rw-r--r--Seminar11/DFS-Additional.cpp200
-rw-r--r--Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp5
-rw-r--r--Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h2
-rw-r--r--Seminar11/README.md44
-rw-r--r--Seminar11/bfs-dfs.cpp7
-rw-r--r--Seminar11/media/dfs-example.gifbin0 -> 611116 bytes
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<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/MatrixGraph/MatrixGraph.cpp b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
index bf155a1..b5835f8 100644
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.cpp
@@ -87,6 +87,11 @@ std::vector<vertex_t> MatrixGraph::getPredecessors(vertex_t from) const {
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
index 1e4ec71..aade1a1 100644
--- a/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
+++ b/Seminar11/Graph-Impl/MatrixGraph/MatrixGraph.h
@@ -45,6 +45,8 @@ class MatrixGraph {
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
index cf0d36c..7f28913 100644
--- a/Seminar11/README.md
+++ b/Seminar11/README.md
@@ -142,4 +142,46 @@ matrix[7][5] = false
Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|).
-Част от материалите са взаимствани от [тук](https://github.com/MariaGrozdeva/Data_structures_and_algorithms_FMI/tree/main/Sem_10) \ No newline at end of file
+Част от материалите са взаимствани от [тук](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 използва различна стратегия, наподобяваща обхождането на лабиринт. Вървим по път докато не "стигнем до края на този път" (нямаме накъде да отидем повече). След това се връщаме назад, докато не стигнем връх, който има непосетен съсед. Рекурсивно повтаряме тази стратегия върху непосетения съсед и внимаваме да не повторим връх два пъти.
+
+![](media/dfs-example.gif)
+
+DFS използва структурата от данни stack за да работи коректно. Важно е да се отбележи, че замяната на опашката със стек в DFS алгоритъма **не влече** кректен DFS. За наше улеснение ще направим функцията рекурсивна и ще използваме системния стек.
+
+На примера виждаме едно DFS обхождане на граф.
+
+Може да видите, че след като обхождането приключи, ребрата, които използваме да посетим връх за пръв път образуват дърво. Това до някаква степен е очаквано, DFS не повтаря върхове и открива всички върхове достижими от началния, тоест графа, който ще е обходен ще е свързан.
+
+DFS посещава всеки връх и всяко ребро точно един път, което води до сложност O(|V| + |E|).
+
+DFS има много приложения, използва се за намиране на цикъл в граф, топологично сортиране на DAG (directet acyclic graph), търсене на пътища и др.
+
+Във файла DFS-Additional има интересни/допълнителни неща около DFS. \ No newline at end of file
diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
index 19ef1b9..75a6f3d 100644
--- a/Seminar11/bfs-dfs.cpp
+++ b/Seminar11/bfs-dfs.cpp
@@ -49,9 +49,10 @@ void DFS(const AdjListGraph& g, AdjListGraph::vertex_t start) {
DFSRec(visited, g, start);
}
+
int main() {
- MatrixGraph g(5);
- // AdjListGraph g(5);
+ // MatrixGraph g(5);
+ AdjListGraph g(5);
g.addEdge(0, 2, 1);
g.addEdge(0, 3, 1);
g.addEdge(0, 1, 1);
@@ -60,5 +61,5 @@ int main() {
g.addEdge(3, 4, 1);
g.addEdge(1, 3, 1);
- BFS(g, 0);
+ DFS(g, 0);
} \ No newline at end of file
diff --git a/Seminar11/media/dfs-example.gif b/Seminar11/media/dfs-example.gif
new file mode 100644
index 0000000..463d476
--- /dev/null
+++ b/Seminar11/media/dfs-example.gif
Binary files differ