【C#】グラフの連結成分を調べるアルゴリズムを実装してみる

はじめに

今回はグラフの連結成分を調べるアルゴリズムを実装してみようと思います。

そもそもグラフの連結成分とは「任意の2点間に道があるグラフのうち、極大な連結部分グラフ」のことをいいます。

以下の画像のようなグラフだと{0, 1}，{2, 3, 4}，{5, 6, 7}の3つの連結成分があることになります。

3つの連結成分があるグラフ

概要が掴めたところで早速実装とアルゴリズムについてみていきましょう。

グラフの定義

頂点・辺の重みなどがないシンプルなグラフは「頂点のラベルとその頂点からの接続先の頂点集合」の集合で表すことができます。

// 実装例
// int型のラベル，接続先の頂点のラベルのリスト
private Dictionary<int, List<int>> graph;

これをもとにもう少し実用的なコードを書いてみました。

/// <summary>
/// グラフ
/// </summary>
/// <typeparam name="T">頂点のラベルの型</typeparam>
public class Graph<T>
{
    public enum Type
    {
        DirectedGraph,      // 有向グラフ
        UndirectedGraph,    // 無向グラフ
    }

    /// <summary>
    /// グラフ上の全頂点 <ラベル，接続先の頂点集合>
    /// </summary>
    public IReadOnlyDictionary<T, List<T>> Vertices => _vertices;
    private readonly Dictionary<T, List<T>> _vertices;

    /// <summary>
    /// グラフの種類(有向グラフ or 無向グラフ)
    /// </summary>
    public Type GraphType { get; }

    public Graph(Type type)
    {
        _vertices = new Dictionary<T, List<T>>();
        GraphType = type;
    }

    public Graph(Type type, IEnumerable<(T, List<T>)> vertices) : this(type)
    {
        foreach (var v in vertices)
            _vertices[v.Item1] = v.Item2;
    }

    /// <summary>
    /// 頂点を追加する
    /// </summary>
    public void AddVertex(T label)
        => _vertices[label] = new List<T>();

    /// <summary>
    /// 頂点を追加する
    /// </summary>
    public void AddVertex(T label, IEnumerable<T> to)
    {
        AddVertex(label);
        foreach (var v in to)
            _vertices[label].Add(v);
    }

    /// <summary>
    /// 頂点数を取得する
    /// </summary>
    public int GetVertexCount()
        => _vertices.Count;

    /// <summary>
    /// 辺を追加する
    /// </summary>
    /// <param name="from">接続元の頂点</param>
    /// <param name="to">接続先の頂点</param>
    /// <returns>追加できたか</returns>
    public bool AddEdge(T from, T to)
    {
        if (!_vertices.ContainsKey(from) || !_vertices.ContainsKey(to)) return false;

        _vertices[from].Add(to);
        if (GraphType == Type.UndirectedGraph) _vertices[to].Add(from);
        return true;
    }

    /// <summary>
    /// 辺数を取得する
    /// </summary>
    /// <returns></returns>
    public int GetEdgeCount()
    {
        var count = _vertices.Aggregate(0, (sum, v) => sum += v.Value.Count);
        if (GraphType == Type.DirectedGraph) return count;
        else return count / 2;
    }

    /// <summary>
    /// グラフの辺集合を取得する
    /// </summary>
    /// <returns>辺のコレクション(<接続元のラベル, 接続先のラベル>)</returns>
    public IEnumerable<(T, T)> GetEdges()
    {
        if (GraphType == Type.DirectedGraph)
        {
            foreach (var v in _vertices)
                foreach (var to in v.Value)
                    yield return (v.Key, to);
        }
        else if (GraphType == Type.UndirectedGraph)
        {
            var memo = new Dictionary<T, List<T>>();
            foreach (var v in _vertices)
                foreach (var to in v.Value)
                {
                    if (!memo.ContainsKey(to)) memo[to] = new List<T>();
                    if (memo[to].Contains(v.Key)) continue;
                    yield return (v.Key, to);
                    if (!memo.ContainsKey(v.Key)) memo[v.Key] = new List<T>();
                    memo[v.Key].Add(to);
                }
        }
    }
}

ちゃんとしたのを書こうとすると長くなってしまうのは仕方ありませんね。。。

連結成分を調べる

連結成分を調べるには以下のステップをとればOKです。

1. 全頂点に未訪問の印をつける

2.未訪問の頂点集合から頂点(=u)を一つ取り出し、連結成分のカウントをインクリメントする

3.頂点uから深さ優先探索をし，頂点uに連結している頂点に訪問済みの印をつける

4.2に戻るが、全ての頂点が訪問済みだった場合は5に進む

5.連結成分のカウントを出力する

計算時間はo(|V| + |E|)となります。

実装

public static class ConnectedComponentCounter<T>
{
    /// <summary>
    /// 実行する
    /// </summary>
    /// <param name="graph">グラフ</param>
    /// <returns>連結成分の数</returns>
    public static int Execute(Graph<T> graph)
    {
        // 「探索済み」かどうかを格納する Dictionary<ラベルT, 探索済みかどうかbool>
        var isSeen = graph.Vertices.Select(v => v.Key)
            .ToDictionary(label => label, label => false);
        var count = 0;

        // 全ての頂点において、未探索ならDFSを行う
        foreach(var v in graph.Vertices)
        {
            if (!isSeen[v.Key])
            {
                count++;
                DepthFirstSerch(v.Key, graph, isSeen);
            }
        }

        return count;
    }

    /// <summary>
    /// DFSで探索済みのラベルをつけていく
    /// </summary>
    private static void DepthFirstSerch(T startVertex, Graph<T> graph, Dictionary<T, bool> isSeen)
    {
        var stack = new Stack<T>();
        stack.Push(startVertex);
        isSeen[startVertex] = true;

        while(stack.Count != 0)
        {
            T state = stack.Pop();
            foreach(var to in graph.Vertices[state])
            {
                if (!isSeen[to])
                {
                    isSeen[to] = true;
                    stack.Push(to);
                }
            }   
        }
    }
}

今回とそんなに関係ないですが、実装するにあたって状態(フィールド)を持たないような純関数として実装した方がいいと思います。

競プロをやっている方とかは馴染みがない？かもしれませんが、大規模なプロジェクトでは設計・テストが非常に重要で、純関数として定義しておけばテストが圧倒的にしやすくなります。

でないとDIといった技術を使ったりなどなど面倒なことになってきますしね。

使い方

使い方の一例はこんな感じ。

private static void Main(string[] args)
{
    var graph = new Graph<int>(Graph<int>.Type.UndirectedGraph);

    for (int i = 0; i < 8; i++)
        graph.AddVertex(i);

    graph.AddEdge(0, 1);

    graph.AddEdge(2, 3);
    graph.AddEdge(3, 4);
    graph.AddEdge(4, 2);

    graph.AddEdge(5, 6);
    graph.AddEdge(6, 7);

    var count = ConnectedComponentCounter<int>.Execute(graph);
    Console.WriteLine($"連結成分の数 : {count}");                 // 3
}

入力グラフ