Documentation
¶
Overview ¶
Package graph demonstrates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal
Index ¶
- Variables
- func ArticulationPoint(graph *Graph) []bool
- func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int)
- func DepthFirstSearch(start, end int, nodes []int, edges [][]bool) ([]int, bool)
- func DepthFirstSearchHelper(start, end int, nodes []int, edges [][]bool, showroute bool) ([]int, bool)
- func GetIdx(target int, nodes []int) int
- func LowestCommonAncestor(tree *Tree)
- func NotExist(target int, slice []int) bool
- func Topological(N int, constraints [][]int) []int
- type Edge
- type Graph
- func (g *Graph) AddEdge(one, two int)
- func (g *Graph) AddVertex(v int)
- func (g *Graph) AddWeightedEdge(one, two, weight int)
- func (g *Graph) BellmanFord(start, end int) (isReachable bool, distance int, err error)
- func (g *Graph) Dijkstra(start, end int) (int, bool)
- func (g *Graph) FindAllCycles() []Graph
- func (g *Graph) HasCycle() bool
- type ITree
- type Item
- type Tree
- type TreeEdge
- type UnionFind
- type Vertex
- type WeightedGraph
Constants ¶
This section is empty.
Variables ¶
var Inf = math.Inf(1)
Defining maximum value. If two vertices share this value, it means they are not connected
Functions ¶
func ArticulationPoint ¶
ArticulationPoint is a function to identify articulation points in a graph. The function takes the graph as an argument and returns a boolean slice which indicates whether a vertex is an articulation point or not. Worst Case Time Complexity: O(|V| + |E|) Auxiliary Space: O(|V|) reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-point
func BreadthFirstSearch ¶
BreadthFirstSearch is an algorithm for traversing and searching graph data structures. It starts at an arbitrary node of a graph, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Worst-case performance O(|V|+|E|)=O(b^{d})}O(|V|+|E|)=O(b^{d}) Worst-case space complexity O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) reference: https://en.wikipedia.org/wiki/Breadth-first_search
func DepthFirstSearch ¶
func DepthFirstSearchHelper ¶
func LowestCommonAncestor ¶
func LowestCommonAncestor(tree *Tree)
For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. Let's call `jump[j][u]` is the `2^j`-th ancestor above the node `u` with `u` in range `[0, numbersVertex)`, `j` in range `[0,MAXLOG)`. These information allow us to jump from any node to any ancestor above it in `O(MAXLOG)` time.
func Topological ¶
Topological assumes that graph given is valid and that its possible to get a topological ordering. constraints are array of []int{a, b}, representing an edge going from a to b
Types ¶
type Graph ¶
type Graph struct {
Directed bool // Differentiate directed/undirected graphs
// contains filtered or unexported fields
}
Graph provides a structure to store the graph. It is safe to use its empty object.
func (*Graph) AddVertex ¶
AddVertex will add a new vertex in the graph. If the vertex already exists it will do nothing.
func (*Graph) AddWeightedEdge ¶
AddWeightedEdge will add a new weighted edge between the provided vertices in the graph
func (*Graph) BellmanFord ¶
func (*Graph) FindAllCycles ¶
this function can do HasCycle() job but it is slower
type UnionFind ¶
type UnionFind struct {
// contains filtered or unexported fields
}
Defining the union-find data structure
func NewUnionFind ¶
Initialise a new union find data structure with s nodes
type WeightedGraph ¶
type WeightedGraph [][]float64
WeightedGraph defining matrix to use 2d array easier
func FloydWarshall ¶
func FloydWarshall(graph WeightedGraph) WeightedGraph
FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm
Source Files
Directories