把 bfs 算法的matlab code 移植到北太天元上
/*
————————————————
版权声明：本文为CSDN博主「爱学习的一一一」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42105848/article/details/124551006
*/
/*
我把上面的代码移植到饿了北太天元软件上， 你可以把下面的代码copy
到一个文件，例如 bfsEx1.m ， 然后就可以在北太天元上执行这个脚本。
*/
clf; close all;clc
%初始化邻接压缩表
b=[1 2;1 3;1 4;2 4;
2 5;3 6;4 6;4 7];
m=max(b(:)); %压缩表中最大值就是邻接矩阵的宽与高
A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示
figure(1);
netplot(A,1) %形象表示
head=1; %队列头
tail=1; %队列尾，开始队列为空，tail==head
queue(head)=1; %向头中加入图第一个节点
head=head+1; %队列扩展
flag=1; %标记某个节点是否访问过了
re=[]; %最终结果
while tail~=head %判断队列是否为空
i=queue(tail); %取队尾节点
for j=1:m
if A(i,j)==1 && isempty(find(flag==j,1)) %如果节点相连并且没有访问过
queue(head)=j; %新节点入列
head=head+1; %扩展队列
flag=[flag j]; %对新节点进行标记
re=[re;i j]; %将边存入结果
end
end
tail=tail+1;
end
A=compresstable2matrix(re);
figure (2);
netplot(A,1)
function A=compresstable2matrix(b)
[n ~]=size(b);
m=max(b(:));
A=zeros(m,m);
for i=1:n
A(b(i,1),b(i,2))=1;
A(b(i,2),b(i,1))=1;
end
end
%函数名netplot
%使用方法输入请help netplot
%无返回值%函数只能处理无向图
%作者：tiandsp
%最后修改：2012.12.26
function netplot(A,flag)
%调用方法输入netplot(A,flag)，无返回值
%A为邻接矩阵或关联矩阵
%flag=1时处理邻接矩阵
%flag=2时处理关联矩阵
%函数只能处理无向图
if flag==1 %邻接矩阵表示无向图
ND_netplot(A);
return;
end
if flag==2 %关联矩阵表示无向图
[m n]=size(A); %关联矩阵变邻接矩阵
W=zeros(m,m);
for i=1:n
a=find(A(:,i)~=0);
W(a(1),a(2))=1;
W(a(2),a(1))=1;
end
ND_netplot(W);
return;
end
end
function ND_netplot(A)
[n n]=size(A);
w=floor(sqrt(n));
h=floor(n/w);
x=[];
y=[];
for i=1:h %使产生的随机点有其范围，使显示分布的更广
for j=1:w
x=[x 10*rand(1)+(j-1)*10];
y=[y 10*rand(1)+(i-1)*10];
end
end
ed=n-h*w;
for i=1:ed
x=[x 10*rand(1)+(i-1)*10];
y=[y 10*rand(1)+h*10];
end
plot(x,y,'r*');
title('网络拓扑图');
for i=1:n
for j=i:n
if A(i,j)~=0
c=num2str(A(i,j)); %将A中的权值转化为字符型
text((x(i)+x(j))/2,(y(i)+y(j))/2,c,'Fontsize',20); %显示边的权值
line([x(i) x(j)],[y(i) y(j)]); %连线
end
text(x(i),y(i),num2str(i),'Fontsize',24,'color','r'); %显示点的序号
hold on;
end
end
hold off;
end
