/*

————————————————

版權(quán)聲明：本文為CSDN博主「愛學(xué)習(xí)的一一一」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/weixin_42105848/article/details/124551006

*/

/*

我把上面的代碼移植到餓了北太天元軟件上， 你可以把下面的代碼copy

到一個(gè)文件，例如 bfsEx1.m ， 然后就可以在北太天元上執(zhí)行這個(gè)腳本。?

*/

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); ?%從鄰接壓縮表構(gòu)造圖的矩陣表示

figure(1);

netplot(A,1) ? ? ? ? ? ? ? ?%形象表示

head=1; ? ? ? ? ? ? %隊(duì)列頭

tail=1; ? ? ? ? ? ? %隊(duì)列尾，開始隊(duì)列為空，tail==head

queue(head)=1; ? ? ?%向頭中加入圖第一個(gè)節(jié)點(diǎn)

head=head+1; ? ? ? ?%隊(duì)列擴(kuò)展

flag=1; ? ? ? ? ? ? %標(biāo)記某個(gè)節(jié)點(diǎn)是否訪問過了

re=[]; ? ? ? ? ? ? ?%最終結(jié)果

while tail~=head ? ?%判斷隊(duì)列是否為空

? ? i=queue(tail); ?%取隊(duì)尾節(jié)點(diǎn)

? ? for j=1:m

? ? ? ? if A(i,j)==1 && isempty(find(flag==j,1)) ? ?%如果節(jié)點(diǎn)相連并且沒有訪問過

? ? ? ? ? ? queue(head)=j; ? ? ? ? ? ? ? ? ? ? ? ? ?%新節(jié)點(diǎn)入列

? ? ? ? ? ? head=head+1; ? ? ? ? ? ? ? ? ? ? ? ? ? ?%擴(kuò)展隊(duì)列

? ? ? ? ? ? flag=[flag j]; ? ? ? ? ? ? ? ? ? ? ? ? ?%對(duì)新節(jié)點(diǎn)進(jìn)行標(biāo)記

? ? ? ? ? ? re=[re;i j]; ? ? ? ? ? ? ? ? ? ? ? ? ? ?%將邊存入結(jié)果

? ? ? ? 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

%函數(shù)名netplot

%使用方法輸入請(qǐng)help netplot

%無返回值%函數(shù)只能處理無向圖

%作者：tiandsp

%最后修改：2012.12.26

function netplot(A,flag)

? ? %調(diào)用方法輸入netplot(A,flag)，無返回值

? ? %A為鄰接矩陣或關(guān)聯(lián)矩陣

? ? %flag=1時(shí)處理鄰接矩陣

? ? %flag=2時(shí)處理關(guān)聯(lián)矩陣

? ? %函數(shù)只能處理無向圖

? ? if flag==1 ? ? ?%鄰接矩陣表示無向圖

? ? ? ? ND_netplot(A);

? ? ? ? return;

? ? end

? ??

? ? if flag==2 ? ? ?%關(guān)聯(lián)矩陣表示無向圖

? ? ? ? [m n]=size(A); ? ? ?%關(guān)聯(lián)矩陣變鄰接矩陣

? ? ? ? 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 ? ? ? ? ? %使產(chǎn)生的隨機(jī)點(diǎn)有其范圍，使顯示分布的更廣

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('網(wǎng)絡(luò)拓?fù)鋱D');?

for i=1:n

for j=i:n

if A(i,j)~=0

c=num2str(A(i,j)); ? ? ? ? ? ? ? ? ? ? ?%將A中的權(quán)值轉(zhuǎn)化為字符型 ? ? ? ? ? ? ?

text((x(i)+x(j))/2,(y(i)+y(j))/2,c,'Fontsize',20); ?%顯示邊的權(quán)值

line([x(i) x(j)],[y(i) y(j)]); ? ? ?%連線

end

text(x(i),y(i),num2str(i),'Fontsize',24,'color','r'); ? %顯示點(diǎn)的序號(hào) ? ? ? ? ? ?

hold on;

end

end ?

hold off;

end