Visualize Breadth-First and Depth-First Search

Open Script

This example shows how to define a function that visualizes the results of bfsearch and dfsearch by highlighting the nodes and edges of a graph.

Create and plot a directed graph.

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)

Perform a depth-first search on the graph. Specify 'allevents' to return all events in the algorithm. Also, specify Restart as true to ensure that the search visits every node in the graph.

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

The values in the table, T, are useful for visualizing the search. The function visualize_search.m shows one way to use the results of searches performed with bfsearch and dfsearch to highlight the nodes and edges in the graph according to the table of events, T. The function pauses before each step in the algorithm, so you can slowly step through the search by pressing any key.

Save visualize_search.m in the current folder.

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

Use this command to run visualize_search.m on graph G and search result T:

  visualize_search(G,T)

The graph begins as all gray, and then a new piece of the search result appears each time you press a key. The search results are highlighted according to:

'startnode' - Starting nodes increase in size.
'discovernode' - Nodes turn red as they are discovered.
'finishnode' - Nodes turn black after they are finished.
'edgetonew' - Edges that lead to undiscovered nodes turn blue.
'edgetodiscovered' - Edges that lead to discovered nodes turn magenta.
'edgetofinished' - Edges that lead to finished nodes turn green.

This .gif animation shows what you see when you step through the results of visualize_search.m.

Visualize Breadth-First and Depth-First Search

See Also

Related Topics