none
поиск мостов в графе RRS feed

  • Вопрос

  • Скиньте пожалсто где можно прочесть про графы, а именно поиск мостов в графе.если есть возможность скиньте плиз кодовый пример!  
    21 декабря 2010 г. 20:17

Ответы

  • нашёл год в учебнике, а поскольку в графах не разбираюсь не знаю даж каким переменным что присваивать!!!

     

    int d[MAXN], low[x], counter;

    void dfs(int x, int parent) {
      int kids = 0;
      d[x] = low[x] = counter++;
      для каждой вершины y смежной с x {
        if (y != parent) {
          if (d[y] == 0) {
            kids++;
            dfs(y, x);
            if (low[y] == d[y]) {
              // ребро (x,y) - мост
            }
            low[x] = min(low[x], low[y]);
          } else {
            // обратное ребро
            low[x] = min(low[x], d[y]);
          }
        }
      }

      if (d[x] == low[x] && (parent != -1 || kids >= 2)) {
        // вершина x - точка сочленения
      }
    }

    memset(d, 0, sizeof(d));
    counter = 1;
    for (int x = 0; x < N; x++) if (d[x] == 0) dfs(x, -1);

    • Помечено в качестве ответа Gomerchik 22 декабря 2010 г. 14:48
    22 декабря 2010 г. 9:07

Все ответы

  • Ну, например, посмотрите Поиск мостов , вообще вы не совсем по адресу, это девелоперский форум и тут задаются вопросы касательно разработки

    Для связи [mail]
    22 декабря 2010 г. 7:43
  • нашёл год в учебнике, а поскольку в графах не разбираюсь не знаю даж каким переменным что присваивать!!!

     

    int d[MAXN], low[x], counter;

    void dfs(int x, int parent) {
      int kids = 0;
      d[x] = low[x] = counter++;
      для каждой вершины y смежной с x {
        if (y != parent) {
          if (d[y] == 0) {
            kids++;
            dfs(y, x);
            if (low[y] == d[y]) {
              // ребро (x,y) - мост
            }
            low[x] = min(low[x], low[y]);
          } else {
            // обратное ребро
            low[x] = min(low[x], d[y]);
          }
        }
      }

      if (d[x] == low[x] && (parent != -1 || kids >= 2)) {
        // вершина x - точка сочленения
      }
    }

    memset(d, 0, sizeof(d));
    counter = 1;
    for (int x = 0; x < N; x++) if (d[x] == 0) dfs(x, -1);

    • Помечено в качестве ответа Gomerchik 22 декабря 2010 г. 14:48
    22 декабря 2010 г. 9:07