ユーザー定義関数でDFSを実行

[PR]当サイトはアフィリエイト広告を利用しています。

今回は自作の関数の中身をグラフ探索用DFSに変更して、DFSを実行するユーザー定義関数を作成していきます。

まず対象とするグラフはこれです。

そしてコード全体は以下です。

Option Explicit

Function graph(arg As Range, startV As Integer)
    Dim c As Variant
    Dim rnum As Integer
    Dim i As Integer
    Dim j As Integer
    Dim graphArray() As Integer
    Dim vnumArray() As Integer
    Dim vertex As Integer
    vertex = startV
    rnum = arg.Rows.Count
    Dim vnumArrayVert() As Integer
    ReDim vnumArray(rnum - 1)
    ReDim vnumArrayVert(rnum - 1, 0)
    ReDim graphArray(rnum - 1, rnum - 1)
    For i = 0 To rnum - 1
        vnumArray(i) = 0
    Next i
    c = arg.Value
    For i = 0 To rnum - 1
        For j = 0 To rnum - 1
            graphArray(i, j) = c(i + 1, j + 1)
        Next j
    Next i
    Call dfs(graphArray, vnumArray, vertex, rnum)
    For i = 0 To rnum - 1
        vnumArrayVert(i, 0) = vnumArray(i)
    Next i
    graph = vnumArrayVert
End Function

Sub dfs(graph() As Integer, vnumArray() As Integer, vertex As Integer, vnum As Integer)
    Dim i As Integer
    vnumArray(vertex) = 1
    For i = 0 To vnum - 1
        If graph(vertex, i) = 1 Then
            If vnumArray(i) = 0 Then
                Call dfs(graph, vnumArray, i, vnum)
            End If
        End If
    Next i
End Sub

コードの解説をしていきます。

Function graph(arg As Range, startV As Integer)
    Dim c As Variant
    Dim rnum As Integer
    Dim i As Integer
    Dim j As Integer
    Dim graphArray() As Integer
    Dim vnumArray() As Integer
    Dim vertex As Integer
    vertex = startV
    rnum = arg.Rows.Count
    Dim vnumArrayVert() As Integer
    ReDim vnumArray(rnum - 1)
    ReDim vnumArrayVert(rnum - 1, 0)
    ReDim graphArray(rnum - 1, rnum - 1)
    For i = 0 To rnum - 1
        vnumArray(i) = 0
    Next i
    c = arg.Value
    For i = 0 To rnum - 1
        For j = 0 To rnum - 1
            graphArray(i, j) = c(i + 1, j + 1)
        Next j
    Next i

3行目のユーザー定義関数の引数にstartVが追加されています。

これがどのノードから始めるかという情報です。

そして10行目でその情報を格納する変数vertexを宣言して11行目で代入しています。

それ以外は以前のコードと同じです。

隣接行列を配列に読み込んでいます。

これまでは配列aryに情報を読み込んでいましたが、今回は配列graphArrayに変更されています。

大きさは隣接行列と同じです。

もう一つ変更点がありました。

9行目と13行目でvnumArrayとvnumArrayVertという配列を宣言していました。

vnumArrayが探索済みのノードの情報を格納する配列、vnumArrayVertがその配列を縦に出力するための配列です。

例えばノード1が探索済みならvnumArrayは[0,1,0,0,0,0]となります。

14行目と15行目でその大きさを調整しています。

ここからDFS本体です。

Sub dfs(graph() As Integer, vnumArray() As Integer, vertex As Integer, vnum As Integer)
    Dim i As Integer
    vnumArray(vertex) = 1
    For i = 0 To vnum - 1
        If graph(vertex, i) = 1 Then
            If vnumArray(i) = 0 Then
                Call dfs(graph, vnumArray, i, vnum)
            End If
        End If
    Next i
End Sub

詳細は以前Pythonで作成したDFSもご覧ください。

35行目で呼び出されたときのノードを探索済みにします。

36行目から42行目で、

もし今のノードとつながったノードがあって

未探索なら

再び自身の関数を呼び出す。

という再帰処理をしています。

ちなみに引数の解説をすると

graph()は隣接行列の情報。

vnumArray()は探索済みのノードの情報。

vertexが現在のノードの情報。

vnumがグラフの全ノード数です。

再びユーザー定義関数に戻ります。

    Call dfs(graphArray, vnumArray, vertex, rnum)
    For i = 0 To rnum - 1
        vnumArrayVert(i, 0) = vnumArray(i)
    Next i
    graph = vnumArrayVert
End Function

26行目でDFSを実行しています。

27行目から29行目で探索済みノードの格納されたvnumArrayの情報を、縦に表示するための配列vnumArrayVertに移動させています。

そして30行目で出力となります。

ノード1からユーザー定義関数Graphを実行してみると

ノード1,3,4がつながっていることが示せました。

以上「ユーザー定義関数でDFSを実行する」でした。