%深度搜索算法
clc
% 初始化
G=[0 1 1 0 0;
1 0 1 0 0;
1 1 0 1 1;
0 0 1 0 1;
0 0 1 1 0;];
n=size(G,1)%顶点的数目为n
W=G
v=1%顶点1
k=zeros(1,n)%k（v）为0表示没有顶点k（v）没有被标记过
f=zeros(1,n)%相应顶点的父亲顶点
b=sum(sum((W==1)))%临接矩阵G中1的个数
c=sum(k==0)%矩阵K中0的个数即未被标记的顶点的个数
d=1%d用来判断是否搜寻完毕
if (b==0)&&(c==0)&&(v==1)%b为0表示每个支路都搜索过了，c为0表示每个顶点都标记过了，v为1表示回到初始节点
d=0
end
k(1)=1%标记顶点1
j=2%第二个顶点的标号
l=2%第1条树枝
while d==1%d用来判断是否搜寻完毕，为1时继续搜寻
%步骤3
a=find(W(v,:)==1)%v行的1位第a列，v为1时，a=2；v为2时，v为3 4
%步骤5
if isempty(a)%a为全0时，isempty(a)为1
W(v,f(v))=l
l=l+1
v=f(v)
else %a中含有1
%步骤4
mm=length(a)
for i=1:length(a)%a的长度
nn=a(i)
if k(a(i))==0%k(a(i))节点之前没有标记过
k(a(i))=j%顶点的标号
j=j+1%下一个顶点的标号加1
W(v,a(i))=l
l=l+1%树枝数加1
f(a(i))=v%f表示相应节点的父亲节点
v=a(i)%节点变为a(i)
break%转步骤3
else if k(a(i))~=0%k(a(i))节点之前已经标记过
W(v,a(i))=l%树枝(v,a(i))已经标志过
l=l+1%树枝数加1
end
end
end
b=sum(sum((W==1)))%矩阵W中1的个数
c=sum(k==0) %矩阵K中0的个数,即标为0的顶点的个数
end
if b==0&&c==0&&v==1%
d=0
end
end
W
k
f
