Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <list>
- #include <iostream>
- #include <queue>
- #include <stack>
- using namespace std;
- struct Edge {
- int begin;
- int end;
- };
- int main()
- {
- system("chcp 1251");
- system("cls");
- queue<int> Queue;
- stack<Edge> Edges;
- int req;
- Edge e;
- int mas[10][10] = {
- { 0,1,1,0,0,0,0,0,0,1 },
- { 0,0,0,0,0,1,1,0,1,0 },
- { 0,0,0,0,0,0,0,1,0,1 },
- { 0,0,0,0,0,0,0,0,0,0 },
- { 0,0,0,0,0,0,0,0,0,0 },
- { 0,0,0,0,0,0,1,0,0,0 },
- { 0,0,0,0,1,0,0,0,0,0 },
- { 0,0,0,0,0,0,0,0,0,0 },
- { 0,0,0,0,0,0,0,0,0,0 },
- { 0,0,0,1,0,0,1,0,0,0 } };
- int nodes[10]; // вершины графа
- for (int i = 0; i < 10; i++) // исходно все вершины равны 0
- nodes[i] = 0;
- cout << "N = "; cin >> req;req-1;
- Queue.push(0); // помещаем в очередь первую вершину
- while (!Queue.empty())
- {
- int node = Queue.front(); // извлекаем вершину
- Queue.pop();
- nodes[node] = 1; // отмечаем ее как посещенную
- for (int j = 0; j < 10; j++)
- {
- if (mas[node][j] == 1 && nodes[j] == 0)
- { // если вершина смежная и не обнаружена
- Queue.push(j); // добавляем ее в очередь
- nodes[j] = 1; // отмечаем вершину как обнаруженную
- e.begin = node; e.end = j;
- Edges.push(e);
- if (node == req) break;
- }
- }
- cout << node << endl; // выводим номер вершины
- }
- cout << "Путь до вершины " << req << endl;
- cout << req + 1;
- while (!Edges.empty()) {
- e = Edges.top();
- Edges.pop();
- if (e.end == req) {
- req = e.begin;
- cout << " <- " << req ;
- }
- }
- cin.get(); cin.get();
- return 0;
- }
Add Comment
Please, Sign In to add comment