我对图的拓扑排序理解
// 节点结构定义,u表示边的始点,v表示边的尾点, node指向下一个可能的节点 var node = {u : 0, v : 0, node : null}; var top = -1; // 游标指针 var ind = []; // 记录入度数组 // 邻接表 arr = [node, ...] var aov = function(arr) { // 1. 初始化 记录入度 的数组 var len = arr.length; for(var i = 0; i < len; i++) { ind.push(0); } // 2. 统计节点入度 for(var i = 0; i < len; i++) { node = arr[i].node; while(node != null) { ind[node.v]++; node = node.node; } } // 3. 查询入度为0的节点,构成链表,链表记录下一个入度为0的节点编号 for(var i = 0; i < len; i++) { if(ind[i] == 0) { ind[i] = top; top = i; } } // 4. 开始拓扑计算 var k = 0; while(top != -1) { k++; // 打印入度为0的节点 console.log(top + ‘-->‘ + arr[top]); // top指向下一个入度为0的节点编号 top = ind[top]; // 当前节点指向的链表,将这个链表中的每个节点入度减1 node = arr[top].node; while(node != null) { ind[node.v]--; if(ind[node.v] == 0) { ind[node.v] = top; top = node.v; } node = node.node; } } // 5. 结论 if(k == len) { console.log(‘图是拓扑序列‘); } else { console.log(‘图非拓扑序列‘); } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。