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
最新文章
- idea IntelliJ IDEA 2016.2破解
- Action的动态调用方法
- JavaScript基础知识之——Location 对象详解
- Linux 基础入门(新版)(实验一至实验四)
- eclipse juno版本中没用 ant
- 爬虫学习之基于Scrapy的网络爬虫
- Delphi给窗体镶边-为控件加边框,描边,改变边框颜色
- 动态规划——J 括号配对问题
- Fitnesse用系列三
- 学习ASP.NET MVC(十)——排序
- Linux中的DRM
- net.at.json.JSONException
- Android官方技术文档翻译——Gradle 插件用户指南(6)
- linux下导入、导出mysql数据库命令的实现方法
- Python爬虫之提取Bing搜索的背景图片并设置为Windows的电脑桌面
- class面向对象-1
- 百度Hr分享,一个合格的数据工程师简历中必备技能?
- golang 引用相对路径package
- 索引与like优化
- yum 出现error: db5 error