graph

Documentation

Overview

Package graph demonstates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal

Index

• func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int)
• func DepthFirstSearch(start, end int, nodes []int, edges [][]bool) ([]int, bool)
• func GetIdx(target int, nodes []int) int
• func NotExist(target int, slice []int) bool
• type Matrix
  • func FloydWarshall(graph Matrix) Matrix

Functions

func BreadthFirstSearch

func BreadthFirstSearch(start, end, nodes int, edges [][]int) (isConnected bool, distance int)

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 DepthFirstSearch(start, end int, nodes []int, edges [][]bool) ([]int, bool)

func GetIdx

func GetIdx(target int, nodes []int) int

func NotExist

func NotExist(target int, slice []int) bool

Types

type Matrix

type Matrix [][]float64

Matrix Defining matrix to use 2d array easier

func FloydWarshall

func FloydWarshall(graph Matrix) Matrix

FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm