387
个编辑
更改
跳到导航
跳到搜索
第263行：
第263行： − − Directed acyclic graphs may also be used as a compact representation of a collection of sequences. In this type of application, one finds a DAG in which the paths form the given sequences. When many of the sequences share the same subsequences, these shared subsequences can be represented by a shared part of the DAG, allowing the representation to use less space than it would take to list out all of the sequences separately. For example, the directed acyclic word graph is a data structure in computer science formed by a directed acyclic graph with a single source and with edges labeled by letters or symbols; the paths from the source to the sinks in this graph represent a set of strings, such as English words. Any set of sequences can be represented as paths in a tree, by forming a tree vertex for every prefix of a sequence and making the parent of one of these vertices represent the sequence with one fewer element; the tree formed in this way for a set of strings is called a trie. A directed acyclic word graph saves space over a trie by allowing paths to diverge and rejoin, so that a set of words with the same possible suffixes can be represented by a single tree vertex. − − 有向无环图也可用作序列集合的紧凑表示。在这种类型的应用程序中，人们会找到一个 DAG，其中的路径形成给定的序列。当许多序列共享相同的子序列时，这些共享子序列可以由 DAG 的一个共享部分来表示，这使得这种表示比单独列出所有序列所需要的空间更少。例如，有向无环词图是计算机科学中的一种数据结构，由一个单源的有向无环图构成，其边缘用字母或符号标记; 在这个图中，从源到汇的路径表示一组字符串，例如英语单词。任何一组序列都可以表示为树中的路径，方法是为序列的每个前缀形成一个树顶点，并使其中一个顶点的父顶点表示只有一个元素的序列; 对于一组字符串以这种方式形成的树称为 trie。有向无环词图允许路径发散和重新连接，从而在一个三元图上节省空间，这样一组可能具有相同后缀的词可以由一个树顶点表示。
→Data processing networks 数据处理网络
在电子电路设计中，静态组合逻辑电路块可以被表示为由逻辑门组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[35]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。
在电子电路设计中，静态组合逻辑电路块可以被表示为由逻辑门组成的有向无环系统。每个逻辑门对输入做一次函数处理，输入和输出均为一个位元组。通常，这些电路块的输出不能够再作为输入，除非它们被存储在寄存器或者状态单元中，以保证图不出现环。[35]纸上或数据库中的电子电路原理图是一种有向无环图的形式，它使用实例或元件来形成对低级元件的有向引用。电子电路本身不一定是非循环的或定向的。