Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Нужен алгоритм поиска в графе вершины......


Автор: hiHo 13.11.2005, 16:56

Нужен алгоритм поиска в графе вершины из которой достижимы все вершины.
(BFS по каждой вершине не предлагать).

Автор: yaja 16.11.2005, 21:10
Делаешь DFS от любой вершины, запоминая для каждой из низ время, когда ты из неё выходишь
После чего проверяешь(есче DFS) вершину с самым большим временем выхода. ИМХО заработает smile

Автор: eskaflone 18.11.2005, 20:57
судя по всему граф ориентированный.
алгоритм за О(n^3) устроит?

Автор: yaja 18.11.2005, 21:44
Цитата(eskaflone @ 18.11.2005, 20:57)
алгоритм за О(n^3) устроит?

Ну наверное ты предложишь DFS или BFS от каждой вершины, ну или модернизацию этого. А то, что я предложил работает за O(E + V), т.е в худшем случае (если граф представлен в виде матрици) за O(n*n)

Автор: eskaflone 18.11.2005, 23:37
1)время выхода это количество посещенных вершин?
2)DFS от любой вершины или от всех?

опиши алгоритм подробнее.
ЗЫ
DFS - поиск в глубину?

Автор: esperant0 19.11.2005, 12:09
Цитата(yaja @ 16.11.2005, 21:10)
Делаешь DFS от любой вершины, запоминая для каждой из низ время, когда ты из неё выходишь
После чего проверяешь(есче DFS) вершину с самым большим временем выхода. ИМХО заработает smile

может быть приведете док-во, а то фраза имхо заработает, лишает надежд.

Автор: poor_yorik 20.11.2005, 14:53
Есть такой умный метод. smile
Находишь все компоненты сильной связности графа Г.
Далее строишь граф Г1 у которого:
! вершинам соответствуют компоненты сильной связности графа Г.
! ребро (а, в) означает, что из соответствующей компоненты сильной связности а можно попасть в компоненту в.
Если Г1 связный и у него одна вершина Y, в которую не входит ни одно ребро, то задача имеет решение. Ответом будут все вершины компоненты сильной связности, которая соотвествовала вершине Y.
Умный метод. Но легче ничего не нашлось. smile

Автор: yaja 20.11.2005, 20:42
Код

void DFS() {
  for (int i = 1; i <= n; i++) { 
    color[i] = WHITE
    way[i] = 0;
  }

  time = 1;
  
  for (int i = 1; i <= n; i++) {
    if (color[i] == WHITE) {
      dfs(i);
    }
  }
}
void dfs(int u) { // поиск в глубину
  color[u] = GRAY;
  for (для всех смежных с u вершин v) {
    if (color[v] == WHITE) dfs(v);
  }
  way[time++] = u; // запоминаем последовательность посещения вершин
  // или leave[u] = time++; это то, что я имел ввиду время выхода
  // запоминать way - лучше, т.к. иначе в нем придется находить максимальный элемен, что стоит времени
}

// return номер вершины от которой достижимы все
int find() {
  DFS();
  int u = way[n]; // если в графе и есть вершина от которой достижимы все, то это несомненно эта
  // проверим, достижимы ли остальный вершины от этой
  for (int i = 1; i <= n; i++) { 
    color[i] = WHITE
  }
  time = 1;
  dfs(u);

  for (int i = 1; i<= n; i++) 
    if (color[i] == WHITE) return -1; // нет требуемой вершины
  retrun u;
}


Заметим, что если из а - достижимы все вершины, то и из любой в, из которой достижима а, будут достижимы все вершины графа. Тогда из свойств dfs'а и из некоторых интуитивных соображений smile следует, что проверять надо только последнюю вершину. Я не знаю как точно это описать, но рассуждения как в топологической сортировке графа smile


poor_yorik Твой метод будет работать только на неориентированном графе (а насколько я понял граф ориентированный, иначе можно было бы только один раз запустить dfs) На ориентированном графе он работать не будет. Вот пример(граф задан списком ребер: первая вершина - начало ребра)
0 1
1 2
В нем три компоненты сильной связности, поэтому твой метод выдаст, что требуемой вершины не существует, а на самом деле такая вершина сушествует - 0 вершина

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)