アルゴリズム図鑑 増補改訂版 絵で見てわかる33のアルゴリズム

No.



4-7

 クラスカル法は、グラフの最小全域木を求めるアルゴリズムです。辺にコストの付いた辺重み

付きグラフが与えられたとき、そのグラフから辺を選んで、選んだ辺だけを使ってすべての頂点

をつなげます。ただし、選んだ辺のコストの総和が最小となるようにします。



4-1



p.088

2

2

45 5 8

1 2

66 3

7

B E

C F

GDA

図のグラフ入さ選ていいはグレーていは

1

つ

選てい

2

2

45 5 8

1 2

66 3

7

B E

C F

GDA

2

2

45 5 8

1 2

66 3

7

B E

C F

GDA

コストの一さい

B, C

とて選

択

の選と

B

と

C

つり

選いの選と

定については

4-2

照

てさい



4-2



p.092

01

02 03

とて選は



選と定は

レンジ



2

2

45 5 8

1 2

66 3

7

B E

C F

GDA

2

2

45 5 8

1 2

66 3

7

B E

C F

GDA

ていいのコストの一さい



E, F

とて選択

じコストの数合はに ...