Добавил алгоритм Прима в алгоритмах на графах

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;
+}