너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth-First Search) 시각화하기

이 예제에서는 그래프의 노드와 간선을 강조 표시하여 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

테이블 T의 값은 탐색을 시각화하는 데 유용합니다. 함수 visualize_search.m은 bfsearch와 dfsearch를 통해 수행한 탐색의 결과를 사용하여 이벤트 테이블 T를 기준으로 그래프의 노드와 간선을 강조 표시하는 한 가지 방법을 보여줍니다. 이 함수는 알고리즘의 각 단계를 수행하기 전에 일시 중지되므로, 아무 키나 눌러 탐색을 순차적으로 느리게 실행할 수 있습니다.

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

너비 우선 탐색(Breadth-First Search)과 깊이 우선 탐색(Depth-First Search) 시각화하기

참고 항목

관련 항목