diff options
| -rw-r--r-- | graphs-algo/Makefile | 10 | ||||
| -rw-r--r-- | graphs-algo/task2.cpp | 149 |
2 files changed, 154 insertions, 5 deletions
diff --git a/graphs-algo/Makefile b/graphs-algo/Makefile index 5343597..44bfcbf 100644 --- a/graphs-algo/Makefile +++ b/graphs-algo/Makefile @@ -6,17 +6,17 @@ task1: $(COMPILE) -o task.out task1.cpp test1: task1 @printf "4\n4\n1 2 1\n2 3 1\n3 4 1\n4 1 1\n4\n2" | ./task.out - @printf "Answer: \n" + @printf "Answer: 4 -> 1 -> 2\n" @printf "4\n4\n1 2 1\n2 3 5\n3 4 1\n4 1 2\n2\n3" | ./task.out - @printf "Answer: \n" + @printf "Answer: 2 -> 1 -> 4 -> 3\n" @printf "3\n1\n1 2 1\n1 2" | ./task.out - @printf "Answer: \n" + @printf "Answer: 1 -> 2\n" task2: $(COMPILE) -o task.out task2.cpp test2: task2 - @printf "" | ./task.out - @printf "Answer: \n" + @printf "6\n7\n1 2 4\n2 3 2\n3 5 4\n5 4 1\n4 6 2\n6 2 5\n1 3 3" | ./task.out + @printf "7\n7\n1 2 4\n2 3 2\n3 5 4\n5 4 1\n4 6 2\n6 2 5\n1 3 3" | ./task.out clean: rm -f task.out *.zip diff --git a/graphs-algo/task2.cpp b/graphs-algo/task2.cpp new file mode 100644 index 0000000..5321ff9 --- /dev/null +++ b/graphs-algo/task2.cpp @@ -0,0 +1,149 @@ +#include<iostream> +#include<vector> +#include<algorithm> +#include<iomanip> + +using namespace std; + +typedef vector<vector<int>> graph; +const int INF = int(1e9); + +void print(graph g) +{ + for (int i = 0; i < int(g.size()); ++i) + { + cout << i + 1 << ": "; + for (int j = 0; j < int(g[i].size()) - 1; ++j) + cout << g[i][j] + 1 << ", "; + + if (g[i].size() > 0) + cout << g[i].back() + 1; + else + cout << "нет смежных вершин"; + + cout << ";" << endl; + } +} + +void print2D(graph g) +{ + int n = int(g.size()); + for (int i = 0; i < n; ++i) + { + for (int j = 0; j < n - 1; ++j) + cout << setw(5) << g[i][j] << ","; + cout << setw(5) << g[i][n - 1] << endl; + } +} + +// Написание данного алгоритма сильно упрощается, если использовать +// матрицу смежности, а не список смежности. +void init(graph *g, int n, int k) +{ + for (int i = 0; i < n; ++i) + { + auto v = new vector<int>(n, k); + (*g)[i] = *v; + } +} + +graph prim(graph g, int n) +{ + graph mst(n); + init(&mst, n, -1); + + vector<int> u(n, 0); + u[0] = 1; + while (true) + { + // Ищем ребро минимального веса с начальной вершиной среди уже + // задействованных, а конечной - среди незадействованных + int m = INF; + int q = -1; + int p = -1; + + // v - уже задействованная вершина + for (int v = 0; v < n; ++v) + { + if (u[v] == 0) continue; + + // i - незадействованная вершина + for (int i = 0; i < n; ++i) + { + if (i == v || u[i] == 1 || g[v][i] == -1) continue; + + if (g[v][i] < m) + { + q = v; + p = i; + m = g[v][i]; + } + } + } + + if (q == -1) break; + if (p == -1) break; + + mst[q][p] = m; + mst[p][q] = m; + u[p] = 1; + } + + // Если количество рёбер (т.е. элементов матрицы, не равных -1) не равно + // n - 1, то граф является несвязным и минимальное остовное дерево + // не может быть построено. + int cnt = 0; + for (int i = 0; i < n; ++i) + for (int j = 0; j < n; ++j) + if (mst[i][j] != -1) ++cnt; + + if (cnt / 2 != n - 1) mst.clear(); + + return mst; +} + +int main() +{ + cout << "Введите количество вершин: "; + int n; + cin >> n; + + cout << "Введите количество рёбер: "; + int k; + cin >> k; + + graph g(n); + init(&g, n, -1); + + cout << "o----------------------o" << endl; + cout << "| Нумерация вершин с 1 |" << endl; + cout << "o----------------------o" << endl; + + cout << "Введите рёбра (неориентированные, взвешенные):" << endl; + for (int i = 0; i < k; ++i) + { + int a, b, c; + cin >> a >> b >> c; + a--; + b--; + g[a][b] = c; + g[b][a] = c; + + g[a][a] = 0; + g[b][b] = 0; + } + + cout << "Введённый граф:" << endl; + print2D(g); + + graph mst = prim(g, n); + if (mst.size() > 0) + { + cout << "Построено минимальное остовное дерево:" << endl; + print2D(mst); + } + else + cout << "Минимальное остовное дерево не может быть построено" << endl; + + return 0; +} |