From 86dbd52947958c8ce263cfc3cb275e79aed6661d Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Wed, 21 Dec 2022 18:52:58 +0200 Subject: fix typos --- Seminar11/README.md | 9 +++++++++ Seminar11/bfs-dfs.cpp | 6 +++--- 2 files changed, 12 insertions(+), 3 deletions(-) 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); } } } -- cgit v1.3.1-23-gd82d