Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson

最小木問題:

クラスカルのアルゴリズム

1. Set i=1 and let E₀={}
2. Select an edge e_i of minimum value not in E_i-1 such that T_i=<E_i-1 cup {e_i} >is acyclic and define E_i=E_i-1 cup {e_i}. If no such edge exists, Let T=<E_i>and stop.
3. Replace i by i+1. Return to Step 2.

JavaScript ソースファイル:

• kruskal.js, graph.js, qsort.js

JavaScript デモ

• a (6,10) graph
• a (5,8) graph
• a (10,19) graph
• a (8,12) graph
• a (6,12) graph
• a (11,22) graph
• a (14,22) graph

関連ページ:

• Minimum Spanning Tree by Prim's Algorithm
• Shortest Path by Dijkstra's Algorithm
• Max Flow by Ford-Fulkerson's Labeling Algorithm
• Simplex Method