bfsearch

グラフの幅優先検索

構文

v = bfsearch(G,s)

T = bfsearch(G,s,events)

[T,E] = bfsearch(G,s,events)

[___] = bfsearch(___,'Restart',tf)

説明

v = bfsearch(G,s) は、幅優先検索をグラフ G にノード s から適用します。結果は、検出順のノード ID からなるベクトルです。

T = bfsearch(G,s,events) は 1 つ以上の検索イベントにフラグを設定して、幅優先検索の出力をカスタマイズします。たとえば、T = bfsearch(G,s,'allevents') はフラグが設定されたすべてのイベントを含むテーブルを返し、X = bfsearch(G,s,'edgetonew') はエッジの行列または cell 配列を返します。

さらに、[T,E] = bfsearch(G,s,events) は、events が 'edgetonew'、'edgetodiscovered'、または 'edgetofinished' に設定されている場合に、エッジ インデックス E のベクトルを返します。エッジ インデックスは、多重グラフでエッジを一意に識別します。

[___] = bfsearch(___,'Restart',tf) で、tf が true の場合、検出したノードから到達可能な新しいノードがない場合に検索を再開します。前述の構文にある任意の入力引数または出力引数の組み合わせが使用できます。このオプションにより、開始ノード s からは到達できないノードやエッジがある場合でも、幅優先検索でグラフ内のすべてのノードおよびエッジに確実に到達します。

例

グラフの幅優先検索の実行

グラフを作成してプロットします。

s = [1 1 1 1 2 2 2 2 2];
t = [3 5 4 2 6 10 7 9 8];
G = graph(s,t);
plot(G)

ノード 2 からグラフの幅優先検索を実行します。結果はノードの検出順序を示します。

v = bfsearch(G,2)

v = 10×1

     2
     1
     6
     7
     8
     9
    10
     3
     4
     5

すべてのイベントを指定したグラフの幅優先検索

有向グラフを作成してプロットします。

s = [1 1 1 2 3 3 3 4 6];
t = [2 4 5 5 6 7 4 1 4];
G = digraph(s,t);
plot(G)

ノード 1 からグラフの幅優先検索を実行します。'allevents' を指定して、アルゴリズムのすべてのイベントを含む table を返します。

T = bfsearch(G,1,'allevents')

T=14×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             1     NaN    NaN       NaN   
    discovernode          1     NaN    NaN       NaN   
    edgetonew           NaN       1      2         1   
    discovernode          2     NaN    NaN       NaN   
    edgetonew           NaN       1      4         2   
    discovernode          4     NaN    NaN       NaN   
    edgetonew           NaN       1      5         3   
    discovernode          5     NaN    NaN       NaN   
    finishnode            1     NaN    NaN       NaN   
    edgetodiscovered    NaN       2      5         4   
    finishnode            2     NaN    NaN       NaN   
    edgetofinished      NaN       4      1         8   
    finishnode            4     NaN    NaN       NaN   
    finishnode            5     NaN    NaN       NaN   

アルゴリズムのステップを追跡するには、テーブル内のイベントを上から下に読み取ります。以下に例を示します。

1. アルゴリズムがノード 1 で開始されます。

2. ノード 1 とノード 2 の間のエッジが検出されます。

3. ノード 2 が検出されます。

4. 以下同様です。

複数の要素をもつグラフの幅優先検索

複数の要素をもつグラフの幅優先検索を実行し、検索結果に基づいてグラフのノードおよびエッジを強調表示します。

有向グラフを作成してプロットします。このグラフには、弱連結要素が 2 つあります。

s = [1 1 2 2 2 3 4 7 8 8 8 8];
t = [3 4 7 5 6 2 6 2 9 10 11 12];
G = digraph(s,t);
p = plot(G,'Layout','layered');

c = conncomp(G,'Type','weak')

c = 1×12

     1     1     1     1     1     1     1     2     2     2     2     2

