建设银行电商网站,公司域名邮箱怎么注册,襄阳建设网站,app开发语言有哪些DAG图 导读一、有向无环图描述表达式1.1 过程演示1.2 DAG图的读取 结语 导读
大家好#xff0c;很高兴又和大家见面啦#xff01;#xff01;#xff01;
今天我们将延续图的应用探索#xff0c;在前两期学习的最小生成树和最短路径基础上#xff0c;展开图的第三个重要… DAG图 导读一、有向无环图描述表达式1.1 过程演示1.2 DAG图的读取 结语 导读
大家好很高兴又和大家见面啦
今天我们将延续图的应用探索在前两期学习的最小生成树和最短路径基础上展开图的第三个重要应用方向——有向无环图DAG。
在前期内容中我们深入探讨了图的两种经典应用 最小生成树MST 解决全节点连通的最低成本问题经典应用网络布线、电力输送核心算法 Prim算法从任意节点开始贪心添加连接树与非树节点的最小边Kruskal算法按权重升序选边用并查集避免成环 最短路径 解决节点间最优路径规划问题核心算法 BFS算法在无权图中实现O(VE)时间复杂度的单源最短路径Dijkstra算法非负权重图中的最优单源路径Bellman-Ford算法支持负权重边并检测负环 BFS的特殊价值当边权为1时其第一次访问路径即最短跳数路径是理解拓扑排序等高级算法的基础。 今天我们将把目光转向图的另一个精妙应用。当问题涉及执行顺序约束如任务依赖关系或计算结构复用如嵌套表达式时DAG凭借其有向无环的特性成为理想解决方案。 为何DAG是自然延伸 最小生成树 → 物理连接问题 最短路径 → 路径规划问题 DAG → 依赖关系管理问题
下面我们将通过具体案例展示DAG如何将表达式存储空间缩减42%马上开始今天的核心内容
一、有向无环图描述表达式
有向无环图一个有向图中不存在环则称为有向无环图简称DAGDirected Acyclic Graph 图。
有向无环图是描述含有公共子式的表达式的有效工具例如表达式 ( ( a b ) ∗ ( b ∗ ( c d ) ) ( c d ) ∗ e ) ∗ ( ( c d ) ∗ e ) ((ab)*(b*(cd))(cd)*e)*((cd)*e) ((ab)∗(b∗(cd))(cd)∗e)∗((cd)∗e)
在这个表达式中我们如果将运算符作为根结点两个操作数作为根结点的左右子树那么我们就可以通过一棵二叉树来表达上式 #mermaid-svg-W3WRdwR4owf8rFln {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-W3WRdwR4owf8rFln .error-icon{fill:#552222;}#mermaid-svg-W3WRdwR4owf8rFln .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-W3WRdwR4owf8rFln .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-W3WRdwR4owf8rFln .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-W3WRdwR4owf8rFln .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-W3WRdwR4owf8rFln .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-W3WRdwR4owf8rFln .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-W3WRdwR4owf8rFln .marker{fill:#333333;stroke:#333333;}#mermaid-svg-W3WRdwR4owf8rFln .marker.cross{stroke:#333333;}#mermaid-svg-W3WRdwR4owf8rFln svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-W3WRdwR4owf8rFln .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-W3WRdwR4owf8rFln .cluster-label text{fill:#333;}#mermaid-svg-W3WRdwR4owf8rFln .cluster-label span{color:#333;}#mermaid-svg-W3WRdwR4owf8rFln .label text,#mermaid-svg-W3WRdwR4owf8rFln span{fill:#333;color:#333;}#mermaid-svg-W3WRdwR4owf8rFln .node rect,#mermaid-svg-W3WRdwR4owf8rFln .node circle,#mermaid-svg-W3WRdwR4owf8rFln .node ellipse,#mermaid-svg-W3WRdwR4owf8rFln .node polygon,#mermaid-svg-W3WRdwR4owf8rFln .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-W3WRdwR4owf8rFln .node .label{text-align:center;}#mermaid-svg-W3WRdwR4owf8rFln .node.clickable{cursor:pointer;}#mermaid-svg-W3WRdwR4owf8rFln .arrowheadPath{fill:#333333;}#mermaid-svg-W3WRdwR4owf8rFln .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-W3WRdwR4owf8rFln .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-W3WRdwR4owf8rFln .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-W3WRdwR4owf8rFln .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-W3WRdwR4owf8rFln .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-W3WRdwR4owf8rFln .cluster text{fill:#333;}#mermaid-svg-W3WRdwR4owf8rFln .cluster span{color:#333;}#mermaid-svg-W3WRdwR4owf8rFln div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-W3WRdwR4owf8rFln :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} * * * * * b b c c c d d d e e a 在这么一棵二叉树中我们不难发现虽然表达式中只有3种标点符号和5个字母但是我们却花费了大量的空间将每一个标点符号和每一个字母都记录了下来。
那有没有一种方法能够很大程度上的节省空间呢
这个就是我们前面提到的有向无环图的功能了在有向无环图中我们可以通过把相同的部分进行共享以此来缩减存储空间的开销。
为了更好的说明有向无环图下面我们就来一步一步的合并上图中的相同子式
1.1 过程演示
这里我们从二叉树的最底层开始按照从左到右的顺序进行合并。该二叉树共有6层因此我们先从第6层开始
第六层二叉树的最底层只有两个元素c和d显然这是无法进行合并的因此这里的元素c和d保留 #mermaid-svg-EnxcHuR0p7Kp5FT3 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .error-icon{fill:#552222;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .marker.cross{stroke:#333333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .cluster-label text{fill:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .cluster-label span{color:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .label text,#mermaid-svg-EnxcHuR0p7Kp5FT3 span{fill:#333;color:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .node rect,#mermaid-svg-EnxcHuR0p7Kp5FT3 .node circle,#mermaid-svg-EnxcHuR0p7Kp5FT3 .node ellipse,#mermaid-svg-EnxcHuR0p7Kp5FT3 .node polygon,#mermaid-svg-EnxcHuR0p7Kp5FT3 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .node .label{text-align:center;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .node.clickable{cursor:pointer;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .arrowheadPath{fill:#333333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .cluster text{fill:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 .cluster span{color:#333;}#mermaid-svg-EnxcHuR0p7Kp5FT3 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EnxcHuR0p7Kp5FT3 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} c d 第五层 在第五层中我们可以看到存在两个b因此这里可以进行合并在第五层中同样也存在元素c和d但是第六层的c、d的父结点是但是第五层的我们目前还不清楚所有这里先保留 #mermaid-svg-iqscrlJMIeO7xn7e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .error-icon{fill:#552222;}#mermaid-svg-iqscrlJMIeO7xn7e .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-iqscrlJMIeO7xn7e .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-iqscrlJMIeO7xn7e .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-iqscrlJMIeO7xn7e .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-iqscrlJMIeO7xn7e .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-iqscrlJMIeO7xn7e .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-iqscrlJMIeO7xn7e .marker{fill:#333333;stroke:#333333;}#mermaid-svg-iqscrlJMIeO7xn7e .marker.cross{stroke:#333333;}#mermaid-svg-iqscrlJMIeO7xn7e svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-iqscrlJMIeO7xn7e .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .cluster-label text{fill:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .cluster-label span{color:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .label text,#mermaid-svg-iqscrlJMIeO7xn7e span{fill:#333;color:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .node rect,#mermaid-svg-iqscrlJMIeO7xn7e .node circle,#mermaid-svg-iqscrlJMIeO7xn7e .node ellipse,#mermaid-svg-iqscrlJMIeO7xn7e .node polygon,#mermaid-svg-iqscrlJMIeO7xn7e .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-iqscrlJMIeO7xn7e .node .label{text-align:center;}#mermaid-svg-iqscrlJMIeO7xn7e .node.clickable{cursor:pointer;}#mermaid-svg-iqscrlJMIeO7xn7e .arrowheadPath{fill:#333333;}#mermaid-svg-iqscrlJMIeO7xn7e .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-iqscrlJMIeO7xn7e .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-iqscrlJMIeO7xn7e .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-iqscrlJMIeO7xn7e .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-iqscrlJMIeO7xn7e .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-iqscrlJMIeO7xn7e .cluster text{fill:#333;}#mermaid-svg-iqscrlJMIeO7xn7e .cluster span{color:#333;}#mermaid-svg-iqscrlJMIeO7xn7e div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-iqscrlJMIeO7xn7e :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} a b c d c d 第四层 在这里层中我们看到存在两个同时又出现了c和d这一层的c和d我们目前需要保留接下来我们来看这一层的两个第一个的左右子树是元素a和b第二个的左右子树是元素c和d这与第五层中的的左右子树相同因此这里的与第五层的进行合并 #mermaid-svg-8yltkOTEh9OAxlZ7 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .error-icon{fill:#552222;}#mermaid-svg-8yltkOTEh9OAxlZ7 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-8yltkOTEh9OAxlZ7 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .marker.cross{stroke:#333333;}#mermaid-svg-8yltkOTEh9OAxlZ7 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .cluster-label text{fill:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .cluster-label span{color:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .label text,#mermaid-svg-8yltkOTEh9OAxlZ7 span{fill:#333;color:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .node rect,#mermaid-svg-8yltkOTEh9OAxlZ7 .node circle,#mermaid-svg-8yltkOTEh9OAxlZ7 .node ellipse,#mermaid-svg-8yltkOTEh9OAxlZ7 .node polygon,#mermaid-svg-8yltkOTEh9OAxlZ7 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .node .label{text-align:center;}#mermaid-svg-8yltkOTEh9OAxlZ7 .node.clickable{cursor:pointer;}#mermaid-svg-8yltkOTEh9OAxlZ7 .arrowheadPath{fill:#333333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-8yltkOTEh9OAxlZ7 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-8yltkOTEh9OAxlZ7 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-8yltkOTEh9OAxlZ7 .cluster text{fill:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 .cluster span{color:#333;}#mermaid-svg-8yltkOTEh9OAxlZ7 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-8yltkOTEh9OAxlZ7 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} a b * c d e c d 第三层 第三层中有4个元素*/*//e第一个*的左右子树分别是第四层的和*第二个*的左右子树分别是第四层的和e因此这两个*不能合并需要保留这一层的的左右子树是c和d与第四层的第二个和第五层的相同因此这里的可以与第五层的进行合并 #mermaid-svg-WzZBAtBCbQos7QUR {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .error-icon{fill:#552222;}#mermaid-svg-WzZBAtBCbQos7QUR .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-WzZBAtBCbQos7QUR .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-WzZBAtBCbQos7QUR .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-WzZBAtBCbQos7QUR .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-WzZBAtBCbQos7QUR .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-WzZBAtBCbQos7QUR .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-WzZBAtBCbQos7QUR .marker{fill:#333333;stroke:#333333;}#mermaid-svg-WzZBAtBCbQos7QUR .marker.cross{stroke:#333333;}#mermaid-svg-WzZBAtBCbQos7QUR svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-WzZBAtBCbQos7QUR .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .cluster-label text{fill:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .cluster-label span{color:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .label text,#mermaid-svg-WzZBAtBCbQos7QUR span{fill:#333;color:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .node rect,#mermaid-svg-WzZBAtBCbQos7QUR .node circle,#mermaid-svg-WzZBAtBCbQos7QUR .node ellipse,#mermaid-svg-WzZBAtBCbQos7QUR .node polygon,#mermaid-svg-WzZBAtBCbQos7QUR .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-WzZBAtBCbQos7QUR .node .label{text-align:center;}#mermaid-svg-WzZBAtBCbQos7QUR .node.clickable{cursor:pointer;}#mermaid-svg-WzZBAtBCbQos7QUR .arrowheadPath{fill:#333333;}#mermaid-svg-WzZBAtBCbQos7QUR .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-WzZBAtBCbQos7QUR .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-WzZBAtBCbQos7QUR .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-WzZBAtBCbQos7QUR .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-WzZBAtBCbQos7QUR .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-WzZBAtBCbQos7QUR .cluster text{fill:#333;}#mermaid-svg-WzZBAtBCbQos7QUR .cluster span{color:#333;}#mermaid-svg-WzZBAtBCbQos7QUR div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-WzZBAtBCbQos7QUR :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} * * a b c d * e e 第二层 第二层只有两个元素/*这一层的的左右子树是第三层的两个*因此需要保留这一层的*的左右子树是第三层的和e这与第三层的第二个*的左右子树相同因此可以合并 #mermaid-svg-RqTVsXj8qQ48BADQ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .error-icon{fill:#552222;}#mermaid-svg-RqTVsXj8qQ48BADQ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RqTVsXj8qQ48BADQ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-RqTVsXj8qQ48BADQ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RqTVsXj8qQ48BADQ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RqTVsXj8qQ48BADQ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RqTVsXj8qQ48BADQ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RqTVsXj8qQ48BADQ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-RqTVsXj8qQ48BADQ .marker.cross{stroke:#333333;}#mermaid-svg-RqTVsXj8qQ48BADQ svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RqTVsXj8qQ48BADQ .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .cluster-label text{fill:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .cluster-label span{color:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .label text,#mermaid-svg-RqTVsXj8qQ48BADQ span{fill:#333;color:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .node rect,#mermaid-svg-RqTVsXj8qQ48BADQ .node circle,#mermaid-svg-RqTVsXj8qQ48BADQ .node ellipse,#mermaid-svg-RqTVsXj8qQ48BADQ .node polygon,#mermaid-svg-RqTVsXj8qQ48BADQ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RqTVsXj8qQ48BADQ .node .label{text-align:center;}#mermaid-svg-RqTVsXj8qQ48BADQ .node.clickable{cursor:pointer;}#mermaid-svg-RqTVsXj8qQ48BADQ .arrowheadPath{fill:#333333;}#mermaid-svg-RqTVsXj8qQ48BADQ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RqTVsXj8qQ48BADQ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RqTVsXj8qQ48BADQ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-RqTVsXj8qQ48BADQ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-RqTVsXj8qQ48BADQ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RqTVsXj8qQ48BADQ .cluster text{fill:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ .cluster span{color:#333;}#mermaid-svg-RqTVsXj8qQ48BADQ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RqTVsXj8qQ48BADQ :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} * * * a b c d e 第一层 第一层只有一个元素*其左右子树分别是第二层的和*这里需要保留 #mermaid-svg-TxNufWp8Sw6YB3R2 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .error-icon{fill:#552222;}#mermaid-svg-TxNufWp8Sw6YB3R2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-TxNufWp8Sw6YB3R2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .marker.cross{stroke:#333333;}#mermaid-svg-TxNufWp8Sw6YB3R2 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .cluster-label text{fill:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .cluster-label span{color:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .label text,#mermaid-svg-TxNufWp8Sw6YB3R2 span{fill:#333;color:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .node rect,#mermaid-svg-TxNufWp8Sw6YB3R2 .node circle,#mermaid-svg-TxNufWp8Sw6YB3R2 .node ellipse,#mermaid-svg-TxNufWp8Sw6YB3R2 .node polygon,#mermaid-svg-TxNufWp8Sw6YB3R2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .node .label{text-align:center;}#mermaid-svg-TxNufWp8Sw6YB3R2 .node.clickable{cursor:pointer;}#mermaid-svg-TxNufWp8Sw6YB3R2 .arrowheadPath{fill:#333333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-TxNufWp8Sw6YB3R2 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-TxNufWp8Sw6YB3R2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-TxNufWp8Sw6YB3R2 .cluster text{fill:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 .cluster span{color:#333;}#mermaid-svg-TxNufWp8Sw6YB3R2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-TxNufWp8Sw6YB3R2 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} * * * * a b c d e 可以看到经过合并后我们目前只使用了12个结点就完成了该表达式的描述相比于之前的二叉树的21个结点我们就节省了9个结点的存储空间
1.2 DAG图的读取
当我们要读取一个DAG图时也很简单我们同样只需要从最底层开始即可如下所示
首先我们读取到的是元素c和d这两个操作数的操作符是因此我们记录下第一部分 c d cd cd接下来我们读取到的是元素a和b这两个操作数的操作符是因此我们记录下第二部分 a b ab ab第一部分的 c d cd cd作为操作数时它的操作符是*而该操作符的另一个操作数指向的时元素b因此第三部分应该是由b和 c d cd cd作为操作符*的左右操作数组成我们记录下第三部分 b ∗ ( c d ) b*(cd) b∗(cd)第二部分的 a b ab ab作为操作数时它的操作符是*而该操作符的另一个操作数指向的是第三部分 b ∗ ( c d ) b*(cd) b∗(cd)因此这一部分是有左右操作数 a b 、 b ∗ ( c d ) ab、b*(cd) ab、b∗(cd)与其操作符*共同组成我们记录下第四部分 ( a b ) ∗ ( b ∗ ( c d ) ) (ab)*(b*(cd)) (ab)∗(b∗(cd))第四部分的 ( a b ) ∗ ( b ∗ ( c d ) ) (ab)*(b*(cd)) (ab)∗(b∗(cd))作为操作数时其操作符是而该操作符的另一个操作数指向的是*下面我们继续查找*的左右操作数 *指向的左操作数是操作符右操作数是e其左操作数的操作符指向的事操作数c和d因此该部分我们记为 ( c d ) ∗ e (cd)*e (cd)∗e第四部分的操作数与*这部分的操作数与操作符共同组成了第五部分我们记录下第五部分 ( a b ) ∗ ( b ∗ ( c d ) ) ( ( c d ) ∗ e ) (ab)*(b*(cd))((cd)*e) (ab)∗(b∗(cd))((cd)∗e) 第五部分的 ( a b ) ∗ ( b ∗ ( c d ) ) ( ( c d ) ∗ e ) (ab)*(b*(cd))((cd)*e) (ab)∗(b∗(cd))((cd)∗e)作为操作数时其操作符为*该操作符指向的另一个操作数为*这里我们将操作符*记为*1操作数的*记为*2下面我们继续查找*2的左右操作数 *2指向的左右操作数分别是和e而操作符指向的左右操作数为c和d因此该部分为 ( c d ) ∗ e (cd)*e (cd)∗e第五部分与*2部分作为操作数与操作符*1共同组成了第六部分因此我们记录下第六部分 ( ( a b ) ∗ ( b ∗ ( c d ) ) ( ( c d ) ∗ e ) ) ∗ ( ( c d ) ∗ e ) ((ab)*(b*(cd))((cd)*e))*((cd)*e) ((ab)∗(b∗(cd))((cd)∗e))∗((cd)∗e) 第六部分已经无法作为操作数继续向上查找因此第六部分就为该DAG图所描述的表达式我们将该表达式中多余的()删除后就得到了最终的表示式 ( ( a b ) ∗ ( b ∗ ( c d ) ) ( c d ) ∗ e ) ∗ ( ( c d ) ∗ e ) ((ab)*(b*(cd))(cd)*e)*((cd)*e) ((ab)∗(b∗(cd))(cd)∗e)∗((cd)∗e)
结语
通过本文的探讨我们深入理解了有向无环图DAG 的核心价值 空间高效性将表达式 ((ab)(b(cd))(cd)e)((cd)*e) 的存储节点从二叉树的21个压缩至DAG的12个节省了42% 的存储空间 依赖可视化通过分层合并与结点共享如复用 (cd) 子式直观呈现计算逻辑中的复用关系 应用普适性为编译器优化、任务调度等需要管理依赖关系的场景提供了天然解决方案 核心洞察DAG通过有向性建立执行顺序通过无环性保障逻辑可行性这正是解决复杂依赖问题的关键 DAG的精妙远不止于此 在下一篇内容中我们将解锁DAG的杀手级应用—— 拓扑排序Topological Sorting 当需要确定任务执行顺序如课程学习计划、项目依赖管理时 当依赖关系复杂但必须保证无死锁执行时 当Git提交历史需要线性化输出时
我们将揭秘 ✅ 如何将DAG转化为线性序列 ✅ Kahn算法与DFS实现的双重解析 ✅ 动态任务调度系统的底层逻辑 剧透亮点拓扑排序本质上是对DAG的BFS/DFS高阶应用这与我们在最短路径中讨论的BFS算法形成了奇妙的知识闭环
如果本文让您对图论有了新的认识 点赞 - 支持原创技术干货
⭐ 收藏 - 构建您的算法知识库 转发 - 分享给更多开发者伙伴 评论 - 留下您的思考 “工作中遇到的DAG应用场景” “最想了解的拓扑排序实现细节”
下期预告用拓扑排序解决课程学习顺序规划的经典问题我们不见不散
