algorithm - 基于可用资源，如何在Go中构造依赖关系图？

Question

例如:

步骤1:
有四个寄存器

[r1，r2，r3，r4]

步骤2(输入):
示例说明为:

g1[r1, r3]
g2[r4]
g3[r3]
g4[r2]
g5[r1, r3]
g6[r1]

g1 [r1，r3]表示指令g1正在使用寄存器r1和r3。
因此，具有r1或r3或同时具有r1或r3的任何其他指令只能在g1即g3之后执行，因为它们是相关的。

但是，g2的寄存器是备用的，因此它是独立的，因此可以与g1并行执行。执行g1之后，g3也变得独立。

步骤3(并非必需):
根据上述说明，可以(手动绘制)图形的可视化示例:



步骤4:
Go代码如下所示:

package main

import (
  "fmt"
  "github.com/twmb/algoimpl/go/graph"
)

func main() {
  g := graph.New(graph.Directed)

  instruction := make(map[string]graph.Node, 0)
  instruction["g1"] = g.MakeNode()
  instruction["g2"] = g.MakeNode()
  instruction["g3"] = g.MakeNode()
  instruction["g4"] = g.MakeNode()
  instruction["g5"] = g.MakeNode()
  instruction["g6"] = g.MakeNode()

  for key, node := range instruction {
    *node.Value = key
  }
  // Connect dependent edges
  g.MakeEdge(instruction["g1"], instruction["g3"])
  g.MakeEdge(instruction["g1"], instruction["g5"])
  g.MakeEdge(instruction["g3"], instruction["g5"])
  g.MakeEdge(instruction["g5"], instruction["g6"])

  sorted := g.TopologicalSort()
  for i := range sorted {
      fmt.Println(*sorted[i].Value)
  }
}

问题:

目前，我正在手动连接从属边。但是，如果输入指令的数量增加，将无法进行手动连接。因此，我想知道如何编写将基于Input自动构建依赖关系图的代码(步骤1和步骤2)。

这将是DAG，并且将使用拓扑排序对执行顺序进行排序，并且输出将是

步骤5(输出):
以上代码的示例输出(可以采用不同的形式):

g1，g2，g4，g3，g5，g6

Answer 1

Rosetta Code中的Go中的this拓扑分类器对您有帮助吗？