Documentation ¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Kruskal ¶
Kruskal 法によって最小全域木 (Minimum Spanning Tree) を構築する. クラスカル法では,予めコストが低い順に辺をソートしておき, 辺の数がゼロのグラフにコストの低い辺から追加していく. 辺は閉路ができない限り追加し,追加が完了した後次の辺の処理へと進む. 閉路の確認にはUnionFindを利用し,各頂点が連結済みかをもって判断する. 最小全域木を構築するにあたり,与えられるグラフ es は連結であると仮定する.
Example ¶
V, E := 7, 9 es := []Edge{ {0, 3, 1}, {1, 2, 10}, {1, 3, 2}, {2, 4, 5}, {3, 4, 7}, {3, 5, 3}, {4, 5, 1}, {4, 6, 8}, {5, 6, 5}, } cost := Kruskal(V, E, es) fmt.Println(cost)
Output: 17
Types ¶
type Dijkstra ¶
Dijkstra は,始点sから全頂点への最短経路を O(E*log(V)) で求めるアルゴリズム. 優先度付きキューを降順で使う場合にはPへの代入時にマイナスをかければよい.
Example ¶
V, _, r := 4, 5, 0 args := []struct { from, to, cost int }{ {0, 1, 1}, {0, 2, 4}, {1, 2, 2}, {2, 3, 1}, {1, 3, 5}, } d := NewDijkstra(V) for _, arg := range args { d.AddEdge(arg.from, arg.to, arg.cost) } dist := d.Do(r) for _, v := range dist { fmt.Println(v) }
Output: 0 1 3 4
func NewDijkstra ¶
type Scc ¶
type Scc struct { N int // グラフの頂点数 G [][]int // グラフの隣接リスト表現 RG [][]int // 辺の向きを逆にしたグラフ Vs []int // 帰りがけ順の並び Visited []bool Cmp []int // グラフに属する強連結成分のトポロジカル順序 }
Example ¶
args := []struct { from, to int }{ {1, 2}, {2, 1}, {2, 3}, {4, 3}, {4, 1}, {1, 4}, {2, 3}, } n, m := 4, 7 scc := NewScc(n) for i := 0; i < m; i++ { a, b := args[i].from, args[i].to a-- b-- scc.AddEdge(a, b) } scc.Do() mp := make(map[int]int) for _, v := range scc.Cmp { mp[v]++ } ans := 0 for _, v := range mp { if v == 1 { continue } ans += v * (v - 1) / 2 } fmt.Println(ans)
Output: 3
Click to show internal directories.
Click to hide internal directories.