DAG（有向无环图）-入门基础

本文主要是介绍DAG（有向无环图）-入门基础，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、图基础

1. 图

图是数据结构中最为复杂的一种，图主要包括：

• 无向图，结点的简单连接
• 有向图，连接有方向性
• 加权图，连接带有权值
• 加权有向图，连接既有方向性，又带有权值

图是由一组顶点和一组能够将两个顶点相连的边组成。

2. 基础术语

• 顶点：图中的一个点
• 边：连接两个顶点的线段叫做边，edge
• 相邻的：一个边的两头的顶点称为是相邻的顶点
• 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
• 路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
• 简单路径：没有重复顶点的路径
• 环：至少含有一条边，并且起点和终点都是同一个顶点的路径
• 简单环：不含有重复顶点和边的环
• 连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
• 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
• 无环图：是一种不包含环的图
• 稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
• 稠密图：图中的每个顶点的度数都很高，看起来很稠密
• 二分图：可以将图中所有顶点分为两部分的图

树其实就是一种无环连通图。

3. 有向图

有向图是一幅有方向性的图，由一组顶点和有向边组成。

在有向图中，顶点被细分为了：

• 出度：由一个顶点出发的边的总数
• 入度：指向一个顶点的边的总数

由于有向图的方向性，一条边的出发点称为头，指向点称为尾。
图的连通性在有向图中表现为可达性，由于边的方向性，可达性必须是通过顶点出发的边的正确方向，与另一个顶点可连通。

可达性的一种应用：垃圾收集。

我们都知道一般的对象垃圾收集都是计算它的引用数。在图结构中，把对象作为顶点，引用作为边，当一个对象在一段时间内未被他人引用的时候，这个顶点就是孤立的，对于其他有效路径上的顶点来说它就是不可达的，因此就不会被标记，这时候，例如JVM就会清除掉这些对象释放内存，所以JVM也是一直在跑类似以上这种DFS的程序，不断找到那些未被标记的顶点，按照一定时间规则进行清除。

3. 有向无环图

不包含有向环的有向图就是有向无环图，DAG，Directed Acyclic Graph。

二、DAG算法基础

1. 什么是DAG

Merkle DAG的全称是 Merkle directed acyclic graph（默克有向无环图）。它是在Merkle tree基础上构建的，Merkle tree是由美国计算机学家merkle于1979年申请的专利。Merkle DAG跟Merkle tree很相似，但不完全一样，比如：Merkle DAG不需要进行树的平衡操作，非叶子节点允许包含数据等。

1. 图论算法——有向无环图

【推荐-讲的很通俗易懂】『学概念找员外』有向无环图DAG的用途
参考URL: https://www.jianshu.com/p/e8e482a95479

图是数据结构中最为复杂的一种，图在信息化社会中的应用非常广泛。

图主要包括：

• 无向图，结点的简单连接
• 有向图，连接有方向性
• 加权图，连接带有权值
• 加权有向图，连接既有方向性，又带有权值

图是由一组顶点和一组能够将两个顶点相连的边组成。 树其实就是一种无环连通图。

术语

• 顶点：图中的一个点
• 边：连接两个顶点的线段叫做边，edge
• 相邻的：一个边的两头的顶点称为是相邻的顶点
• 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
• 路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
• 简单路径：没有重复顶点的路径
  -连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
• 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
• 无环图：是一种不包含环的图
• 稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
• 稠密图：图中的每个顶点的度数都很高，看起来很稠密
• 二分图：可以将图中所有顶点分为两部分的图

有向图
有向图是一幅有方向性的图，由一组顶点和有向边组成。所以，大白话来讲，有向图是包括箭头来代表方向的。

常见的例如食物链，网络通信等都是有向图的结构。

在有向图中，顶点被细分为了：

• 出度：由一个顶点出发的边的总数
• 入度：指向一个顶点的边的总数

由于有向图的方向性，一条边的出发点称为头，指向点称为尾。
图的连通性在有向图中表现为可达性，由于边的方向性，可达性必须是通过顶点出发的边的正确方向，与另一个顶点可连通。

有向无环图:
有向无环图就是从一个图中的任何一点出发，不管走过多少个分叉路口，都没有回到原来这个点的可能性。

三、参考

科普 ｜ 一文读懂 DAG（有向无环图）技术
参考URL: https://baijiahao.baidu.com/s?id=1613728387077554506&wfr=spider&for=pc
拓扑排序-有向无环图（DAG, Directed Acyclic Graph）
参考URL: https://www.cnblogs.com/shoulinniao/p/10395815.html
Spark中的有向无环图(DAG:Directed Acyclic Graph)
参考URL: https://www.pianshen.com/article/38531455651/
基于有向无环图（DAG）的任务调度Demo
参考URL: https://blog.csdn.net/dbqb007/article/details/89042984
算法精解：DAG有向无环图
参考URL: https://www.cnblogs.com/Evsward/p/dag.html
五分钟讲明白DAG（有向无环图）的优缺点
参考URL: https://baijiahao.baidu.com/s?id=1602410984624790167&wfr=spider&for=pc

这篇关于DAG（有向无环图）-入门基础的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---