Доброго времени суток!
Понадобилось реализовать сабж для своего проекта, но исходников на JavaScript найти не удалось, может плохо искал, не суть, пришлось переработать имеющийся на паскале (брр…) с некоторой доработкой. Первая часть функции по сути подготовка исходных данных для второй части (самого алгоритма). И вот что вышло:
Топологическая сортировка
-
-
/**
-
Topological sorting algorithm
-
http://algolist.manual.ru/sort/top_sort.php
-
http://en.wikipedia.org/wiki/Topological_sorting
-
Sample:
-
-
var relations = {
-
'a': ['b','d','c','e'],
-
'b': ['d'],
-
'c': ['d', 'e'],
-
'd': ['e'],
-
'e': []
-
}
-
-
alert(tsort(relations));
-
-
Or cyclic:
-
-
relations['e']=['a']
-
try{
-
tsort(relations)
-
}catch(e){
-
alert(e);
-
}
-
*/
-
-
function tsort(relations){
-
-
var l=1, vert=[], edge=[], result={};
-
var n = 0, edgeCount = [];
-
var nullVert = [], nullVertName='null';
-
-
for(var key in relations)
-
{
-
n++;
-
var i;
-
for(i=0;relations[key][i]!=undefined; i++){}
-
edgeCount[key]=i;
-
nullVert.push(key);
-
while(edgeCount[nullVertName]!=undefined) nullVertName+='_';
-
}
-
-
edge[l]=1;
-
vert[l]=nullVertName;
-
relations[nullVertName] = nullVert;
-
-
for(;(l==1 && edge[l]==n+1)!==true;)
-
{
-
if(l>n) throw "Cyclic graph detected.";
-
-
if(edge[l]==edgeCount[vert[l]]+1)
-
{
-
result[vert[l]]=true;
-
l–; edge[l]++;
-
} else {
-
lastvert = relations[vert[l]][edge[l]-1];
-
if(result[lastvert])
-
edge[l]++;
-
else {
-
l++; vert[l]=lastvert; edge[l]=1;
-
}
-
}
-
}
-
var order = [];
-
for(var key in result)
-
order.push(key);
-
return order;
-
}
-
-
var relations = {
-
'a': ['b','d','c','e'],
-
'b': ['d'],
-
'c': ['d', 'e'],
-
'd': ['e'],
-
'e': []
-
}
-
-
alert(tsort(relations));
P.S. Подробнее о его работе смотрите здесь, теория здесь.
Source code
Оставить комментарий