graph

Documentation

Index

• func GetD2S[T comparable](t Tree[T], src, dst T) []T
• func GetFitD2S[T comparable](t Tree[T], src, dst T) []T
• func GetFitS2D[T comparable](t Tree[T], src, dst T) []T
• func GetS2D[T comparable](t Tree[T], src, dst T) []T
• type DegreeFunc
• type GraphMap
  • func (x GraphMap[T]) Adjacency(prev T) []T
  • func (x GraphMap[T]) BFS(s T) GraphMapTree[T]
  • func (x GraphMap[T]) BreadthFirstSearch(s T, max_degree int, degree DegreeFunc[T]) GraphMapTree[T]
  • func (x GraphMap[T]) DFS(s T) GraphMapTree[T]
  • func (x GraphMap[T]) DepthFirstSearch(s T, max_degree int, degree DegreeFunc[T]) GraphMapTree[T]
  • func (x GraphMap[T]) NewTree() Tree[T]
• type GraphMapTree
  • func (x GraphMapTree[T]) Get(next T) (T, bool)
  • func (x GraphMapTree[T]) Set(next, prev T)
• type Grapher
• type Searcher
• type Tree
  • func BFS[T comparable](x Searcher[T], s T) Tree[T]
  • func BreadthFirstSearch[T comparable](x Searcher[T], s T, max_degree int, degree DegreeFunc[T]) Tree[T]
  • func DFS[T comparable](x Searcher[T], s T) Tree[T]
  • func DepthFirstSearch[T comparable](x Searcher[T], s T, max_degree int, degree DegreeFunc[T]) Tree[T]
  • func Dijkstra[T comparable](g Grapher[T], s T) Tree[T]
• type Weight

Functions

func GetD2S

func GetD2S[T comparable](t Tree[T], src, dst T) []T

func GetFitD2S

func GetFitD2S[T comparable](t Tree[T], src, dst T) []T

func GetFitS2D

func GetFitS2D[T comparable](t Tree[T], src, dst T) []T

func GetS2D

func GetS2D[T comparable](t Tree[T], src, dst T) []T

Types

type DegreeFunc

type DegreeFunc[T any] func(u, v T) int

u: 前节点 v: 后节点

type GraphMap

type GraphMap[T comparable] map[T][]T

func (GraphMap[T]) Adjacency

func (x GraphMap[T]) Adjacency(prev T) []T

func (GraphMap[T]) BFS

func (x GraphMap[T]) BFS(s T) GraphMapTree[T]

breadth-first search

func (GraphMap[T]) BreadthFirstSearch

func (x GraphMap[T]) BreadthFirstSearch(s T, max_degree int, degree DegreeFunc[T]) GraphMapTree[T]

func (GraphMap[T]) DFS

func (x GraphMap[T]) DFS(s T) GraphMapTree[T]

Depth-first search

func (GraphMap[T]) DepthFirstSearch

func (x GraphMap[T]) DepthFirstSearch(s T, max_degree int, degree DegreeFunc[T]) GraphMapTree[T]

func (GraphMap[T]) NewTree

func (x GraphMap[T]) NewTree() Tree[T]

type GraphMapTree

type GraphMapTree[T comparable] map[T]T

func (GraphMapTree[T]) Get

func (x GraphMapTree[T]) Get(next T) (T, bool)

func (GraphMapTree[T]) Set

func (x GraphMapTree[T]) Set(next, prev T)

type Grapher

type Grapher[T comparable] interface {
	Adjacency(prev T) []T
	NewTree() Tree[T]
	Weight(prev T, next T) int
}

type Searcher

type Searcher[T comparable] interface {
	Adjacency(prev T) []T
	NewTree() Tree[T]
}

type Tree

type Tree[T comparable] interface {
	Get(next T) (T, bool)
	Set(next, prev T)
}

如果生成树是从起点开始遍历的结果 则每次Set的都是子节点对应的父节点，每次Get的都是子节点的父节点 eg: GetS2D[T](t, start, end)返回从起点到终点的路径, GetD2S[T](t, start, end)返回从终点到起点的路径 如果生成树是从终点开始遍历 GetS2D[T](t, end, start) 返回从终点到起点的路径，GetD2S[T](t, end, start)返回从起点到终点的路径

func BFS

func BFS[T comparable](x Searcher[T], s T) Tree[T]

func BreadthFirstSearch

func BreadthFirstSearch[T comparable](x Searcher[T], s T, max_degree int, degree DegreeFunc[T]) Tree[T]

s : 起始位置 max_degree : 限制深度

func DFS

func DFS[T comparable](x Searcher[T], s T) Tree[T]

func DepthFirstSearch

func DepthFirstSearch[T comparable](x Searcher[T], s T, max_degree int, degree DegreeFunc[T]) Tree[T]

func Dijkstra

func Dijkstra[T comparable](g Grapher[T], s T) Tree[T]

type Weight

type Weight interface {
	Add(Weight) Weight
	Less(Weight) bool
}