回路搜寻.doc

肀functionval=FindCircle(c,x)聿%==========================================================================芆%相关概念:芃%1、有向图G=(V,E)中,若边序列P=(e(i1),e(i2),e(i3),……,e(iq)),其中eik=螃%(v(l),v(j))满足v(l)是e(ik-1)的终点、v(j)是e(ik+1)的起点,就称P是G的一条有向道衿%路。若e(iq)的终点也是e(i1)的起点,则称P是G的一条有向回路。若P中的边没有重复出莇%现,则称P是简单有向道路或简单有向回路;进而,若P中的结点也不重复出现,则称P是初蒂%级有向道路或初级有向回路。节%2、无向图G=(V,E)中,若点边交替序列P=(v(i1),e(i1),v(i2),e(i2),……,蕿%e(iq-1),v(iq)),满足v(ik)、v(ik+1)是e(ik)的两个端点,则称P是G的一条链或道路。膅%若v(iq)=v(i1)的起点,则称P是G的一个圈或回路。若P中的边没有重复出现,则称P是简螄%单道路或简单回路;进而,若P中的结点也不重复出现,则称P是初级道路或初级回路。蚂%==========================================================================莀%实际意义:膆%寻找图中的回路。袂%==========================================================================肁%算法及步骤:肀%基于权矩阵求图中的回路。芇%无向图中回路的判定:不断删除度为1的结点,若最后图中仍有结点,则存在回路,芅%否则不存在回路。蒀%有向图中回路的判定:不断删除入度为0的结点,若最后图中仍有结点,则存在回路,袁%否则不存在回路。肅%==========================================================================莃%函数的使用:羀%输入:芇%(1)权矩阵C;膆%(2)是否是有向图:x==1表示是有向图;x==0表示是无向图。蒂%输出:荿%图中是否存在回路:存在回路返回1,否则返回0。肇%==========================================================================***袄c1=c;肃n=max(size(c));螈f=1;羅bin=zeros(1,n);%储存已删结点,bin(i)==1表示结点i已被删除羂蒂ifx==0%如果是无向图薈whilef==1肆f=0;莅fori=1:n袁ifsum(c1(i,:)~=zeros(1,n))==1%结点i的度为1芈c1(i,:)=zeros(1,n);肈c1(:,i)=zeros(n,1);蒃f=1;莁end;聿end;袅end;袅ifsum(sum(c1))==0%已没有结点螀val=0;蝿else羆val=1;羄end;腿else%如果是有向图葿whilef==1羈f=0;肂in_degree=sum(c1~=zeros(n,