有向无环图VS树

有向无环图VS树：

前言:

• Big-man在看着 《终极算法》 的时候，突然一个很要好的朋友（是一名程序媛）抛出了一数据结构有关的问题: 有向无环图 VS 树。Big-man想着他们之间有什么差别了，虽然这样想着。但是Big-man还是想着需要去分析一下的。

有向无环图:

定义:

• Big-man首先得去把有向无环图的定义给出:
• 简单的定义: 一个无环的有向图；英文称为Directed Acyclic Graph，简称DAG图。

特点:

• DAG图的特点:
• DAG图是一类较有向树更一般的特殊有向图。
• 如下图所示:
  
  
  
• 以上给出的结构图中从左到右依次是: 树->有向无环图->有向图；
• 检查一个有向图是否存在环要比无向图本身复杂。
• 对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环；而对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。
• 但是，如果从有向图上某个顶点v 出发的遍历，在dfs(v)（即深度优先遍历/深度优先搜索）结束之前出现一条从顶点u 到顶点v 的回边，由于u 在生成树上是v 的子孙，则有向图必定存在包含顶点v 和u 的环。

• 这里可能存在询问什么是深度优先遍历/深度优先搜索(Depth_First_Search)?
• 深度优先遍历/深度优先搜索(英文是Depth_First_Search——简称:DFS)——这个在实际应用当中比较广泛；提到DFS，不得不提到的是图的遍历，因为图的遍历方式当中之一就是深度优先遍历，还有就是广度优先遍历。
• 图的遍历:
• 图的遍历不像树的遍历那样, 图的遍历需要在遍历的过程当中把访问过的顶点打上标记（做个记录），这样做是为了避免重复地去访问被访问过的顶点，一般记录访问过的顶点会定义一个访问数组如:visited[n], n表示图中顶点的个数，初始值为0，访问后设置为1。
• 深度优先遍历：
  • 遍历方式：
    • 对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有的顶点都被访问过为止。
    • DFS其实就是一个递归的过程，就像一棵树的前序遍历。
      
      
      

    （ 对于连通图）从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到。

• 有向无环图的描述含有公共子式的表达式的有效工具。例如下述表达式:
• (a+b) * (b * (c+d)+(c+d) * e) * ((c+d) * e );
• 以上的公式用数据结构图表示 :
  • b、有向无环图:
    
    
    
  • 给出程序分析的结构图出来，相信大家都会觉得是比较一目了然的了，以上的公式(a+b) * (b * (c+d)+(c+d) * e) * ((c+d) * e )你如果仔细观察的话，可以发现一些相同的子表达式，比如说是(c+d)和(c+d)*e等，在二叉树中，它们是会重复出现的，因为需要每一步都进行遍历。
  • 但是如果使用得到是有向无环图的话，则可以实现对相同子式的共享，从而节省储存空间。

  a、二叉树:
  
  
  

• 有向无环图是描述一项工程或系统的进行过程的有效工具。除最简单的情况之外，几乎所有的工程（project）都可分为若干个称作活动（activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。
• 对整个工程和系统，人们关心的是两个方面的问题：
  • 一是工程能否顺利进行;
  • 二是估算整个工程完成所必须的最短时间。

有向无环图的实际应用:

AOV网(Activity on vertex network):

• 所有的工程或者某种流程可以分为若干个小的工程或阶段，这些小的工程或阶段就称为活动。
• 若以图中的顶点来表示活动，有向边表示活动之间的优先关系，则这样活动在顶点上的有向图称为AOV 网。
• 在AOV 网中，若从顶点i 到顶点j 之间存在一条有向路径，称顶点i 是顶点j 的前驱，或者称顶点j 是顶点i 的后继。
• AOV 网中的弧表示了活动之间存在的制约关系。例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。学生按照怎样的顺序来学习这些课程呢？这个问题可以被看成是一个大的工程，其活动就是学习每一门课程。如下表一样:

