BST和DST简单的matlab程序（图的广度和深度遍历）

图的广度和深度遍历，具体内容教材有

clc;
clear all;
close all;

%初始化邻接压缩表
compressTable=[1 2;1 3;1 4;2 4;2 5;3 6;4 6;4 7];
max_vertex = max(compressTable(:)); %压缩表中最大值就是邻接矩阵的宽与高
graph_matrix = compressTableToMatrix(compressTable);%从邻接压缩表构造图的矩阵表示
[x,y] = cylinder(1,max_vertex);
plot(x(1,:),y(1,:),’r*’,’markersize’,12)
hold on
for i = 1:max_vertex
tem = [‘V’,int2str(i)];
text(x(1,i) + 0.1,y(1,i),tem);
end
for i = 1:length(compressTable)
plot(x(1,compressTable(i,:)),y(1,compressTable(i,:)),’k-‘,’linewidth’,3);
end
%% BFS
% head = 1; %构造对头
% tail = 1; %构造队尾
% queue(head) = 1; %向头中加入图第一个节点
% head = head + 1; %队列扩展
%
% flag = 1; %标记访问过
% result_matrix = []; %结果矩阵
% while tail ~= head
% i = queue(tail);
% for j = 1 :max_vertex
% if graph_matrix(i,j) == 1 && isempty(find(flag == j,1))
% queue(head) = j;
% head = head + 1;
% flag = [flag,j];
% result_matrix = [result_matrix,i,j];
% end
% end
% tail = tail + 1;
% end
% graph_result_matrix = compressTableToMatrix(compressTable);
%
% [x,y] = cylinder(1,max_vertex);
% plot(x(1,:),y(1,:),’r*’,’markersize’,12)
% hold on
% for i = 1:max_vertex
% tem = [‘V’,int2str(i)];
% text(x(1,i) + 0.1,y(1,i),tem);
% end
% for i = 1:length(compressTable)
% plot(x(1,compressTable(i,:)),y(1,compressTable(i,:)),’m.-‘,’linewidth’,1);
% end
%% DFS
top = 1;
stack (top) = 1;

flag = 1; %标记访问过
result_matrix = []; %结果矩阵
while top ~= 0
pre_len = length(stack);
i = stack(top);
for j = 1:max_vertex
if graph_matrix(i,j) ~= 0 && isempty(find(flag == j,1))
top = top +1;
stack(top) = j;
flag = [flag,j];
result_matrix =[result_matrix,i,j];
end
end
if length(stack) == pre_len
stack(top) = [];
top = top – 1;
end
end

graph_result_matrix = compressTableToMatrix(compressTable);

[x,y] = cylinder(1,max_vertex);
plot(x(1,:),y(1,:),’r*’,’markersize’,12)
hold on
for i = 1:max_vertex
tem = [‘V’,int2str(i)];
text(x(1,i) + 0.1,y(1,i),tem);
end
for i = 1:length(compressTable)
plot(x(1,compressTable(i,:)),y(1,compressTable(i,:)),’m.-‘,’linewidth’,1);
end

function graph_matrix = compressTableToMatrix(compressTable)

max_vertex = max(compressTable(:));
graph_matrix = ones(max_vertex);

for i = 1 : max_vertex
graph_matrix(compressTable(i,1),compressTable(i,2)) = 1;
graph_matrix(compressTable(i,2),compressTable(i,1)) = 1;
end

end