主要内容

可视化广度优先和深度优先搜索

打开脚本

的结果可视化的函数bfsearch而且dfsearch通过突出显示图的节点和边。

创建并绘制有向图。

S = [1 2 3 3 3 3 4 5 6 7 8 9 9 9 9 10];T = [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2];G =有向图(s,t);情节(G)

在图上执行深度优先搜索。指定“allevents”返回算法中的所有事件。同时,指定重新启动作为真正的以确保搜索访问图中的每个节点。

T = dfsearch(G, 1，“allevents”，“重启”,真正的)
T = 38 x4 EdgeIndex表事件节点优势  ________________ ____ __________ _________ startnode南南南discovernode 1南南南edgetonew南1 7 discovernode 7南南南edgetonew南7 3 10 discovernode 3南南南edgetodiscovered南3 1 3 edgetonew南3 5 4 discovernode 5南南南edgetonew南5 4 8 discovernode 4南南南edgetonew南4 2 7 discovernode 2南南南edgetonew南2 6 2 discovernode 6南南南edgetodiscovered南6 4 9 finishnode 6南南南finishnode 2南南南南南南finishnode finishnode 4 5南南南edgetofinished南3 6 5 edgetonew南3 8 6 discovernode 8南南南edgetodiscovered南8 7 11 finishnode 8 3南南南南南南finishnode finishnode 7南南南finishnode 1南南南startnode 9南南南discovernode 9南南南edgetofinished南9 1 12 edgetofinished南9 14 finishnode 6 13 edgetofinished南9 8 9 10南南南南南南startnode discovernode 10南南南edgetofinished NaN10 2 15 finishnode 10 NaN NaN NaN

表中的值，T，对于可视化搜索很有用。这个函数visualize_search.m显示使用的搜索结果的一种方法bfsearch而且dfsearch若要根据事件表突出显示图中的节点和边，T．该函数在算法的每个步骤之前暂停，因此您可以通过按任意键缓慢地执行搜索。

保存visualize_search.m在当前文件夹中。

函数visualize_search (G, t)% G是一个图或有向图对象，t是调用% BFSEARCH或DFSEARCH。％输入示例: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);The MathWorks, Inc.版权所有isundirected = isa(G，“图”）;如果isundirected将图替换为对应的有向图，因为我们需要分离%两个方向的边[src, tgt] = findge (G);G =有向图([src;tgt]、[tgt;src]， [1:numedges(G)， 1:numedges(G)]);结束h = plot(G，“NodeColor”，[0.5 0.5 0.5]，“EdgeColor”，[0.5 0.5 0.5]，.．.“EdgeLabelMode”，“汽车”）;为2 = 1:尺寸(t) 1)开关t.Event (2)情况下“startnode”突出(h, t.Node (ii),“MarkerSize”分钟(h.MarkerSize) * 2);情况下“discovernode”突出(h, t.Node (ii),“NodeColor”，“r”）;情况下“finishnode”突出(h, t.Node (ii),“NodeColor”，“k”）;否则如果isundirected a = G.Edges.Weight;b = t.EdgeIndex(ii);相交(find(a == b)，.．.findedge (G, t.Edge (ii, 1), t.Edge (2, 2)));其他的edgeind = t.EdgeIndex(ii);结束开关t.Event (2)情况下“edgetonew”突出(h,“边缘”edgeind,“EdgeColor”，“b”）;情况下“edgetodiscovered”突出(h,“边缘”edgeind,“EdgeColor”，[0.8 0 0.8]);情况下“edgetofinished”突出(h,“边缘”edgeind,“EdgeColor”，[0 0.8 0]);结束结束nodeStr = t.Node;如果isnumeric(nodeStr) nodeStr = num2cell(nodeStr);nodeStr = cellfun(@num2str, nodeStr，“UniformOutput”、假);结束edgeStr = t.Edge;如果isnumeric(edgeStr) edgeStr = num2cell(edgeStr);edgeStr = cellfun(@num2str, edgeStr，“UniformOutput”、假);结束如果~isnan(t. node (ii)) title([char(t{ii, 1}))' on Node 'nodeStr {2}]);其他的标题([char (t {ii, 1})' on Edge ('edgeStr {ii, 1}”、“.．.edgeStr {ii, 2},')边缘索引'sprintf (' % d '， t{ii, 4})]);结束disp (“按任意键继续……”)暂停结束disp (“完成”。)关闭所有

使用该命令运行visualize_search.m在图G和搜索结果T：

visualize_search (G, T)

图表开始时全为灰色，然后每次按下一个键，就会出现搜索结果的新部分。搜索结果按以下方式高亮显示:

  • “startnode”—启动节点增加大小。

  • “discovernode”-节点转红色的当他们被发现时。

  • “finishnode”-节点转黑色的在他们完成之后。

  • “edgetonew”-导致未发现节点的边会转动蓝色的．

  • “edgetodiscovered”-导致发现节点的边转动品红色的．

  • “edgetofinished”-导致完成节点转动的边绿色．

这gif的结果时，动画显示您所看到的内容visualize_search.m．

另请参阅

|||

相关的话题