• 表中，C1、C12 是独立于其它课程的基础课，而有的课却需要有先行课程，比如，学完程序设计导论和数值分析后才能学数据结构……，先行条件规定了课程之间的优先关系。这种优先关系可以用图8.33 所示的有向图来表示。其中，顶点表示课程，有向边表示前提条件。若课程i 为课程j 的先行课，则必然存在有向边〈i,j〉。在安排学习顺序时，必须保证在学习某门课之前，已经学习了其先行课程。如下图所示:
  
  
  
• 类似的AOV 网的例子还有很多，比如大家熟悉的计算机程序，任何一个可执行程序也可以划分为若干个程序段（或若干语句），由这些程序段组成的流程图也是一个AOV 网。

拓扑排序:

• 首先复习一下离散数学中的偏序集合与全序集合两个概念。
• 偏序集合：
  • 若集合A 中的二元关系R 是自反的、非对称的和传递的，则R 是A 上的偏序关系。集合A 与关系R 一起称为一个偏序集合。
• 全序集合：
  • 若R 是集合A 上的一个偏序关系，如果对每个a、b∈A 必有aRb 或bRa ，则R 是A上的全序关系。集合A 与关系R 一起称为一个全序集合。
• 偏序关系经常出现在我们的日常生活中。
  • 例如，若把A看成一项大的工程必须完成的一批活动，则aRb 意味着活动a 必须在活动b 之前完成。比如，对于前面提到的计算机专业的学生必修的基础课与专业课，由于课程之间的先后依赖关系，某些课程必须在其它课程以前讲授，这里的aRb 就意味着课程a 必须在课程b 之前学完。
  • AOV 网所代表的一项工程中活动的集合显然是一个偏序集合。为了保证该项工程得以顺利完成，必须保证AOV 网中不出现回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。测试AOV 网是否具有回路（即是否是一个有向无环图）的方法，就是在AOV 网的偏序集合下构造一个线性序列，该线性序列具有以下性质：
    • 1、在AOV 网中，若顶点i 优先于顶点j ，则在线性序列中顶点i 仍然优先于顶点j；
    • 2、对于网中原来没有优先关系的顶点与顶点，如图8.33 中的C1 与C13，在线性序列中也建立一个先后关系，或者顶点i 优先于顶点j ，或者顶点j 优先于i。
  • 满足这样性质的线性序列称为拓扑有序序列。构造拓扑序列的过程称为拓扑排序。也可以说拓扑排序就是由某个集合上的一个偏序得到该集合上的一个全序的操作。
  • 若某个AOV 网中所有顶点都在它的拓扑序列中，则说明该AOV 网不会存在回路，这时的拓扑序列集合是AOV 网中所有活动的一个全序集合。以图8.21 中的AOV 网例，可以得到不止一个拓扑序列，C1、C12、C4、C13、C5、C2、C3、C9、C7、C10、C11、C6、C8 就是其中之一。显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。

拓扑排序算法

• 对AOV 网进行拓扑排序的方法和步骤是：
  • 1、从AOV 网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；
  • 2、从网中删去该顶点，并且删去从该顶点发出的全部有向边；
  • 3、重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。
• 这样操作的结果有两种：
  • 一种是网中全部顶点都被输出，这说明网中不存在有向回路；
  • 另一种就是网中顶点未被全部输出，剩余的顶点均不前驱顶点，这说明网中存在有向回路。
• 在一个AOV 网上实施上述步骤的例子。如下图所示:
  
  
  
• 这样得到一个拓扑序列：v2,v5,v1,v4,v3,v7,v6。
• 为了实现上述算法，对AOV 网采用邻接表存储方式，并且邻接表中顶点结点中增加一个记录顶点入度的数据域，即顶点结构设为：
  
  
  
• 顶点表结点结构的描述改为：

typedef struct vnode{ /*顶点表结点*/ int count /*存放顶点入度*/ VertexType vertex; /*顶点域*/ EdgeNode * firstedge; /*边表头指针*/ } VertexNode; 

