Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit86dbd52947958c8ce263cfc3cb275e79aed6661d (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2022-12-21 18:52:58 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2022-12-21 18:52:58 +0200
Files48170b3f666ca6611a36e2d542399aeec68504de
Data-structures-and-algorithms-86dbd52947958c8ce263cfc3cb275e79aed6661d.tar
Data-structures-and-algorithms-86dbd52947958c8ce263cfc3cb275e79aed6661d.tar.gz
Data-structures-and-algorithms-86dbd52947958c8ce263cfc3cb275e79aed6661d.zip
Parent750de18faa33ae862a3348a6679f32e1517a3d4b (diff)
fix typos
2 files changed, 12 insertions, 3 deletions
-rw-r--r--Seminar11/README.md9
-rw-r--r--Seminar11/bfs-dfs.cpp6
diff --git a/Seminar11/README.md b/Seminar11/README.md
index d572d6e..bd320a7 100644
--- a/Seminar11/README.md
+++ b/Seminar11/README.md
@@ -7,6 +7,7 @@
Графите, както подсказва името, могат да бъдат изобразени "графично". Важно е да не се бърка рисунката на граф със самия граф. Един граф може да има безброй много рисунки.
Примерно, нека V = {v1, v2, v3}, E = {{v1, v2}, {v2, v3}, {v3, v1}}. Този граф може да се нарисува като:
+
![](media/graph.png)
## Видове графи
@@ -24,15 +25,21 @@
Нека V = {v1, v2, v3} и E = {(v1, v2), (v2, v3), (v2, v1)}.
Този граф би изглеждал така:
+
![](media/dir-graph.png)
+
### Тегловен граф
Често е полезно да "закачим" някакви тегла на ребрата. Примерно, ако върходете на графа представляват някакви забележителности, а ребрата са пътища между тях, теглата могат да представляват времето в минути, което отнема да стигнем от v1 до v2.
Примерно, това е **рисунка** на тегловен граф:
+
+
![](media/weighted-graph.png)
Можем да имаме и тегловни ориентирани графи.
+
+
![](media/weighted-dirscted-graph%20(1).png)
### Мултиграфи
@@ -111,6 +118,7 @@ matrix[7][5] = false
|getPredecessors|O(n)||
![](media/matrix.png)
+
* Тук може да си мислите за A = 0, B = 1 и тн.
## Списък от списъци
@@ -129,6 +137,7 @@ matrix[7][5] = false
Тегловни графи можем да представим, като вече списъците не са от числа а от двойки (Връх, Тегло).
![](media/weighted-list.png)
+
* Отново, тук индексацията започва от 1. Без никакъв проблем можем да я направим да започва от 0.
Предимството на тази реализация е, че бързо можем да добавяме върхове и ребра. Също така паметта ни вече не е O(|V|^2) а O(|V| + |E|). \ No newline at end of file
diff --git a/Seminar11/bfs-dfs.cpp b/Seminar11/bfs-dfs.cpp
index a19abcd..19ef1b9 100644
--- a/Seminar11/bfs-dfs.cpp
+++ b/Seminar11/bfs-dfs.cpp
@@ -23,9 +23,9 @@ void BFS(const MatrixGraph& g, MatrixGraph::vertex_t start) {
auto successors = g.getSuccessors(current);
- for(const auto& edge : successors) {
- if(!visited[edge])
- q.push(edge);
+ for(const auto& currentVertex : successors) {
+ if(!visited[currentVertex])
+ q.push(currentVertex);
}
}
}