Version: v1.0.0-...-e1490ca Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Nov 9, 2014 License: BSD-2-Clause Imports: 2 Imported by: 0



Package dfs implements the depth-first-search algorithm for the graphs.

The DFS is implemented using on demand calculations, meaning that only that part of the search space will be expanded as requested, iteratively expanding it if needed.

Neighbor traversal order currently is random due to the graph implementation. Specific order may be added in the future.

Example (Usage)

Small API demo based on a trie graph and a few disconnected vertices.

package main

import (


func main() {
	// Create the graph
	g := graph.New(7)
	g.Connect(0, 1)
	g.Connect(1, 2)
	g.Connect(2, 3)
	g.Connect(3, 4)
	g.Connect(3, 5)

	// Create the depth first search algo structure for g and source node #2
	d := dfs.New(g, 0)

	// Get the path between #0 (source) and #2
	fmt.Println("Path 0->5:", d.Path(5))
	fmt.Println("Order:", d.Order())
	fmt.Println("Reachable #4 #6:", d.Reachable(4), d.Reachable(6))


Path 0->5: [0 1 2 3 5]
Order: [0 1 2 3 5 4]
Reachable #4 #6: true false




This section is empty.


This section is empty.


This section is empty.


type Dfs

type Dfs struct {
	// contains filtered or unexported fields

Depth-first-search algorithm data structure.

func New

func New(g *graph.Graph, src int) *Dfs

Creates a new random-order dfs structure.

func (*Dfs) Order

func (d *Dfs) Order() []int

Generates the full order in which nodes were traversed.

func (*Dfs) Path

func (d *Dfs) Path(dst int) []int

Generates the path from the source node to the destination.

func (*Dfs) Reachable

func (d *Dfs) Reachable(dst int) bool

Checks whether a given vertex is reachable from the source.

Source Files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL