首页 > 代码库 > 我对图的拓扑排序理解
我对图的拓扑排序理解
// 节点结构定义,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(‘图非拓扑序列‘); } }
我对图的拓扑排序理解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。