ノード 2 からグラフの幅優先検索を実行し、'edgetonew'、'edgetofinished' および 'startnode' のイベントにフラグを設定します。Restart を true に指定して、到達できないノードが残っている場合は必ず検索を再開します。

events = {'edgetonew','edgetofinished','startnode'};
T = bfsearch(G,2,events,'Restart',true)

T=15×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           2     NaN    NaN       NaN   
    edgetonew         NaN       2      5         3   
    edgetonew         NaN       2      6         4   
    edgetonew         NaN       2      7         5   
    edgetofinished    NaN       7      2         8   
    startnode           1     NaN    NaN       NaN   
    edgetonew         NaN       1      3         1   
    edgetonew         NaN       1      4         2   
    edgetofinished    NaN       3      2         6   
    edgetofinished    NaN       4      6         7   
    startnode           8     NaN    NaN       NaN   
    edgetonew         NaN       8      9         9   
    edgetonew         NaN       8     10        10   
    edgetonew         NaN       8     11        11   
    edgetonew         NaN       8     12        12   

Restart が true の場合、'startnode' イベントはアルゴリズムが検索を再開する位置と時点に関する情報を返します。

イベントに基づいてグラフを強調表示します。

• 開始ノードを赤色にします。

• 緑のエッジは 'edgetonew'

• 黒のエッジは 'edgetofinished'

highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g')
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') 
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

グラフが 2 部グラフかどうかの判定

幅優先検索を使用してグラフが 2 部グラフかどうかを判定し、関連区画を返します。2 部グラフとは、グラフ内のノードを A および B の 2 セットに分割でき、グラフ内の各エッジが A のノードと B のノードを連結するグラフです。

有向グラフを作成してプロットします。

s = [1 1 1 1 2 2 4 5 6 7 8];
t = [2 3 6 8 5 10 6 6 10 3 10];
g = digraph(s,t);
plot(g);

グラフの幅優先検索を使用して 2 部グラフかどうかを判定し、2 部グラフである場合は関連区画を返します。

events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;

for ii=1:size(T, 1)   
    if is_edgetonew(ii)
        partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
    else
        if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
            is_bipart = false;
            break;
        end
    end
end

is_bipart

is_bipart = logical
   1

g は 2 部グラフであるため、変数 partitions は各ノードが属する区画に関する情報を含みます。

'layered' レイアウトを指定し、変数 partitions を使用して 1 番目の層に現れるソース ノードを指定して、2 部グラフをプロットします。

partitions

partitions = 1x10 logical array

   0   1   1   0   0   1   0   1   0   0

plot(g, 'Layout', 'layered', 'Source', find(partitions));

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

入力グラフ。graph オブジェクトまたは digraph オブジェクトとして指定します。無向グラフの作成には graph を、有向グラフの作成には digraph を使用します。

例: G = graph(1,2)

例: G = digraph([1 2],[2 3])

s — 開始ノード

ノード インデックス | ノード名

開始ノード。次の表のいずれかの値として指定します。

値	例
スカラー ノード インデックス	1
文字ベクトルのノード名	'A'
string スカラーのノード名	"A"

例: bfsearch(G,1)

events — フラグが設定された検索イベント

'discovernode' (既定値) | 'startnode' | 'finishnode' | 'edgetonew' | 'edgetodiscovered' | 'edgetofinished' | 'allevents' | cell 配列 | string 配列

フラグが設定された検索イベント。次の表のいずれかのオプションとして指定します。

• 単一のイベントにフラグを設定するには、フラグ名を使用します。

• イベントのサブセットにフラグを設定するには、2 つ以上のフラグ名を cell 配列または string 配列に入れます。

• すべてのイベントにフラグを設定するには、'allevents' を使用します。

メモ

events の値により、bfsearch の出力は異なります。各オプションにより返される出力については、次の表の最後の列を参照してください。

