連結グラフ 判定アルゴリズム

目次

はじめに

見に来てくださってありがとうございます。ちなみに初投稿です。
このページでは、タイトル通り、与えられたグラフが「連結グラフ」であるかどうかを判定するアルゴリズムについて説明していきます。

キーワード

グラフ理論、連結グラフ、つながっている、隣接、探索、深さ優先探索(DFS)、頂点、道

対象の方

グラフ理論の基本事項をご存じな方が対象です。具体的には、キーワードにおいて、「深さ優先探索」以外のものをご存じな方となります。また、プログラムは「Python」で書いております。

理解のコツ

アルゴリズムグラフ理論が好きでない方は下記にあるGif画像(動く画像)を中心に御覧になることをおすすめ致します。さらに練習問題も用意致しましたので、よろしければそちらもご覧ください。また閲覧する順番は以下がおすすめです。
1.「直感的な方法」の節でなんとなく理解
2.「練習問題」の章で自分の理解が正しいかを確認
3.「アルゴリズムの詳細」の節でアルゴリズムを厳密に理解する
4.「ソースコード」の章でプログラムを理解する
 

アルゴリズム

直観的な方法

 

f:id:inninzityou:20180228144715g:plain
連結グラフ判定アルゴリズム
※画像の説明:青や赤で括られた頂点は現在注目している(探索中の)ものを表しています。また、頂点の外にある数字は、頂点の番号で、中に書いてあるのはラベル付けの際に利用した数字です。

まず、直観的な方法について説明いたします。また、直観的な方法ですので、曖昧な部分があります。そこは「アルゴリズムの詳細」の方で解決いたします。
深さ優先探索(幅優先探索でも可能)と呼ばれるアルゴリズムを用いて頂点にラベル付け(印をつけること)していく。
すなわち、現在注目している(探索中の)頂点と隣接している頂点の中で、まだ探索していないものを新たに探索しラベル付けする。また、その条件にあてはまらない場合は前に探索した頂点を再び探索する(ここの表現は曖昧)。最終的にすべての頂点がラベル付けされていれば与えられたグラフは連結グラフである。そうでなければ連結グラフではない。
 

アルゴリズムの詳細

前提条件

  • グラフGは無向グラフとする
  • 位数(頂点の数)をp(>=1)
  • サイズ(辺の数)をq(>=0)
  • V(G)={v_0,v_1,v_2,...,v_(p-1)}
  • E(G)={e_0,e_1,e_2,...,e_(q-1)}

Step1. labelに0を代入。
Step2. v_0のラベルをlabelとする。
Step3. v_0に隣接している頂点をvとしStep5へ。隣接している点が存在しなかった場合はStep8へ。
Step4. vに隣接かつ未探索である頂点を新たにvとし、Step5へ。その条件にあてはまる頂点が存在しない場合はStep7へ。
Step5. labelにlabel+1を代入する。
Step6. vのラベルをlabelとし、Step4へ。
Step7. 隣接している頂点の中で現在探索中のラベルより小さい中で一番(ラベルの)番号が近い頂点を選びStep4へ。もし、現在探索中のラベルが0だった場合はStep8へ。
Step8. 全ての頂点がラベル付けされていたらグラフGは連結グラフ。そうでなければ連結グラフではない。

ソースコード

このコードでは「隣接行列」と呼ばれるものを使って、グラフをコードに落とし込んでいます。ご存じない方は「隣接行列」を調べてから、このコードを読むことをおすすめします。