• 当然也可以不增设入度域，而另外设一个一维数组来存放每一个结点的入度。算法中可设置了一个堆栈，凡是网中入度为0 的顶点都将其入栈。为此，拓扑排序的算法步骤为：
  • 1、将没有前驱的顶点（count 域为0）压入栈；
  • 2、从栈中退出栈顶元素输出，并把该顶点引出的所有有向边删去，即把它的各个邻接顶点的入度减1；
  • 3、将新的入度为0 的顶点再入堆栈；
  • 4、重复②～④，直到栈为空为止。此时或者是已经输出全部顶点，或者剩下的顶点中没有入度为0 的顶点。
• 下面给出用C 语言描述的拓扑排序算法的实现。
• 从上面的步骤可以看出，栈在这里的作用只是起到一个保存当前入度为零点的顶点，并使之处理有序。这种有序可以是后进先出，也可以是先进先出，故此也可用队列来辅助实现。在下面给出用C 语言描述的拓扑排序的算法实现中，我们采用栈来存放当前未处理过的入度为零点的结点，但并不需要额外增设栈的空间，而是设一个栈顶位置的指针将当前所有未处理过的入度为零的结点连接起来，形成一个链式栈。

void Topo_Sort (AlGraph *G) { /*对以带入度的邻接链表为存储结构的图G，输出其一种拓扑序列*/ int top = -1； /* 栈顶指针初始化*/ for (i=0；i 
             
               adjlist[i]. Count == 0) { G->adjlist[i].count = top； top = i； } } for (i=0;i 
              
                adjlist[top].count; /* 从栈中退出一个顶点并输出*/ printf(“% c”,G->adjlist[j].vertex); ptr=G->adjlist[j].firstedge; while (ptr!=null) { k=ptr->adjvex; G->adjlist[k].count--; /*当前输出顶点邻接点的入度减1*/ if(G->adjlist[k].count= =0) /*新的入度为0 的顶点进栈*/ { G->adjlist[k].count =top; top=k; } ptr=ptr->next; /*找到下一个邻接点*/ } } } 
               
             

代码诠释有向无环图:

• 下面Big-man将以C/C++代码来诠释有向无环图：

