Golang多键树,带并行搜索
#go #tree #parllel #tread

golang软件包树是带有任何方向节点的树的纯golang实现。树上的每个节点都可以与许多孩子联系在一起,并有许多父母。

Image description

在实施这棵树时,父母与孩子没有什么不同。树元素包含对分支的引用,而无需指定是父母还是孩子。

元素中的每个节点参考都包含一个路径成本,该路径成本在计算从点A到点的路径时考虑了。点A和B之间的路径使用线程(并行)计算,以最大程度地减少查找所有路径的时间。

这棵树没有根。树上的路径可以循环。

树元素可以存储任何数据结构。创建树时定义了此结构。

请参阅创建树及其元素的代码部分:

t := tree.New[TreeData]("My first element")

// Create new tree elements (first element and end point element)
e := t.New("My first element")
ep := t.New("End point")

// Create children of e (first element) element
ch1, _ := e.Add(t.New("My first child"))
ch2, _ := e.Add(t.New("My second child"), tree.WayOptions{Cost: 3.0})
ch4, _ := e.Add(t.New("My fourth child"), tree.WayOptions{Cost: 3.0})

// Create sub children elements
ch3, _ := ch2.Add(t.New("Some third child"))
ch3.Add(ch4)

// Add children to ep (end point) element
ch1.Add(ch4)
ch2.Add(ep)
ch4.Add(ep)

// Set oneway path from ep (end point) to e (first element) element
ep.Add(e, tree.WayOptions{Cost: 5.0, Oneway: true})

// Print tree started from e (first element) element
fmt.Printf("\nPrint tree:\n%v\n\n", e)

最后一个printf的结果:

. My first element
├── My first child, cost: 1.00
│   ├── My fourth child, cost: 1.00
│   │   ├── My first element, cost: 3.00 🡡
│   │   ├── Some third child, cost: 1.00
│   │   │   ├── My second child, cost: 1.00
│   │   │   │   ├── My first element, cost: 3.00 🡡
│   │   │   │   ├── Some third child, cost: 1.00 🡡
│   │   │   │   └── End point, cost: 1.00
│   │   │   │       ├── My second child, cost: 1.00 🡡
│   │   │   │       ├── My fourth child, cost: 1.00 🡡
│   │   │   │       └── My first element, cost: 5.00 (one way road) 🡡
│   │   │   └── My fourth child, cost: 1.00 🡡
│   │   ├── My first child, cost: 1.00 🡡
│   │   └── End point, cost: 1.00 🡡
│   └── My first element, cost: 1.00 🡡
├── My second child, cost: 3.00 🡡
├── My fourth child, cost: 3.00 🡡
└── End point, cost: 5.00 (way not allowed) 🡡

请参见代码以及更多描述和示例:https://github.com/kirill-scherba/tree