events の値	説明	出力
'discovernode' (既定)	新しいノードが検出されました。	ノード ID のベクトルを返します。 s が数値ノード インデックスの場合、ベクトルは数値ノード インデックスを含みます。 s がノード名の場合、ベクトルはノード名を含む cell 配列です。
'finishnode'	ノードから出るすべてのエッジが訪問されました。
'startnode'	このフラグは検索の開始ノードを示します。 'Restart' が true である場合、'startnode' は検索が再開されるたびに開始ノードにフラグを設定します。
'edgetonew'	エッジは未検出のノードに連結しています。	グラフ エッジの終了ノードを示す、サイズが N 行 2 列の行列または cell 配列を返します。 s が数値ノード インデックスの場合、行列は数値ノード インデックスを含みます。 s がノード名の場合、行列はノード名を含む cell 配列です。 また、エッジ インデックス E のベクトルを返す [T,E] = bfsearch(…) で 2 つ目の出力を指定できます。
'edgetodiscovered'	エッジは以前検出したノードに連結しています。
'edgetofinished'	エッジは終了ノードに連結しています。
cell 配列	検索中にイベントに設定する 2 つ以上のフラグを cell 配列で指定します。	変数 T.Event、T.Node、T.Edge、および T.EdgeIndex を含むテーブル T を返します。 T.Event は発生順にフラグを含む categorical ベクトルです。 T.Node は、イベント 'discovernode'、'finishnode' および 'startnode' に対応するノードのノード ID を含みます。 T.Edge は、イベント 'edgetonew'、'edgetodiscovered' および 'edgetofinished' に対応するエッジを含みます。 T.EdgeIndex には、イベント 'edgetonew'、'edgetodiscovered'、および 'edgetofinished' のエッジ インデックスが含まれます。エッジ インデックスは、多重グラフで繰り返されるエッジを一意に識別します。 T.Node および T.Edge の未使用の要素は NaN に設定されます。 s が数値ノード インデックスの場合、T.Node および T.Edge は数値ノード インデックスを含みます。 s がノード名の場合、T.Node および T.Edge はノード名を含む cell 配列です。
'allevents'	すべてのイベントにフラグが設定されます。

例: v = bfsearch(G,3) は 3 番目のノードから検索を開始し、ノードを検出順に含むベクトル v を返します。これは、v = bfsearch(G,3,'discovernode') と同じです。

例: X = bfsearch(G,'A','edgetonew') では 'A' という名前のノードから開始して、cell 配列 X を返します。これは、検索中に未検出のノードに連結している個々のエッジを示します。

例: T = bfsearch(G,s,{'discovernode','finishnode'}) はテーブル T を返しますが、新しいノードが検出された場合、あるいはノードが終了としてマークされた場合にのみフラグを設定します。

例: T = bfsearch(G,s,'allevents') はすべての検索イベントにフラグを設定し、table T を返します。

データ型: char | string | cell

tf — 検索を再開するかどうかのトグル

false (既定値) | true

検索を再開するかどうかのトグル。false (既定値) または true として指定します。開始ノードから到達できないノードがグラフに含まれる場合、このオプションが便利です。'Restart' が true の場合、検出済みのノードから到達できない未検出のノードが残っているときには常に検索が再開されます。新しい開始ノードは、最小のインデックスをもつ未検出のノードです。bfsearch がすべてのノードを検出するまで、再開プロセスが繰り返されます。

'Restart' の既定値は false であり、検索では開始ノードから到達可能なノードのみが訪問されます。

'Restart' が true の場合、'discovernode' および 'finishnode' のイベントは、グラフの各ノードで 1 回発生します。また、グラフの各エッジには、'edgetonew'、'edgetodiscovered' または 'edgetofinished' によりフラグが 1 回設定されます。'edgetonew' によりフラグが設定されるエッジは、1 つ以上の木を構成します。

例: T = bfsearch(graph([1 3],[2 4]),1,'Restart',true) は、グラフ内の両方の連結要素を検索します。

データ型: logical

出力引数

v — ノード ID

数値列ベクトル | cell ベクトル

ノード ID。次のいずれかの形式で返されます。

• 数値ノード ID を使用して開始ノード s を指定した場合、v はノード インデックスの数値列ベクトルです。

