拓扑排序原理分析及js实现
1. 偏序和全序的概念
1.1. 偏序
设R是集合A上的⼀个⼆元关系，若R满⾜下列三个性质则称R为A上的偏序关系
⾃反性：对任意x∈A，有<x,x>∈R
反对称性：对任意的x,y∈A，如果<x,y>∈R，且<y,x>∈R，则必有x=y
传递性：对任意x,y,z∈A，若<x,y>∈R,<y,z>∈R，则必有<x,z>∈R
通俗解释：⾃然数之间的"⼤于等于"是⼀个偏序关系，例如⾃然数的⼀个⼦集A={1,2,3}
"⼤于等于"的⼀个⼦集R={<1,1>,<2,2>,<3,3>,<3,2>,<2,1>,<3,1>}对于⾃反的解释是1=1,2=2,3=3；对于反对称性，<3,2>,<2,1>,<3,1>∈R，但关系R中不存在元素<2,3>,<1,2><1,3>因为2<3,1<2,1<3，对于传递<3,2>,<2,1>∈R即3>2,2>1所以3>1即<3,1>∈R
1.2. 全序
全序是偏序的⼀个⼦集，即集合中任意两个元素之间都有明确的"序"的关系也就是下⾯的性质
完全性：集合中任意两个元素之间都有明确的"序"的关系，由此可见完全性包含了⾃反性，任意就包含了元素和元素⾃⼰
通俗解释：是偏序但不是全序，设集合A={1,2,3,b},b=2i+1；由于b是⼀个复数，所以其它的三个元素都不可以和它来⽐较⼤⼩
1.3. 算法的稳定性
如果我们要对下列数组的元素按照index的⼤⼩进⾏排序 [{id:a,index:1},{id:b,index:1},{id:c,index:2}]，我们设第⼀个为A，第⼆个为B，第三个为C, 我们应该如何确定A和B之间的顺序呢？
由于A，B的index值相同，但A和B确实是不同的元素，因此我们⽆法确定他们的先后顺序，即A和B不可⽐较，所以在A，B，C三个元素组成的关系不具备全序关系。但是⼀个偏序关系，如果我们默认，先出现的排在前⾯，那么我们就能⽐较A，B的关系了。我们排序就有C,A,B
稳定的算法：是对于存在上述情况的元素总能按照元素出现的先后顺序排列的算法
不稳定的算法：是对于上述情况，不能保证先出现的排在前⾯由此我们说，直接插⼊排序，冒泡排序，归并排序，基数排序是稳定的⽽shell 排序，堆排序，快速排序直接选择排序是不稳定的
2. 拓扑排序
说明：本⽂图的构建⽅法及DFS算法可以参考
我们每天早上起床后穿⾐的过程可以分为很多步骤，例如，穿内裤，穿裤⼦，穿内裤必须在穿裤⼦之前，同样的穿袜⼦必须在穿鞋⼦之前等等，戴⼿表和其它的任何⼀个动作之间都没有明显的关系，因此放在这个线性序列中的哪⾥都⽆所谓
2.1. 拓扑排序定义
对于⼀个有向⽆环图G来说，拓扑排序就是对图G中的所有节点的⼀次线性排序，该排序满⾜如下条件，如果图G中包含边(u,v)，则节点u⼀定在v的前⾯，可以将拓扑排序看作是将图的所有节点在⼀条直线上⽔平排开
3. Kahn算法
3.1. 算法原理
对于⼀个有向⽆环AOV(顶点表⽰活动，边表⽰优先关系)图，我们重复执⾏以下两个步骤，直到不存在⼊度为0的顶点为⽌
(1)先择⼀个⼊度为0的顶点并输出
(2)从图中删除由该节点发出的所有边
这样得到的序列就是该图的拓扑排序，如果途中有环，则输出的顶点的数⽬⼩于图中节点的数⽬
3.2. 算法描述
L⼀个⽤来存放已排序顶点的List
S⼀个⽤来存放如度为0的顶点List
当S不为空时执⾏循环执⾏以下步骤
从S中移除⼀个顶点(没有顺序要求，随意移除)n
将n插⼊到L中
循环遍历从n发出的边，对于所有的孩⼦节点m
移除边<n,m>
如果m的⼊度为0，则将m放⼊S中
如果循环结束后图中还有边则说明图中有环
否则L是拓扑排序的结果
3.3. 算法的js实现
//数据结构邻接链表-顶点
function Vertex() {
if (!(this instanceof Vertex))
return new Vertex();
this.pi = null; //初始为⽆前驱
this.d = this.INFINITY; //初始为⽆穷⼤
this.edges = null; //由顶点发出的所有边
this.value = null; //节点的标识
this.data = null; //节点的数据
this.incoming = 0; //节点的⼊度
}
Vertex.prototype = {
constructor: Vertex,
WHITE: 'white', //⽩⾊
GRAY: 'gray', //灰⾊
BLACK: 'black', //⿊⾊
INFINITY: null, //d 为 null 时表⽰⽆穷⼤
}
//数据结构邻接链表-边
function Edge() {
if (!(this instanceof Edge))
return new Edge();
this.index = null; //边所依附的节点的位置
this.sibling = null;
this.w = null; //保存边的权值
}
//数据结构图-G
function Graph() {
if (!(this instanceof Graph))
return new Graph();
this.dict = {}; //字典⽤来映射标节点的识符和数组中的位置
}
Graph.prototype = {
constructor: Graph,
//这⾥加进来的已经具备了边的关系
addNode: function(node) {
},
getNode: function(index) {
aph[index];
},
//创建图的节点
initVertex: function(vertexs) {
/
/创建节点并初始化节点属性 value
for (let value of vertexs) {
let vertex = Vertex();
vertex.value = value.value;
vertex.data = value.data;
}
//初始化字典
for (let i aph) {
this.aph[i].value] = i;
}
},
//建⽴图中边的关系
initEdge: function(edges) {
for (let field in edges) {
let index = this.dict[field]; //从字典表中出节点在 graph 中的位置
let vertex = aph[index]; //获取节点
vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, aph);
}
}
}
//创建链表，返回链表的第⼀个节点
function createLink(index, len, edges, dict, vertexs) {
if (index >= len) return null;
let edgeNode = Edge();
edgeNode.index = dict[edges[index].id]; //边连接的节点⽤在数组中的位置表⽰参照字典
vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //设置节点的⼊度    edgeNode.w = edges[index].w; //边的权值
edgeNode.sibling = createLink(++index, len, edges, dict, vertexs); //通过递归实现回溯
return edgeNode;
}
// a内裤 b袜⼦ c⼿表 d裤⼦ e鞋 f腰带 g衬⾐ h领带 i 夹克
vertexs = [{value: 'a',    data: '内裤'}, {value: 'b',    data: '袜⼦'},
{value: 'c',data: '⼿表'}, {value: 'd',    data: '裤⼦'},
{value: 'e',data: '鞋'}, {value: 'f',    data: '腰带'},
{value: 'g',data: '衬⾐'}, {value: 'h',    data: '领带'},
{value: 'i',data: '夹克'}];
var edges = {
a: [{id: 'd', w: 1 }, {id: 'e', w: 1 }],
b: [{id: 'e', w: 1}],
c: [],
d: [{id: 'e', w: 1 }, {id: 'f', w: 1 }],
e: [],
f: [{id: 'i', w: 1}],
g: [{id: 'f', w: 1 }, {id: 'h', w: 1 }],
h: [{id: 'i', w: 1}],
i: []
}
//kahn算法
function kahn(g) {
let s = []; //⽤于存放⼊度为0的顶点
let l = []; //⽤来存放已经排好序的顶点
//初始化set 将图中所有⼊度为0的节点加⼊到set中
for(let v aph) {
if(v.incoming==0)
s.push(v);
}
while(s.length > 0) {
let u = s.shift();
l.push(u);
if (u.edges == null) continue;
let sibling = u.edges;
while (sibling != null) {
let index = sibling.index;
let n = g.getNode(index);
n.incoming = n.incoming - 1; //删除边
if(n.incoming == 0)    s.push(n); //⼊度为0的放⼊s
sibling = sibling.sibling;
}
}
return l;
}
var g = Graph();
g.initVertex(vertexs);
g.initEdge(edges);
var r = kahn(g);
console.log(r);
运⾏结果
4. 基于DFS的拓扑排序算法
4.1. 算法原理
原理：拓扑排序的次序与顶点的完成时间恰好相反
对于拓扑排序，我们要做的是保证对于任意⼀条边（u,v），节点u⼀定出现在节点v前⾯。
对于DFS算法的每个节点，我们都有⼀个发现时间d，⼀个访问时间f，当DFS运⾏完成时，对于图中的任意⼀条边（u,v），都有 u.f>v.f，所以拓扑排序的次序与顶点的完成时间恰好相反。
当DFS在图上运⾏时，探索到任意⼀条边（u,v）时，u为灰⾊，所以v要么是⽩⾊，要么是⿊⾊，如果v是⽩⾊，则v⼀定早于u被访问，即u.f>v.f，当v为⿊⾊时，此时v已经被访问过，⽽u还为灰⾊，即u没有被访问，所以v依然早于u被访问，仍有 u.f>v.f，由此可见上述结论成⽴
4.2. js实现
基于以上结论，我们⽤DFS实现拓扑排序，只需要在节点 的f被设置值即节点被访问后，将其加⼊⼀个后进先出队列中（调⽤unshift⽅法始终向数组的头部添加新元素）L中，当DFS运⾏结束后，L中的元素就是经过拓扑排序的结果
//数据结构邻接链表-顶点
function Vertex() {
if (!(this instanceof Vertex))
return new Vertex();
this.pi = null; //初始为⽆前驱
this.d = this.INFINITY; //初始为⽆穷⼤
this.edges = null; //由顶点发出的所有边
this.value = null; //节点的标识
this.data = null; //节点的数据
this.incoming = 0;
}
Vertex.prototype = {
constructor: Vertex,
WHITE: 'white', //⽩⾊
GRAY: 'gray', //灰⾊
BLACK: 'black', //⿊⾊
INFINITY: null, //d 为 null 时表⽰⽆穷⼤
}
//数据结构邻接链表-边
function Edge() {
if (!(this instanceof Edge))
return new Edge();
this.index = null; //边所依附的节点的位置
this.sibling = null;
this.w = null; //保存边的权值
}
//数据结构图-G
function Graph() {
if (!(this instanceof Graph))
return new Graph();
this.dict = {}; //字典⽤来映射标节点的识符和数组中的位置
}
Graph.prototype = {
constructor: Graph,
//这⾥加进来的已经具备了边的关系
addNode: function(node) {
sibling什么时候用复数
},
getNode: function(index) {
aph[index];
},
//创建图的节点
initVertex: function(vertexs) {
//创建节点并初始化节点属性 value
for (let value of vertexs) {
let vertex = Vertex();
vertex.value = value.value;
vertex.data = value.data;
}
//初始化字典
for (let i aph) {
this.aph[i].value] = i;
}
},
//建⽴图中边的关系
initEdge: function(edges) {
for (let field in edges) {
let index = this.dict[field]; //从字典表中出节点在 graph 中的位置
let vertex = aph[index]; //获取节点
vertex.edges = createLink(0, edges[field].length, edges[field], this.dict, aph);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。