diff options
fix typos
2 files changed, 12 insertions, 3 deletions
| -rw-r--r-- | Seminar11/README.md | 9 | ||||
| -rw-r--r-- | Seminar11/bfs-dfs.cpp | 6 |
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}}. Този граф може да се нарисува като: +  ## Видове графи @@ -24,15 +25,21 @@ Нека V = {v1, v2, v3} и E = {(v1, v2), (v2, v3), (v2, v1)}. Този граф би изглеждал така: +  + ### Тегловен граф Често е полезно да "закачим" някакви тегла на ребрата. Примерно, ако върходете на графа представляват някакви забележителности, а ребрата са пътища между тях, теглата могат да представляват времето в минути, което отнема да стигнем от v1 до v2. Примерно, това е **рисунка** на тегловен граф: + +  Можем да имаме и тегловни ориентирани графи. + + .png) ### Мултиграфи @@ -111,6 +118,7 @@ matrix[7][5] = false |getPredecessors|O(n)||  + * Тук може да си мислите за A = 0, B = 1 и тн. ## Списък от списъци @@ -129,6 +137,7 @@ matrix[7][5] = false Тегловни графи можем да представим, като вече списъците не са от числа а от двойки (Връх, Тегло).  + * Отново, тук индексацията започва от 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); } } } |