class Graph:
    #グラフを表す

    # 頂点につけるlabelの初期値(ラベリングされていないことを示す値)
    no_labeling_num = -1

    class Vertex:
        # 頂点を表す

        def __init__(self, g, no, label):
            """

            :param g: グラフを表す。またVertexを所有するオブジェクトでもある
            :param no: 頂点にグラフのなかで一意に割り振られた識別用の番号
            :param label: 探索された順番を表す番号。ラベル。
            """
            self.no = no
            self.g = g
            self.label = label

        def __str__(self):
            """
             
            """
            return "no:{0},label:{1}".format(self.no,self.label)

        def adjacentVs(self):
            """ selfと隣接している頂点のリストを返す

            :return:
            """
            result = []
            for c in range(self.g.order):
                if self.g.aDJM[self.no][c] == 1:
                    result.append((self.g.vs[c]))
            return result

        def back_to_previous(self):
            """ 前に探索した頂点を返す(厳密な表現ではない)
            詳細
            ・この頂点に隣接する頂点において、ラベル付けされていない(未探索)なものがないときに、
            次に探索する頂点を返す関数
            ・自身のラベル番号より小さい頂点の中で一番近いものを返す
            ・存在しないときは「None」を返す

            :return:
            """
            result = None
            vs = list(filter(lambda x: self.label > x.label, self.adjacentVs()))
            if vs != []:
                result = vs[0]
                key0 = self.label - result.label
                for v in vs:
                    key1 = self.label - v.label
                    if (key1 < key0):
                        key0 = key1
                        result = v

            return result

    def __init__(self, aDJM):
        """
        
        :param aDJM:隣接行列
        """
        self.aDJM = aDJM
        self.order = len(aDJM)
        self.vs = [Graph.Vertex(self, i, self.no_labeling_num) for i in range(self.order)]

    def no_labelingVs(self, vs):
        """ 渡された頂点リストにおいてlabelingされていない頂点のリストを返す

        :return:
        """
        result = []
        for v in vs:
            if v.label == self.no_labeling_num:
                result.append(v)
        return result

    def isconnected(self):
        """ このグラフが連結グラフであるかどうかを判定する
        
        :return:
        """
        label = 0
        v = self.vs[0]
        v.label = label
        # 最初に探索した頂点が孤立点である場合に対処するための条件
        if v.adjacentVs()==[]:
            v=None
        else:
            v = v.adjacentVs()[0]
            label += 1
            v.label = label
        while (v != None):  # 現在探索中の頂点のラベルが0かつその点に隣接する頂点すべてが探索ずみだったら終了するようにする
            vs = self.no_labelingVs(v.adjacentVs())
            if vs == []:
                v = v.back_to_previous()
            else:
                v = vs[0]
                label += 1
                v.label = label

        return not(self.no_labeling_num in list(map(lambda x:x.label,self.vs)))

# 隣接行列
aDJM = [[0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
        [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
        [1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        ]

g=Graph(aDJM)

print(g.isconnected())

練習問題

 以下の図において、今回紹介したアルゴリズムに基づいてラベル付けをしてみてください。

f:id:inninzityou:20180306162321p:plain
練習問題1
 
f:id:inninzityou:20180306162522p:plain
練習問題1_解答

解説
 他の手順、解答も存在します。例えば、v_0の次にv_1に注目していますが、v_3、もしくはv_5でも構いません。なお、この解説では、どこに注目し、ラベル付けしたのかということしか書いておりません。詳しい情報は上記の「アルゴリズム」などの項目をご覧ください。

v_0に注目(を探索)
v_0に0とラベル付け(印をつける)

v_1に注目(を探索)
v_1に1とラベル付け(印をつける)

v_2に注目(を探索)
v_2に2とラベル付け(印をつける)

v_1に注目(を探索)

v_0に注目(を探索)

v_3に注目(を探索)
v_3に3とラベル付け(印をつける)

v_4に注目(を探索)
v_4に4とラベル付け(印をつける)

v_3に注目(を探索)

v_0に注目(を探索)

v_5に注目(を探索)
v_5に5とラベル付け(印をつける)

v_0に注目(を探索)
探索終了
すべての頂点がラベル付けされているのでこのグラフは連結グラフである。

f:id:inninzityou:20180306162525p:plain
練習問題2
 
f:id:inninzityou:20180306162528p:plain
練習問題2_解答

解説
v_0に注目(を探索)
v_0に0とラベル付け(印をつける)

v_1に注目(を探索)
v_1に1とラベル付け(印をつける)

v_2に注目(を探索)
v_2に2とラベル付け(印をつける)

v_1に注目(を探索)

v_3に注目(を探索)
v_3に3とラベル付け(印をつける)

v_1に注目(を探索)

v_0に注目(を探索)
探索終了
ラベル付けされていない頂点が存在するので与えられたグラフは連結グラフではない。

追記

 ソースコードについてですが、無理矢理クラスにせず、もっと簡潔に書けば良かったように思えます。書き直すのは面倒なのでお許しください。また、自分は変数を命名するセンスが皆無です。よろしければご教授ください。ちなみに変数の付け方において知っていることは、キャメルケース、スネークケース、クラス名は基本最初が大文字、定数はすべて大文字、Pythonは基本スネークケースなどです。