Но "от большего к меньшему" - недостаточное условие для зацикливания.
Короче, вот как я сделал. Нашёл похожий урок на хабре. Не знаю, как быстродействие, но вроде работает. Нужно только пронумеровать все вершины графа в произвольном порядке и для каждой написать, к каким вершинам от неё имеются переходы. Этот массив скармливаем функции и получаем ответ, имеются в графе циклы или нет.
код 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;
}
А вот картинка, по которой я вершины нумеровал. Можно поэкспериментировать.