Advertisement
r1411

Обход в глубину (по матрице смежности)

Jun 14th, 2021
782
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int a[100][100] = { 0 };    // Матрица смежности
  5. int mark[100] = { 0 };      // Метки посещенности вершин
  6.  
  7.  
  8. void dfs(int v, int n) {
  9.     mark[v] = 1;
  10.     cout << "Посетили вершину " << v << endl;
  11.     for (int i = 1; i <= n; i++) {
  12.         // Если есть дуга v->i, а i - не посещенная вершина, запускаем dfs от i.
  13.         if (a[v][i] == 1 && mark[i] == 0)
  14.             dfs(i, n);
  15.     }
  16. }
  17.  
  18.  
  19. void main() {
  20.     setlocale(LC_ALL, "Russian");
  21.     int n;
  22.     cout << "Введите колво вершин" << endl;
  23.     cin >> n;
  24.  
  25.     int v1, v2;
  26.     cout << "Вводите смежные вершины (формат: <v1> <v2>, окончание ввода - 0 0)" << endl;
  27.     cin >> v1 >> v2;
  28.     while (v1 != 0 && v2 != 0) {
  29.         a[v1][v2] = 1;
  30.         cin >> v1 >> v2;
  31.     }
  32.  
  33.     for (int i = 1; i <= n; i++)
  34.         if(mark[i] == 0)
  35.             dfs(i, n);
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement