dag图算法

A. 对于一个复杂的有向无环网络，怎么寻找它的一个子图，其中子图内的箭头只在子图内，也就是个闭集这

说明不清晰。什么叫子图内的箭头只在子图内？我猜你想说，子图中的任意节点只能指向该子图内某个节点，不能指向子图外部的节点。
方法是：找到该DAG图的所有叶子节点（出度为0的节点）。如果该子图只包括一个叶子，则该子图是以该叶子节点为根的反向DAG图（即从该节点出发，逆着边的方向，得到反向DAG图。这显然不唯一，非常多）；如果包括多个叶子（比如n个叶子），则该子图是前面n个反向DAG图的并。
总之，一个很简单的DAG图就有很多这种子图，非常多。前面的算法中含有冗余的计算，可以进一步改善。

B. 什么是DAG区块链技术

DAG全称是“有向无环图”，没有区块概念，不是把所有数据打包成区块，再用区块链接区块，而是每个用户都可以提交一个数据单元，这个数据单元里可以有很多东西，比如交易、消息等等。数据单元间通过引用关系链接起来，从而形成具有半序关系的DAG（有向无环图）。DAG的特点是把数据单元的写入操作异步化，大量的钱包客户端可以自主异步地把交易数据写入DAG，从而可以支持极大的并发量和极高的速度。同时，使用DAG技术的TrustNote还支持声明式智能合约，声明式的智能合约要表达的意思是可以直接按照用户想要的结果去写、去描述，以很简单的语言，让大家都能看懂的语言去描述他要干的事情。

截止到2017年年底，“高流量应用”越来越多，除了主流电商平台外，还有直播平台、P2P理财、今日头条、陌陌等崭露头角，如果“高流量应用”与DAG区块链技术结合，将会给行业带来哪些变革呢？除区块链自身的特点去中心化、分布式账本、不可篡改之外，DAG区块链技术不但可以支持高并发，结合双层共识机制，使用工作量证明共识算法，还能够防止“双花”问题。

那么，DAG如何支持高并发的呢？第一，数据不像比特币和以太坊一样强同步，而是弱同步，允许节点在同一时刻数据不一样，数据可以有一些微小的差别。第二，可以通过数据单元之间的引用来完成交易的确认，就是后面发生的单元去引用前面的单元，这样不需要我们把数据传给矿工，整个过程都是由自己去完成的，这个过程很快。DAG是解决高并发比较优美的方法，比起之前的闪电网络，还有其他一些方面，DAG有其先天优势。

再来看看DAG是如何防止“双花”？在有向图里如果能选出一个MainChain，这个时候会发现所有图里面的节点都可以用一种方法来给它做排序，把这个序号连接起来在一排，这张图将会变成跟区块链一样的序列结构，就是排完序的节点，而且每个节点是一个交易，而不是一个区块。所以，确定了主链，通过主链，可以形成全序。最后达到的结局就是在某一个逻辑状态里，交易还是被排序了，这是DAG最关键核心的部分。

“高流量应用”是随着节点数和交易数的增加平滑扩展，当这个节点数超过1亿或交易数超过并发100万时，DAG的特性刚好是交易越多越快，节点越多越快。

C. 基本块的dag图怎么画

基本块构造步骤:

(1): 由规则 (1) 中的 1 可知语句 (1) 是一个入口语句

(2): 由规则 (1) 中的 2 可知, 语句 (3) 和 (8) 均是人口语句

(3): 由规则 (1) 中的 3 可知, 语句 (5) 是二个人口语句, 可以用 "+" 在人口语句的左侧作标记.

(4): 由规则 (2) 可以划分该程序为四个基本块, 它们分别是:

语句 (1),(2) 组成的基本块 B1

语句 (3),(4) 组成的基本块 B2

语句 (5),(6) 和 (7) 组成的基本块 B3

语句 (8) .(9) 组成的基本块 B4

程序中在代码段左侧对各个基本块进行了标记.

(三)程序控制流程流图

定义: 以基本块为结点, 控制程序流向作为有向边, 画出的有向图称为流图.

特点:

具有唯一首结点的有向图

从首结点开始到流图中任何结点都有通路

如果一个结点的基本块的入口语句是程序的第一条语句, 则称此结点为首结点

程序控制流程流图的表示

一个控制流程图可表示成一个三元组:

G=(N,E,n0 )

N: 所有结点 (基本块) 集;

E: 所有有向边集;

n0 : 首结点.

有向边:

当下述条件有一个成立时, 从结点 i 有一有向边引向结点 j:

1 基本块 j 在程序的位置紧跟在 i 后, 且 i

D. 什么是DAG

参考 Explaining Directed Acylic Graph (DAG), The Real Blockchain 3.0

Bitcoin视为blockchain 1.0, Ethereum视为2.0, 那么3.0是什么? DAG可能会是.

DAG, 即Direct Acyclic Graph, 有向无环图. 它的特点是节点有先后次序, 可以有分叉, 但还不会有环. DAG常用语数据处理, 事务规划, 最优路径查找, 数据压缩

bitcoin之所以效率低是因为它的POW机制. 整个网络只有一个主链, 其上的新块只能有一个, 无法同时创建多个新块. 10分钟左右以内的所有交易记录都被记录到一个块中. Ethereum也是类似, 大概15-20秒产生一个新块.

NXT 是第一个想到用DAG替代blockchain单链表结构的组织.

有了DAG, 就可以同一时间创建多个块.

使用DAG的想法来自于侧链(side-chain). 不同类型的交易在不同的链上同时进行.

IoT Chain (ITC), IOTA , 和 Byteball 是没有block概念的项目.

如果每个block只有一个transaction, 那这个transaction就不用等待被打包, 跳过计算hash的过程(即挖矿), 直接上链了.

Bitcoin使用UTXO(Unspent Transaction output)模型.

DAG网络中, 降低网络宽度是比较重要的一个课题.

由于只有transaction, 没有打包的过程, DAG比基于PoW或PoS的区块链更快.

DAG网络里, 没有矿工. 交易的验证直接在交易时进行. 对于用户来说这意味着交易可以瞬间完成.

DAG可以有效降低交易费.

IoT Chain (ITC) 所基于的DAG的TPS达到10,000.

E. 如何判断一个图是否为有向无环图（DAG）

判断图是否为有向无环图的基本思想为：从任意点出发，都不会再回到该点。
Description：
Input:邻接矩阵
color:用来记录节点被访问的情况。‘0’代表未被访问过，‘1代表正在访问’，‘-1’代表该点的后裔节点都已经被访问过。在一次搜索中，若某点的状态为1，则该点之前被访问过，存在环。若某点的状态为‘-1’，则该点的后裔点均被访问过，跳过该次搜索。若某点的状态为‘0’，则该点之前没有被访问过，DFS该点。

本文分别用一个有向无圈图和一个有向有圈图做测试：

F. dag图的介绍

DAG数据结构跟踪基本块中值和变量的计算和赋值 ；块中使用的来自别处的值表示为叶子结点 ；值上的操作表示为内部结点 ；新值的赋值表示为将目标变量或临时变量的名字附加到表示赋值的结点上。

G. 有谁知道能解释一下有向无环图(DAG)么怎么用程序做出来，及怎么应用到经济学实证上

我们说区块链目前还不成熟，有各种各样的问题，比如说处理速度慢、手续费高昂、存在安全隐患等等，这些都是用户最直观的体验，体验不是太好。区块链还有一个问题，那就是高并发问题。
高并发问题是怎么回事呢，我们简单说一下。高并发是计算机领域的问题，简单来讲，高并发问题就是系统无法顺利同时运行多个任务。
很多任务同时运行，一大堆用户涌进来，系统承受不住这么多的任务，会出现高并发问题，你的系统就卡住了，就好比春运时候，12306系统总是卡住，有可能就是高并发问题造成的。
传统互联网尚且存在高并发问题，区块链网络自然也存在这个问题，毕竟区块链的成熟程度比起传统互联网，还有很大的差距。但是，如果没有安全、可靠和高效的公链，整个区块链产业的发展都将受到严重制约，应用落地也是空谈。
在这种背景下，DAG 技术就被提出来了，DAG 的全称是“Directed Acyclic Graph”，中文翻译为“有向无环图”。
DAG有向无环图是怎么回事呢，它到底能起到什么作用呢？我们下面解释一下。
一、DAG：一个新型的数据结构
DAG，中文名字叫“有向无环图”，从字面意思看，“有向"就是说它是有方向的，
“无环”就是说它是没有环路的、不能形成闭环的。所以，DAG其实是一种新型的数据结构，这个数据结构是有方向的，同时又是不能形成闭环的。
传统区块来讲，我们总是以“区块”为单位，一个区块里往往包含了多笔交易信息。而在DAG中，没有区块的概念，而是以“单元”为单位，每个单元记录的是单个用户的交易，组成的单元不是区块，而是一笔笔的交易，这样一来，可以省去打包出块的时间。
简单来说，区块链和DAG有向无环图最大的区别就是：区块链是一个接一个的区块来存储和验证交易的分布式账本，而DAG则是把每笔交易都看成一个区块，每一笔交易都可以链接到多个先前的交易来进行验证。
二、DAG 的工作原理
传统区块链上，就拿比特币来讲，它是单链式的结构，区块与区块之间按照时间戳的先后顺序排列开来（如图一），数据记录在一条主链上。用不太恰当的比喻来讲，这个
“单链式”结构是一条一字排列的链。
区块链只有一条单链，打包出块就无法并发执行。新的区块会加入到原先的最长链之上，所有节点都以最长链为准，继续按照时间戳的顺序无限蔓延下去。而对于DAG来讲，每个新加入的单元，不仅只加入到最长链的一个单元，还要加入到之前所有的单元（如图二）。
举个例子：假设我发布了一个新的交易，此时DAG结构已经有2个有效的交易单元，那么我的交易单元会主动同时链接到前面的2个之中，去验证并确认，直到链接到创世单元，而且，上一个单元的哈希会包含到自己的单元里面。
换句话说，你要想进行一笔交易，就必须要验证前面的交易，具体验证几个交易，根据不同的规则来进行。这种验证手段，使得DAG可以异步并发的写入很多交易，并最终构成一种拓扑的树状结构，极大地提高扩展性。
依据DAG有向无环图，每一笔交易都直接参与了维护全网。当交易发起后，直接广播全网，跳过矿工打包区块阶段，这样就省去了打包交易出块的时间，提升了区块链处理交易的效率。
随着时间递增，所有交易的区块链相互连接，形成图状结构，如果要更改数据，那就不仅仅是几个区块的问题了，而是整个区块图的数据更改。DAG这个模式相比来说，要进行的复杂度更高，更难以被更改。
总结一下，DAG作为一种新型的去中心化数据结构，它属于广义区块链的一种，具备去中心化的属性，但是二者的不同之处在于：
区块链组成单元是Block（区块），DAG组成单元是TX（交易）。
区块链是单线程，DAG是多线程。
区块链所有交易记录记在同一个区块中，DAG每笔交易单独记录在每笔交易中。
区块链需要矿工，DAG不需要矿工。
三、 DAG 的代表：IOTA
DAG当前的代表项目，最知名的无疑就是 IOTA。可以说，正是因为IOTA这个币种在 2017年下半年冲进市值排行第四位，才使人们真正认识到了它的底层技术：DAG有向无环图。
IOTA在DAG有向无环图的基础上提出了“缠结”概念，在IOTA里面，没有区块的概念，共识的最小单位是交易。每一个交易都会引用过去的两条交易记录哈希，这样前一交易会证明过去两条交易的合法性，间接证明之前所有交易的合法性。这样一来， 就不再需要传统区块链中的矿工这样少量节点来验证交易、打包区块，从而提升效率，节省交易费用。
四、 DAG 的现状
尽管理论上来讲，DAG有向无环图能够弥补传统区块链的一些弊端，但是目前并不成熟，应用到数字货币领域的时间也比较短，还比较年轻 。
它没有像比特币那般经过长达10年的时间来验证整个系统的安全性，也没有像以太坊那般实现了广泛的应用场景。不过，现在有些声音提出要采用“传统区块链+DAG”的数据结构，但是还没有非常突出的案例，这里就不多说了。
总结一下，本节我们介绍了区块链的衍生技术：DAG有向无环图，这是一种全新的数据结构，可以对区块链处理交易的效率、并发力达到显着的提升。

