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
Source Files
Click to show internal directories.
Click to hide internal directories.