1 / 6
文档名称:

回路搜寻.doc

格式:doc   大小:30KB   页数:6页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

回路搜寻.doc

上传人:坐水行舟 2019/4/21 文件大小:30 KB

下载得到文件列表

回路搜寻.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,n));芇fori=1:n薃ifin_degree(i)==0&