幅優先探索と深さ優先探索の可視化
この例では、グラフのノードとエッジを強調表示することにより bfsearch
と dfsearch
の結果を可視化する関数の定義方法を示します。
有向グラフを作成してプロットします。
s = [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10]; t = [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2]; G = digraph(s,t); plot(G)
グラフに対して深さ優先探索を実行します。アルゴリズムでのすべてのイベントを返すよう 'allevents'
を指定します。また、グラフ内のすべてのノードが確実に検索されるよう Restart
を true
に設定します。
T = dfsearch(G, 1, 'allevents', 'Restart', true)
T = 38x4 table Event Node Edge EdgeIndex ________________ ____ __________ _________ startnode 1 NaN NaN NaN discovernode 1 NaN NaN NaN edgetonew NaN 1 7 1 discovernode 7 NaN NaN NaN edgetonew NaN 7 3 10 discovernode 3 NaN NaN NaN edgetodiscovered NaN 3 1 3 edgetonew NaN 3 5 4 discovernode 5 NaN NaN NaN edgetonew NaN 5 4 8 discovernode 4 NaN NaN NaN edgetonew NaN 4 2 7 discovernode 2 NaN NaN NaN edgetonew NaN 2 6 2 discovernode 6 NaN NaN NaN edgetodiscovered NaN 6 4 9 finishnode 6 NaN NaN NaN finishnode 2 NaN NaN NaN finishnode 4 NaN NaN NaN finishnode 5 NaN NaN NaN edgetofinished NaN 3 6 5 edgetonew NaN 3 8 6 discovernode 8 NaN NaN NaN edgetodiscovered NaN 8 7 11 finishnode 8 NaN NaN NaN finishnode 3 NaN NaN NaN finishnode 7 NaN NaN NaN finishnode 1 NaN NaN NaN startnode 9 NaN NaN NaN discovernode 9 NaN NaN NaN edgetofinished NaN 9 1 12 edgetofinished NaN 9 6 13 edgetofinished NaN 9 8 14 finishnode 9 NaN NaN NaN startnode 10 NaN NaN NaN discovernode 10 NaN NaN NaN edgetofinished NaN 10 2 15 finishnode 10 NaN NaN NaN
table T
内の値は検索の可視化に便利です。関数 visualize_search.m
は、bfsearch
と dfsearch
で実行した検索の結果を使用して、イベントの table T
に従ってグラフ内のノードとエッジを強調表示する 1 つの方法を示しています。この関数はアルゴリズムの各ステップの前で一時停止するため、任意のキーを押すことで、検索をゆっくりステップ実行できます。
visualize_search.m
を現在のフォルダーに保存します。
function visualize_search(G,t) % G is a graph or digraph object, and t is a table resulting from a call to % BFSEARCH or DFSEARCH on that graph. % % Example inputs: G = digraph([1 2 3 3 3 3 4 5 6 7 8 9 9 9 10], ... % [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2]); % t = dfsearch(G, 1, 'allevents', 'Restart', true); % Copyright 1984-2019 The MathWorks, Inc. isundirected = isa(G, 'graph'); if isundirected % Replace graph with corresponding digraph, because we need separate % edges for both directions [src, tgt] = findedge(G); G = digraph([src; tgt], [tgt; src], [1:numedges(G), 1:numedges(G)]); end h = plot(G,'NodeColor',[0.5 0.5 0.5],'EdgeColor',[0.5 0.5 0.5], ... 'EdgeLabelMode', 'auto'); for ii=1:size(t,1) switch t.Event(ii) case 'startnode' highlight(h,t.Node(ii),'MarkerSize',min(h.MarkerSize)*2); case 'discovernode' highlight(h,t.Node(ii),'NodeColor','r'); case 'finishnode' highlight(h,t.Node(ii),'NodeColor','k'); otherwise if isundirected a = G.Edges.Weight; b = t.EdgeIndex(ii); edgeind = intersect(find(a == b),... findedge(G,t.Edge(ii,1),t.Edge(ii,2))); else edgeind = t.EdgeIndex(ii); end switch t.Event(ii) case 'edgetonew' highlight(h,'Edges',edgeind,'EdgeColor','b'); case 'edgetodiscovered' highlight(h,'Edges',edgeind,'EdgeColor',[0.8 0 0.8]); case 'edgetofinished' highlight(h,'Edges',edgeind,'EdgeColor',[0 0.8 0]); end end nodeStr = t.Node; if isnumeric(nodeStr) nodeStr = num2cell(nodeStr); nodeStr = cellfun(@num2str, nodeStr, 'UniformOutput', false); end edgeStr = t.Edge; if isnumeric(edgeStr) edgeStr = num2cell(edgeStr); edgeStr = cellfun(@num2str, edgeStr, 'UniformOutput', false); end if ~isnan(t.Node(ii)) title([char(t{ii, 1}) ' on Node ' nodeStr{ii}]); else title([char(t{ii, 1}) ' on Edge (' edgeStr{ii, 1} ', '... edgeStr{ii, 2},') with edge index ' sprintf('%d ', t{ii, 4})]); end disp('Strike any key to continue...') pause end disp('Done.') close all
G
グラフと検索結果 T
に対して visualize_search.m
を実行するには、次のコマンドを使用します。
visualize_search(G,T)
グラフは最初全体がグレーで表示されますが、キーを押すたびに新しい検索結果が表示されていきます。検索結果は次のように強調表示されます。
'startnode'
- 開始ノードのサイズが "増大" します。'discovernode'
- ノードは検出されると "赤" になります。'finishnode'
- ノードは検索終了後 "黒" になります。'edgetonew'
- 検出されていないノードに向かっているエッジは "青" になります。'edgetodiscovered'
- 検出されたノードに向かっているエッジは "マゼンタ" になります。'edgetofinished'
- 検索終了したノードに向かっているエッジは "緑" になります。
この .gif
アニメーションは、visualize_search.m
の結果をステップ実行したときの表示内容を示しています。
参考
bfsearch
| dfsearch
| graph
| digraph