文档章节

我对图的拓扑排序理解

rutine
 rutine
发布于 2014/12/07 18:49
字数 314
阅读 156
收藏 7
<!-- lang: js -->
 // 节点结构定义,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('图非拓扑序列');
  }
}

© 著作权归作者所有

共有 人打赏支持
rutine
粉丝 1
博文 4
码字总数 1176
作品 0
广州
程序员
私信 提问
图应用之拓扑排序(Topological Sort)

这一篇写有向无环图及其它的应用: 清楚概念: 有向无环图(DAG):一个无环的有向图。通俗的讲就是从一个点沿着有向边出发,无论怎么遍历都不会回到出发点上。 有向无环图是描述一项工程或者...

临江仙卜算子
2018/06/20
0
0
hdu 1285 确定比赛名次 拓扑排序

Problem Description 有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排名,但现在裁判委员会不能直接获得每个队的...

阿豪boy
2017/11/20
0
0
【图的遍历】判断能否完成课程(是否又环) Course Schedule

问题: There are a total of n courses you have to take, labeled from to . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, whic......

叶枫啦啦
2017/11/17
0
0
图的搜索

前言 图的搜索指的是系统化地跟随图中的边来访问图中每一个结点,并不是随意地访问图中的结点。图的搜索算法可以用来发现图的结构,许多图的算法都要求先搜索全图,可以说,图的搜索是整个图...

某昆
2017/09/16
0
0
有向图问题1--深度优先、广度优先遍历和拓扑排序

有向图基础 术语定义: 一个顶点的出度为由该顶点指出的边的总数 一个顶点的入度为指向该顶点的边的总数 一条有向边的第一个顶点称为它的头,第二个顶点称为它的尾 数据结构: 使用邻接表来表...

SuperHeroes
2017/12/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jenkins安装

https://my.oschina.net/u/593517/blog/1797968 jenkins 安装 https://my.oschina.net/u/593517/blog/3028175 GIT 安装 https://my.oschina.net/u/593517/blog/3028179 maven 安装 插件安装 ......

Gm_ning
21分钟前
2
0
小言服务端解决方案-监控

框架保证方向,整体包容细节 为保证服务端运行平稳正常,owner应使得系统应保有相应的监控:系统监控,业务监控。而服务运行的平稳高效是否有保障跟监控粒度又成直接的正比关系。本文仅针对开...

重城重楼
33分钟前
1
0
搜索引擎(Elasticsearch搜索详解)

学完本课题,你应达成如下目标: 掌握ES搜索API的规则、用法。 掌握各种查询用法 搜索API 搜索API 端点地址 GET /twitter/_search?q=user:kimchy GET /twitter/tweet,user/_search?q=user:...

这很耳东先生
56分钟前
7
0
浅谈如何减少GC的次数

GC会stop the world。会暂停程序的执行,带来延迟的代价。所以在开发中,我们不希望GC的次数过多。 本文将讨论如何在开发中改善各种细节,从而减少GC的次数。 (1)对象不用时最好显式置为 Nu...

浮躁的码农
58分钟前
1
0
jpa 自定义返回对象

任何ORM框架都少不了开放自定义sql的问题。jpa自然也不例外,很多场景需要写复杂sql的。 首先定义一个方法签名,然后打上@Query注解。像下面这样,需要注意nativeQuery,这个表示query中的字...

朝如青丝暮成雪
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部