Documentation
¶
Overview ¶
Package coloring provides implementation of different graph coloring algorithms, e.g. coloring using BFS, using Backtracking, using greedy approach. Author(s): [Shivam](https://github.com/Shivam010)
Index ¶
- func BipartiteCheck(N int, edges [][]int) bool
- type Color
- type Graph
- func (g *Graph) AddEdge(one, two int)
- func (g *Graph) AddVertex(v int)
- func (g *Graph) ColorUsingBFS() (map[int]Color, int)
- func (g *Graph) ColorUsingBacktracking() (map[int]Color, int)
- func (g *Graph) ColorUsingGreedyApproach() (map[int]Color, int)
- func (g *Graph) TryBipartiteColoring() map[int]Color
- func (g *Graph) ValidateColorsOfVertex(colors map[int]Color) error
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BipartiteCheck ¶
basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartite
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph provides a structure to store an undirected 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 exist it will do nothing
func (*Graph) ColorUsingBFS ¶
ColorUsingBFS will return the Color of each vertex and the total number of different colors used, using BFS
func (*Graph) ColorUsingBacktracking ¶
ColorUsingBacktracking will return the Color of each vertex and the total number of different colors used, using backtracking
func (*Graph) ColorUsingGreedyApproach ¶
ColorUsingGreedyApproach will return the Color of each vertex and the total number of different colors used, using a greedy approach, based on the number of edges (or degree) from any vertex.
Source Files