H. ‘学概念找员外’有向无环图DAG的用途

有向无环图（DAG, Directed Acyclic Graph） ：是一个无回路的有向图。如果有一个图，从A点出发到B点，然后经过C点，最后可以顺着方向回到A，形成一个闭环，那么这个图就不是非向无环图。如果将从C到A的边方向改为从A到C，则变成有向无环图。如图1 和 图2。

看到这两幅图，应该可以明白了，当然这个图是很简单的，只有三个点，事实上可能是由百万千万或者更多个点组成的图。有向无环图就是从一个图中的任何一点出发，不管走过多少个分叉路口，都没有回到原来这个点的可能性。

拓扑排序 ：就是一个有向无环图的所有定点的线性序列。且这个序列必须满足这两个条件：

这个东西，是比较难理解，再上图说话吧。比如在这个有向无环图中，它用拓扑排序，该怎么进行呢？

最后，一个完整的拓扑排序就完成了，结果为：1、2、4、3、5。

大家都知道，在比特币系统中，固定约十分钟出一个块，而且一旦打包成功一个区块，这个区块的信息还必须同步到其他的所有区块上面去，这是极其耗费资源和时间的。同时一个块里面大概能容纳3000笔交易，也就意味着10分钟才能交易成功3000笔。这个交易速度实在是满足不了用户的需求，所以为了解决比特币这个问题，出现了各种分叉币，也可谓是把比特币搞的乱七八糟了。后来以太坊问世后，基于比特币的基础上，交易速度提高了不少，每秒交易可达到20笔左右，但是任然有多次的以太坊拥堵事件，证明这个交易速度还远远不够。

在比特币系统中，如果可以改变51%的节点的记录数据，那么就实现了恶意攻击。然而现在比特币的大部分算力掌握在少数几个较大的矿厂手里，虽然大家都有共识，不会发起恶意攻击，但是不代表不会有意外事件发生。

随着计算机硬件的不断迭代升级，量子计算机的问世，那么比特币的加密算法还会有用吗？会不会被破解掉？虽然比特币的哈希算法可以实时调整难度，但是到底能承受多大的考验，员外是说不清的。

比特币用于大额的跨境转账或者交易等用途，还是挺实用的，但是谁会去用比特币购买小件商品？显然是不可能的，交易手续费就会让你心疼半天，然后还得再等半天的确认时间。

在区块链的应用上使用了DAG图之后，可以使得出块速度变快，因为DAG图中的每个顶点都是一个在某一时间点打包完成的区块。与传统的公链一次性只能产出一个区块来比，DAG的不同节点都可以自己来生成区块，然后这个区块只要选择好自己的下一个或者多个区块作为自己的子区块就好了。仅仅是在这一点上，出块速度就会高出比特币多个量级，交易速度简直可以快的飞起。

基于DAG的数据结构来说的话，对于里面的每个节点来说，因为与之相连的节点很少，而且是有方向性的，只能往前不能后退，所以都不需要再等大量的其他节点达成共识后，再同时确认下一笔交易了，避免了因网络延迟和数据同步造成的大量时间浪费。所以，使用DAG记账的节点的延展性可得到大幅度提升。

从上面这张图中，可以看到DAG的每一个节点都可以向下连接任意多个新的节点，这个有什么用呢？如果在这一个区块内部交易数据或者与之相连的下一步的交易数据也是过多的话，那么就可以分成足够多个区块来共同分担区块压力，从而可以提高交易的吞吐量。相比于比特币这样的系统每次只能打包一个区块来说，简直是完胜。

没有一个东西是完美的，有优势就有缺点，所以DAG的缺点目前在安全问题上面，主要是双花和影子链攻击。这个问题员外目前还没有找到足够好的答案，只能后续再说了。

本文参加优享优质经验征集计划，经验即价值，优享为成长买单
全球首个去中心化经验价值共享平台“优享”开启今夏最强空投!注册即送UX，最高5000UX，更多价值，等你发现！注册链接