最小生成木のアルゴリズムと応用
最小生成木は、無向重み付きグラフにおいて、すべてのノードをつなぐことを保証しつつ、選ばれた辺の総和が最小となる構造である。この構造には複数の可能性があり、その中でも総和が最小のものを最小生成木と呼ぶ。n個のノードを持つグラフでは、最小生成木は必ずn-1本の辺で構成される。また、最小生成木にはサイクルが存在しない。
Kruskalアルゴリズムは、最小生成木を ...
8月12日 06:44 投稿
グラフアルゴリズムの実装と応用
グラフの冗長接続検出
無向グラフにおいて、ツリー構造を維持しながら冗長な接続を特定する方法について説明します。
Union-Findによる冗長接続の検出
#include <iostream>
#include <vector>
using namespace std;
class UnionFind {
private:
vector<int> parent;
public:
UnionFind(int n) : parent(n + 1) {
for (int i = 0; i &l ...
6月19日 19:16 投稿