MATLAB Examples

Visualize Breadth-First and Depth-First Search

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 =

  38x3 table

         Event          Node       Edge   
    ________________    ____    __________

    startnode             1     NaN    NaN
    discovernode          1     NaN    NaN
    edgetonew           NaN       1      7
    discovernode          7     NaN    NaN
    edgetonew           NaN       7      3
    discovernode          3     NaN    NaN
    edgetodiscovered    NaN       3      1
    edgetonew           NaN       3      5
    discovernode          5     NaN    NaN
    edgetonew           NaN       5      4
    discovernode          4     NaN    NaN
    edgetonew           NaN       4      2
    discovernode          2     NaN    NaN
    edgetonew           NaN       2      6
    discovernode          6     NaN    NaN
    edgetodiscovered    NaN       6      4
    finishnode            6     NaN    NaN
    finishnode            2     NaN    NaN
    finishnode            4     NaN    NaN
    finishnode            5     NaN    NaN
    edgetofinished      NaN       3      6
    edgetonew           NaN       3      8
    discovernode          8     NaN    NaN
    edgetodiscovered    NaN       8      7
    finishnode            8     NaN    NaN
    finishnode            3     NaN    NaN
    finishnode            7     NaN    NaN
    finishnode            1     NaN    NaN
    startnode             9     NaN    NaN
    discovernode          9     NaN    NaN
    edgetofinished      NaN       9      1
    edgetofinished      NaN       9      6
    edgetofinished      NaN       9      8
    finishnode            9     NaN    NaN
    startnode            10     NaN    NaN
    discovernode         10     NaN    NaN
    edgetofinished      NaN      10      2
    finishnode           10     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-2015 The MathWorks, Inc.

if isa(G,'graph')
    % Replace graph with corresponding digraph, because we need separate
    % edges for both directions
    G = digraph(adjacency(G));
end

h = plot(G,'NodeColor',[0.5 0.5 0.5],'EdgeColor',[0.5 0.5 0.5]);

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');
        case 'edgetonew'
            highlight(h,t.Edge(ii,1),t.Edge(ii,2),'EdgeColor','b');
        case 'edgetodiscovered'
            highlight(h,t.Edge(ii,1),t.Edge(ii,2),'EdgeColor',[0.8 0 0.8]);
        case 'edgetofinished'
            highlight(h,t.Edge(ii,1),t.Edge(ii,2),'EdgeColor',[0 0.8 0]);
    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.