大家好，我是ProgrammerSpectre。最近在想，软件工程中遇到的很多重要问题，都可以归结为几个简单的问题。只要看看任何一本关于算法的书，它们中的大多数都是排序或搜索集合的一些变体。谷歌存在是因为“哪些文档包含这些短语？”是一个很难解决的问题（好吧，这大大简化了谷歌产品的广泛范围，但基本思想仍然成立）。01什么是拓扑排序？在我的职业生涯中，我一次又一次遇到的常见问题之一是对依赖图的节点进行拓扑排序。换句话说，给定一些DAG——认为可以依赖于其他包的包，或大型公司项目中的任务——对它们进行排序，以便列表中的任何项目都不会依赖于后面的任何内容。假设我们正在做蛋糕，在开始之前，我们需要一些配料。让我们简化一下，假设我们只需要鸡蛋和面粉。嗯，对于鸡蛋，我们需要鸡（相信我，我不是在开玩笑），对于面粉，我们需要谷物。鸡也需要谷物来喂养，而谷物生长需要土壤和水。我们考虑一个表达所有这些依赖关系的图：蛋糕的依赖图该图的一个可能的拓扑顺序是：[]string{"soil","water","grain","chickens","flour","eggs","cake"}但是，还有其他可能的拓扑顺序：[]string{"water","soil","grain","flour","chickens","eggs","cake"}我们也可以把鸡蛋后的面粉，因为唯一依赖鸡蛋的东西就是蛋糕。由于我们可以重新排列项目，我们也可以并行完成其中的一些项目，同时防止任何项目出现在依赖它的任何项目之前。例如，我们可以通过添加一层嵌套来指示内部切片中的所有内容都独立于该切片中的任何其他内容：[][]string{{"soil","water"},{"grain"},{"chickens","flour"},{"eggs"},{"cake"},}从这个图中我们得到了一个很好的“执行计划”来准备蛋糕的依赖关系。首先，我们需要找到一些土壤和水。接下来，我们种植谷物。然后我们养一些鸡，同时做面粉，收集鸡蛋。终于可以做蛋糕了！对于四岁以下的人来说，这似乎是一项繁重的工作，但好事需要时间。02构建依赖关系图现在我们知道该做什么了，让我们考虑如何编写一些代码来构建这个依赖关系列表。我们当然需要跟踪元素本身，我们需要跟踪什么取决于什么。使“X取决于什么？”和“X取决于什么？”高效，我们将跟踪两个方向的依赖关系。我们已经足够了解开始编写代码所需的内容：//Anodeinthisgraphisjustastring,soanodesetisamapwhose//keysarethenodesthatarepresent.typenodesetmap[string]struct{}//depmaptracksthenodesthathavesomedependencyrelationshipto//someothernode,representedbythekeyofthemap.typedepmapmap[string]nodesettypeGraphstruct{nodesnodeset//Maintaindependencyrelationshipsinbothdirections.These//datastructuresaretheedgesofthegraph.//`dependencies`trackschild->parents.dependenciesdepmap//`dependencies`tracksparent->children.dependentsdepmap//Keeptrackofthenodesoftthegraphthemselves.}funcNew()*Graph{return&Graph{dependencies:make(depmap):make(),nodes:make(nodeset),}}这个数据结构应该适合我们的目的，因为它包含了我们需要的所有信息：节点、“依赖”边和“依赖”边。现在让我们考虑创建一个API来向图形添加新的依赖项。我们所需要的只是一种声明某些节点依赖于另一个节点的方法，例如：graph.DependOn("flour","grain")。有几种情况我们要明确禁止。首先，一个节点不能依赖自己，其次，如果面粉依赖谷物，那么谷物一定不能依赖面粉，否则我们将创建一个无限依赖循环。准备就绪后，让我们编写Graph.DependOn()方法。func(g*Graph)DependOn(child,parentstring)error{ifchild==parent{returnerrors.New("self-referentialdependenciesnotallowed")}//TheGraph.DependsOn()methoddoesn'texistyet.//We'llwriteitnext.ifg.DependsOn(parent,child){returnerrors.New("循环依赖不允许")}//Addnodes.g.nodes[parent]=struct{}{}g.nodes[child]=struct{}{}//Addedges.addNodeToNodeset(g.dependencies,parent,child)addNodeToNodeset(g.dependencies,child,parent)returnnil}funcaddNodeToNodeset(dmdepmap,key,nodestring){节点,ok:=dm[key]if!ok{nodes=make(nodeset)dm[key]=nodes}nodes[node]=struct{}{}}这将在我们实现Graph.DependsOn()后有效地向我们的图形添加依赖项。我们可以很容易地判断一个节点是否直接依赖于另一个节点，但我们也想知道是否存在传递依赖。比如，面粉靠粮，粮食靠土，面粉也靠土。这将需要我们获取节点的直接依赖项，然后为每个依赖项获取其依赖项，依此类推，直到我们停止发现新的依赖项。在计算机科学术语中，我们正在计算一个不动点，以在我们的图上找到“DependsOn”关系的传递闭包。func(g*Graph)DependsOn(child,parentstring)bool{deps:=g.Dependencies(child)_,ok:=deps[parent]returnok}func(g*Graph)Dependencies(childstring)nodeset{if_,ok:=g.nodes[root];!ok{returnil}out:=make(nodeset)searchNext:=[]string{root}forlen(searchNext)>0{//Listofnewnodesfromthislayerofthedependencygraph.Thisis//赋值给`searchNext`attheendoftheouter"发现"loop.discovered:=[]string{}for_,node:=rangesearchNext{//Foreachnodetodiscover,findthenextnodes.fornextNode:=rangenextFn(node){//如果我们之前没有看到该节点，也将其添加到输出中//作为节点列表以在扩展中遍历。if_,ok:=out[nextNode];!ok{out[nextNode]=struct{}{}discovered=append(discovered,nextNode)}}}searchNext=discovered}returnout}03对图进行排序既然我们有了图数据结构，我们可以考虑如何节点被顺序删除。如果我们可以发现叶节点——即节点本身不依赖于其他节点——那么我们可以重复获取叶子并将它们从图中移除，直到图为空。在第一次迭代中，我们将找到独立的元素，然后在随后的每次迭代中，我们将找到仅依赖于已删除元素的节点。最终结果将是单个“层”节点的拓扑有序切片。获取图的叶子很简单。我们只需要找到在dependencies中没有条目的节点。这意味着它们不依赖于任何其他节点。func(g*Graph)Leaves()[]string{leaves:=make([]string,0)fornode:=rangeg.nodes{if_,ok:=g.dependencies[node];!ok{leaves=append(leaves,node)}}returnleaves}最后一块拼图实际上是计算图的拓扑排序层。这也是最复杂的一块。我们将遵循的一般策略是迭代地收集叶子并将它们从图中移除，直到图为空。由于我们要改变图，我们希望克隆它以便原始图在执行排序后保持完整，因此我们将继续并实现该克隆：funccopyNodeset(snodeset)nodeset{out:=make(nodeset,len(s))fork,v:=ranges{out[k]=v}returnout}funccopyDepmap(mdepmap)depmap{out:=make(depmap,len(m))fork,v:=range{out[k]=copyNodeset(v)}returnout}func(g*Graph)clone()*Graph{return&Graph{dependencies:copyDepmap(g.dependencies),dependencies:copyDepmap(g.dependents),节点:copyNodeset(g.nodes),}}我们还需要能够从图中删除一个节点和所有边。删除节点就像从每个节点删除出站边缘一样简单。然而，我们在两个方向上跟踪每条边这一事实意味着我们必须做一些额外的工作来删除入站记录。我们将用于删除所有边的策略如下：在dependents中找到节点A的条目。这为我们提供了一组依赖于A的节点。对于这些节点中的每一个，都会在依赖项中找到一个条目。从节点集中删除A。删除节点A在dependents中的条目。执行相反的操作，在依赖项中查找节点A，等等。借助一个允许我们从depmap条目中删除节点的小实用程序，我们可以编写从图中完全删除节点的方法。funcremoveFromDepmap(dmdepmap,key,nodestring){nodes:=dm[key]iflen(nodes)==1{//theonlyelementinthenodesetmustbe`node`,sowe//candeletetheentryentirely.delete(dm,key)}else{//否则，removethesinglenodefromthenodeset.delete(nodes,node)}}func(g*Graph)remove(nodestring){//Removeedgesfromthingsthatdependon`node`.fordependent:=rangeg.dependents[node]{removeFromDepmap(g.dependencies,dependent,node)}delete(g.dependents,node)//Removealledgesfromnodetothethingsitdependency.fordependency:=rangeg.dependencies[node]{removeFromDepmap(g.dependencies,dependency,node)}delete(g.dependencies,node)//最后，removethenodeitself.delete(g.nodes,node)}最后，我们可以实现Graph.TopoSortedLayers()：func(g*Graph)TopoSortedLayers()[][]string{layers:=[][]string{}//CopythegraphshrinkingGraph:=g.clone()for{leaves:=shrinkingGraph.Leaves()iflen(leaves)==0{break}layers=append(layers,leaves)for_,leafNode:=rangeleaves{shrinkingGraph.remove(leafNode)}}returnlayers}这种方法清楚地概述了我们对图进行拓击排序的策略：克隆图，这样我们就可以迭代地转换它以将图的叶子收集到输出“层”中。收集后移除每一层。当图为空时，返回收集的层。现在我们可以回到最初的蛋糕制作问题，以确保我们的图形为我们解决了这个问题：packagemainimport("fmt""strings""github.com/kendru/darwin/go/depgraph")funcmain(){g:=depgraph.New()g.DependOn("cake","eggs")g.DependOn("cake","flour")g.DependOn("eggs","chickens")g.DependOn("flour","谷物")g.DependOn("鸡","谷物")g.DependOn("谷物","土壤")g.DependOn("谷物","水")g.DependOn("鸡","水")fori,layer:=rangeg.TopoSortedLayers(){fmt.Printf("%d:%s\n",i,strings.Join(layer,","))}//输出：//0：土壤,water//1:grain//2:flour,chickens//3:eggs//4:cake}所有这些工作都不是小菜一碟，但现在我们有了一个几乎可以用于任何事物的依赖图是拓扑排序的。您可以在GitHub上找到[1]本文的完整代码。这个实现有一些明显的局限性，我想挑战你改进它，以便它可以：存储不是简单字符串的节点允许单独添加节点和边缘/依赖信息生成字符串输出用于调试原始链接：https：//kendru.github.io/go/2021/10/26/sorting-a-dependency-graph-in-go/参考[1]在GitHub上找到：https://github.com/kendru/darwin/tree/main/go/depgraph本文转载自微信公众号“鬼”，您可以通过以下二维码关注。转载本文请联系有鬼公众号。