• s がノード名を含む文字ベクトルまたは string である場合、v はノード名を含む cell ベクトルです。

v のノード ID は、グラフの幅優先検索で検出された順序を反映します。

T — 検索結果

table | ベクトル | 行列 | ノード名の cell 配列

検索結果。次のいずれかの形式で返されます。

• events が指定されていない場合、あるいは 'discovernode'、'finishnode' または 'startnode' である場合、T は v と同様なノード ID のベクトルです。

• events が 'edgetonew'、'edgetodiscovered' または 'edgetofinished' である場合、T はサイズが N 行 2 列の行列または cell 配列であり、各関連エッジのソース ノードとターゲット ノードを示します。

• events が検索イベントの cell 配列または 'allevents' である場合、T はフラグの設定された検索イベントを含む table です。この table は、T.Event の検索イベントのフラグ、T.Node の関連ノード ID および T.Edge と T.EdgeIndex の関連エッジを含みます。

すべての場合で、次のようになります。

• T の要素または行の順序は、検索中に発生した順序を示します。

• s を数値ノード ID として指定した場合、T も数値 ID を使用してノードを表します。

• s をノード名として指定した場合、T もその名前を使用してノードを表します。

E — エッジ インデックス

ベクトル

エッジ インデックス。ベクトルとして返されます。

この出力を指定して、イベント 'edgetonew'、'edgetodiscovered'、または 'edgetofinished' のエッジ インデックスのベクトルを取得します。エッジ インデックスの N 行 1 列のベクトルは T に対応します。これはサイズが N 行 2 列の行列または cell 配列であり、各関連エッジのソース ノードとターゲット ノードを示します。

例: [T,E] = bfsearch(G,s,'edgetonew')

ヒント

• dfsearch および bfsearch は有向グラフと無向グラフを同様に扱います。ノード s とノード t の間の無向エッジは、s から t へと、t から s への双方向エッジと同様に扱われます。

アルゴリズム

幅優先検索アルゴリズムは開始ノード s から開始し、ノード インデックスの順序でその隣接ノードをすべて検査します。次に、それらの隣接ノードのそれぞれについて、順番に未訪問の隣接ノードを訪問します。開始ノードから到達可能なすべてのノードが訪問されるまで、アルゴリズムが継続します。

このアルゴリズムは、疑似コードで次のように記述できます。

Event startnode(S)
Event discovernode(S)
NodeList = {S}

WHILE NodeList is not empty

  C = NodeList{1}
  Remove first element from NodeList
  
  FOR edge E from outgoing edges of node C, connecting to node N
    Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E)
    (depending on the state of node N)
    IF event was edgetonew
      Event discovernode(N)
      Append N to the end of NodeList
    END
  END

  Event finishnode(C)
END

bfsearch は、新しいノードが検出された時点、あるノードから出るすべてのエッジが訪問された時点など、アルゴリズム内での異なるイベントを表すフラグを返すことができます。イベントのフラグを次の表に示します。

イベントのフラグ	イベントの説明
'discovernode'	新しいノードが検出されました。
'finishnode'	ノードから出るすべてのエッジが訪問されました。
'startnode'	このフラグは検索の開始ノードを示します。
'edgetonew'	エッジは未検出のノードに連結しています。
'edgetodiscovered'	エッジは以前検出したノードに連結しています。
'edgetofinished'	エッジは終了ノードに連結しています。

詳細は、events の入力引数の説明を参照してください。

メモ

開始ノードから到達できないノードが入力グラフに含まれている場合、'Restart' オプションにより検索でグラフ内の各ノードを訪問できます。この場合、'startnode' イベントは検索が再開されるたびに開始ノードを示します。

バージョン履歴

R2015b で導入

参考

dfsearch | conncomp | graph | digraph

トピック

• 幅優先探索と深さ優先探索の可視化

×

例を開く

この例の変更されたバージョンがあります。編集された方の例を開きますか?

いいえ、変更されたバージョンを上書きします。 はい