章节 8 拓扑排序
AOV
kahh 算法
应用场景：工程当中需要用到事件活动，其中图中的顶点表示活动，图中的边表示事件
遵循原则：
- <i,j> i 为 j 的直接前驱，j 为 i 的直接后继，当i无直接前驱时，可以先把这个顶点去掉，加到到一个数组里面
- 并删除以 i 为弧尾的边
重复以上过程 当所有的顶点都已出现在数组中，说明图中不存在环。
以下是 js 实现：
//数据结构 邻接链表-顶点
class Vertex {
constructor() {
this.color = 'white'; //初始为 白色
this.pi = null; //初始为 无前驱
this.d = null; //初始为 无穷大
this.edges = null; //由顶点发出的所有边
this.value = null; //节点的标识
this.data = null; //节点的数据
this.incoming = 0; //节点的入度
}
}
//数据结构 邻接链表-边
class Edge {
constructor() {
this.index = null; //边所依附的节点的位置
this.sibling = null;
this.w = null; //保存边的权值
}
}
class Graph {
constructor() {
this.graph = [];
this.dict = {}; //字典 用来映射标节点的识符和数组中的位置
}
//这里加进来的已经具备了边的关系
addNode(node) {
this.graph.push(node);
}
getNode(index) {
return this.graph[index];
}
//创建图的 节点
initVertex(vertexs) {
//创建节点并初始化节点属性 value
for (let value of vertexs) {
let vertex = new Vertex();
vertex.value = value.value;
vertex.data = value.data;
this.graph.push(vertex);
}
//初始化 字典
for (let i in this.graph) {
this.dict[this.graph[i].value] = i;
}
}
//建立图中 边 的关系
initEdge(edges) {
for (let field in edges) {
let index = this.dict[field]; //从字典表中找出节点在 graph 中的位置
let vertex = this.graph[index]; //获取节点
vertex.edges = this.createLink(0, edges[field].length, edges[field], this.dict, this.graph);
}
}
//创建链表，返回链表的第一个节点
createLink(index, len, edges, dict, vertexs) {
if (index >= len) return null;
let edgeNode = new Edge();
edgeNode.index = dict[edges[index].id]; //边连接的节点 用在数组中的位置表示 参照字典
vertexs[edgeNode.index].incoming = vertexs[edgeNode.index].incoming + 1; //设置节点的入度
edgeNode.w = edges[index].w; //边的权值
edgeNode.sibling = this.createLink(++index, len, edges, dict, vertexs); //通过递归实现 回溯
return edgeNode;
}
}
// a内裤 b袜子 c手表 d裤子 e鞋 f腰带 g衬衣 h领带 i 夹克
var 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 of g.graph) {
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 = new Graph();
g.initVertex(vertexs);
g.initEdge(edges);
var r = kahn(g);
console.log(r);