graph

Documentation

Overview

Package graph は隣接リスト表現のグラフに対する BFS / DFS / Dijkstra を提供する。

Index

• func BFS(g AdjList, src int) []int
• func DFS(g AdjList, src int) []int
• func Dijkstra(g AdjList, src int) []int64
• type AdjList
• type Edge

Functions

func BFS

func BFS(g AdjList, src int) []int

BFS は src から幅優先探索を行い、各到達可能ノードへの辺数距離を返す。 到達不能なノードは距離 -1。

func DFS

func DFS(g AdjList, src int) []int

DFS は src から反復版の深さ優先探索を行い、訪問したノードを発見順に返す。

func Dijkstra

func Dijkstra(g AdjList, src int) []int64

Dijkstra は非負重みグラフで src からの最短距離を計算する。 到達不能ノードは math.MaxInt64 を返す。負の重みがある場合は panic する。

Types

type AdjList

type AdjList [][]Edge

AdjList は隣接リスト表現。AdjList[u] は u を始点とする辺の一覧。

type Edge

type Edge struct {
	To int
	W  int
}

Edge は重み W を持つ有向辺で、終点を To に持つ。