From 5b28380e3650dd030fd5f5cd2b95749535afd884 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <saintruler@gmail.com>
Date: Tue, 30 Mar 2021 10:46:20 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=B8=D0=BB=20=D0=BF?=
 =?UTF-8?q?=D1=8F=D1=82=D1=83=D1=8E=20=D0=B7=D0=B0=D0=B4=D0=B0=D1=87=D1=83?=
 =?UTF-8?q?=20=D0=B2=20=D0=B3=D1=80=D0=B0=D1=84=D0=B0=D1=85?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 graphs/Makefile  |   6 ++-
 graphs/task5.cpp | 131 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 135 insertions(+), 2 deletions(-)
 create mode 100644 graphs/task5.cpp

(limited to 'graphs')

diff --git a/graphs/Makefile b/graphs/Makefile
index d20a34b..b61c5fb 100644
--- a/graphs/Makefile
+++ b/graphs/Makefile
@@ -33,8 +33,10 @@ test4: task4
 task5:
 	$(COMPILE) -o task.out task5.cpp
 test5: task5
-	@printf "" | ./task.out
-	@printf "Answer: \n"
+	@printf "6\n9\n1 2\n2 3\n3 5\n5 6\n1 4\n4 6\n1 3\n3 5\n5 6\n1 6" | ./task.out
+	@printf "Answer: 1 -> 4 -> 6\n"
+	@printf "3\n1\n1 2\n1 3" | ./task.out
+	@printf "Answer: none\n"
 
 task6:
 	$(COMPILE) -o task.out task6.cpp
diff --git a/graphs/task5.cpp b/graphs/task5.cpp
new file mode 100644
index 0000000..7fc9652
--- /dev/null
+++ b/graphs/task5.cpp
@@ -0,0 +1,131 @@
+#include<iostream>
+#include<stdio.h>
+#include<vector>
+#include<queue>
+#include<algorithm>
+
+using namespace std;
+
+typedef vector<vector<int>> graph;
+
+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 bfs( int a,
+          int b,
+          graph g,
+          vector<int> *paths,
+          vector<int> *used, 
+          queue<int> *q )
+{
+    (*used)[a] = 1;
+    q->push(a);
+    while (q->size() > 0)
+    {
+        int y = q->front();
+        q->pop();
+        for (int i = 0; i < int(g[y].size()); ++i)
+        {
+            int node = g[y][i];
+            if ((*used)[node] == 0)
+            {
+                (*used)[node] = 1;
+                if ((*paths)[node] == -1)
+                    (*paths)[node] = y;
+                q->push(node);
+
+                if(node == b) return;
+            }
+        }
+    }
+}
+
+void bfs(int a, int b, graph g, vector<int> *path)
+{
+    int n = int(g.size());
+    vector<int> used(n, 0);
+    queue<int> q;
+    vector<int> paths(n, -1);
+    bfs(a, b, g, &paths, &used, &q);
+    
+    int cur = b;
+    while (true)
+    {
+        path->push_back(cur);
+        if (cur == a) break;
+        if (cur == -1)
+        {
+            path->clear();
+            break;
+        }
+        cur = paths[cur];
+    }
+    reverse(path->begin(), path->end());
+}
+
+
+int main()
+{
+    cout << "Введите количество вершин: ";
+    int n;
+    cin >> n;
+
+    cout << "Введите количество рёбер: ";
+    int k;
+    cin >> k;
+
+    graph g(n);
+    
+    cout << "o----------------------o" << endl;
+    cout << "| Нумерация вершин с 1 |" << endl;
+    cout << "o----------------------o" << endl;
+
+    cout << "Введите рёбра (неориентированные):" << endl;
+    for (int i = 0; i < k; ++i)
+    {
+        int a, b;
+        cin >> a >> b;
+        a--;
+        b--;
+        g[a].push_back(b);
+        g[b].push_back(a);
+    }
+
+    cout << "Введённый граф:" << endl;
+    print(g);
+
+    cout << "Введите вершины, между которыми нужно найти путь:" << endl;
+    int a, b;
+    cin >> a >> b;
+    a--;
+    b--;
+    vector<int> path;
+    bfs(a, b, g, &path);
+
+    if (path.size() > 0)
+    {
+        printf("Найден путь из вершины %i в вершину %i:\n", a + 1, b + 1);
+        for (int i = 0; i < int(path.size()) - 1; ++i)
+            cout << path[i] + 1 << " -> ";
+
+        cout << path.back() + 1 << endl;
+    }
+    else
+        printf("Путь из вершины %i в вершину %i не найден.\n", a + 1, b + 1);
+
+    return 0;
+}
-- 
cgit v1.2.3