From aaa6a2375d3621828f062d5f4f09ed8628addd7b Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 4 Apr 2021 20:49:48 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=B8=D0=BB=20=D0=B0?= =?UTF-8?q?=D0=BB=D0=B3=D0=BE=D1=80=D0=B8=D1=82=D0=BC=20=D0=9F=D1=80=D0=B8?= =?UTF-8?q?=D0=BC=D0=B0=20=D0=B2=20=D0=B0=D0=BB=D0=B3=D0=BE=D1=80=D0=B8?= =?UTF-8?q?=D1=82=D0=BC=D0=B0=D1=85=20=D0=BD=D0=B0=20=D0=B3=D1=80=D0=B0?= =?UTF-8?q?=D1=84=D0=B0=D1=85?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- graphs-algo/Makefile | 10 ++-- graphs-algo/task2.cpp | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 154 insertions(+), 5 deletions(-) create mode 100644 graphs-algo/task2.cpp (limited to 'graphs-algo') 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 +#include +#include +#include + +using namespace std; + +typedef vector> 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(n, k); + (*g)[i] = *v; + } +} + +graph prim(graph g, int n) +{ + graph mst(n); + init(&mst, n, -1); + + vector 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; +} -- cgit v1.2.3