BreadthFirstDirectedPaths | algorithms-ts

This implementation uses breadth-first search. The constructor takes time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.

Type parameters

V

Hierarchy

BreadthFirstDirectedPaths

Implements

DirectedPaths<V>

Index

Constructors

constructor

Properties

Methods

Constructors

constructor

new BreadthFirstDirectedPaths(G: Digraph<V>, source: Vertex<V>): BreadthFirstDirectedPaths

- Defined in graphs/BreadthFirstDirectedPaths.ts:21
Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.

Parameters
- G: Digraph<V>
  
  the digraph
- source: Vertex<V>
  
  the source vertex
Returns BreadthFirstDirectedPaths

Properties

Private edgeTo

edgeTo: StringMap<object> = new StringMap<Vertex<V>>()

Private marked

marked: StringMap<boolean> = new StringMap<boolean>()

Private source

source: Vertex<V>

the source vertex

Methods

Private bfs

bfs(G: Digraph<V>, source: Vertex<V>): void

- Defined in graphs/BreadthFirstDirectedPaths.ts:33
Parameters
- G: Digraph<V>
- source: Vertex<V>
Returns void

hasPathTo

hasPathTo(v: Vertex<V>): boolean

Implementation of DirectedPaths.hasPathTo
- Defined in graphs/BreadthFirstDirectedPaths.ts:49
Parameters
- v: Vertex<V>
Returns boolean

pathTo

pathTo(v: Vertex<V>): Collection<Vertex<V>>

Implementation of DirectedPaths.pathTo
- Defined in graphs/BreadthFirstDirectedPaths.ts:53
Parameters
- v: Vertex<V>
Returns Collection<Vertex<V>>

Generated using TypeDoc