StarCraft FOREVER - Показать сообщение отдельно - Тема для волосатых мужиков (задача с графом)
Показать сообщение отдельно
Старый 19.07.2011, 18:41   #5
uti
Местный
 
Аватар для uti
 
Регистрация: 16.06.2004
Сообщений: 3,753
Нарушения: 14
ICQ:
Но "от большего к меньшему" - недостаточное условие для зацикливания.

Короче, вот как я сделал. Нашёл похожий урок на хабре. Не знаю, как быстродействие, но вроде работает. Нужно только пронумеровать все вершины графа в произвольном порядке и для каждой написать, к каким вершинам от неё имеются переходы. Этот массив скармливаем функции и получаем ответ, имеются в графе циклы или нет.

код javascript:
Код:
var edges = [
  [1],        // из 0
  [2],        // из 1
  [3],        // из 2
  [4,15],     // из 3
  [],         // из 4
  [8],        // из 5
  [7],        // из 6
  [10],       // из 7
  [10],       // из 8
  [],         // из 9
  [9],        // из 10
  [5,12],     // из 11
  [1],        // из 12 (!)
  [11],       // из 13
  [6],        // из 14
  [13,14]     // из 15
];

// true если петель нет, false если есть
alert(checkGraph(edges));

function checkGraph(edges) {
  var n = edges.length;
  var clr = new Array(n);
  var dfs = function(v) {
    if (clr[v] == 1) return true;
    if (clr[v] == 2) return false;
    clr[v] = 1;
    for (var i = 0; i < edges[v].length; i++) {
      if (dfs(edges[v][i])) return true;
    }
    clr[v] = 2;
    return false;
  };
  for (var i = 0; i < n; i++) {
    if (dfs(i)) return false;
  }
  return true;
}
А вот картинка, по которой я вершины нумеровал. Можно поэкспериментировать.

uti вне форума   Ответить с цитированием