#include 
              
                #include 
               
                 #include 
                
                  using namespace std; typedef struct Node { int lData; //邻接点的信息 Node *nextArc; // 指向下一个节点 } Node; //邻接表中的结点类型 typedef struct { int tData; //顶点的信息 int intDegree; //顶点入度 Node *first; //指向第一个邻接点 }tNode,adjList[100]; //表头节点类型 typedef struct { adjList vextives; int v, e; //邻接表类型 }ALgraph; ALgraph creatGraph() { int m, n, i, j, k; adjList G; Node *L; printf("请输入顶点个数：\n"); scanf("%d", &m); for (int i = 0; i <= m; i++) // 对邻接表的所有顶点初始化 { /* code */ G[i].intDegree = 0; // 顶点的入度值为0 G[i].first = NULL; // 将指向下一个节点置空 } printf("请输入边数:\n"); scanf("%d", &n); for (int i = 0; i <=n; i++) // 依次读入所有边的信息, 并储存在邻接表中 { /* code */ scanf("%d %d", &j, &k); L = (Node *) malloc (sizeof(Node)); // 分配节点 L -> lData = k; L -> nextArc = G[j].first; G[j].first = L; // 将节点插入邻接表中 G[k].intDegree ++; // 使节点的入度加一 } ALgraph al; // 邻接表创建图 for (int i = 0; i <= m; i++) { /* code */ al.vextives[i] = G[i]; } al.v = m; al.e = n; return al; } void Topusort(ALgraph G, int n); int show[50]; // 将入度为0的顶点存入 int g = 0; // 记录存入show[]的顶点数 int k = 50; // 标记图是否存在回路 int t = 0; // 记录一个有向无环图有多少拓扑排序 int visited[50]; // 标记图中的顶点是否被访问过 int main(void) { ALgraph alg; alg = creatGraph(); for(int i = 1; i < 50; i++) { // 将所有节点标记为未被访问 visited[i] = 0; } Topusort(alg, 1); printf("\n 此AOV网共有%d个拓扑排序\n", t); return 0; } void Topusort (ALgraph G, int n) { int i, m = 0; int r[50]; Node *s; int flag = 0; if( k == 1) { return; } k = 50; for(i = 1; i <= G.v; i++) { if(visited[i] == 0) { flag = 1; break; } } if(flag == 0) { for(i = 1; i <= g; i++) { printf("V%d", show[i]); } printf("\n"); t ++; } else { for(i = 1; i <= G.v; i++) { if(G.vextives[i].intDegree == 0 && visited[i] == 0) { k = 0; break; } } if(k != 0) { printf("图中存在环，无法拓扑排序\n"); k = 1; return; } else { for(i = 1; i <= G.v; i++) { if(G.vextives[i].intDegree == 0 && visited[i] == 0) { g++; show[g] = i; visited[i] = 1; s = G.vextives[i].first; while(s != NULL) { int a=s->lData; m ++; r[m] = a; G.vextives[a].intDegree --; s = s->nextArc; } Topusort(G, n+1); visited[i] = 0; g --; for(int j = 1; j <= m; j++) { G.vextives[r[j]].intDegree++; } } } } } } 
                 
                
              

树：

树的定义:

• 树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0 时，称这棵树为空树。在一棵非树T 中：
  • （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。
  • （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm 称为这个根结点的子树。
• 可以看出，在树的定义中用了递归概念，即用树来定义树。因此，树结构的算法类同于二叉树结构的算法，也可以使用递归方法。
• 树的定义还可形式化的描述为二元组的形式：
  • T＝（D，R）
• 其中D为树T 中结点的集合，R为树中结点之间关系的集合。
• 当树为空树时，D＝Φ；当树T 不为空树时有：
• D＝{Root}∪DF
• 其中，Root 为树T 的根结点，DF 为树T的根Root 的子树集合。DF 可由下式表示：
  • DF＝D1∪D2∪…∪Dm 且Di∩Dj＝Φ（i≠j，1≤i≤m，1≤j≤m）
• 当树T 中结点个数n≤1 时，R＝Φ；当树T 中结点个数n>1 时有：
  • R＝{

，i＝1，2，…，m}

• 其中，Root 为树T 的根结点，ri 是树T 的根结点Root 的子树Ti 的根结点。
• 树定义的形式化，主要用于树的理论描述。
• 图7.1(a)是一棵具有9 个结点的树，即T＝{A，B，C，…，H，I}，结点A 为树T 的根结点，除根结点A 之外的其余结点分为两个不相交的集合： T1＝{B,D,E,F,H,I}和T2={C,G}，T1 和T2 构成了结点A 的两棵子树，T1 和T2 本身也分别是一棵树。
• 例如，子树T1 的根结点为B，其余结点又分为两个不相交的集合：T11＝{D}，T12＝{E,H,I}和T13＝{F}。
• T11、T12 和T13 构成了子树T1 的根结点B 的三棵子树。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。
• 从树的定义和图7.1(a)的示例可以看出，树具有下面两个特点：
  • （1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
  • （2）树中所有结点可以有零个或多个后继结点。
• 由此特点可知，图7.1(b)、©、(d)所示的都不是树结构。
  
  
  

相关术语：

• 在二叉树中介绍的有关概念在树中仍然适用。除此之外，再介绍两个关于树的术语。
  • （1）有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。
  • （2）森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。

树的表示：

• 树的表示方法有以下四种，各用于不同的目的。
• 1、直观表示法:
  • 树的直观表示法就是以倒着的分支树的形式表示，图7.1(a)就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。
• 2、嵌套集合表示法:
  • 所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。图7.2 (a)就是一棵树的嵌套集合表示。
• 3、凹入表示法:
  • 树的凹入表示法如图7.2 ©所示。树的凹入表示法主要用于树的屏幕和打印输出。
• 4、广义表表示法:
  • 树用广义表表示，就是将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。图7.2 (b)就是一棵树的广义表表示。

代码诠释树:

JackDan9 Thinking