1 / 5
文档名称:

回路搜寻.doc

格式:doc   大小:27KB   页数:5页
下载后只包含 1 个 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);%储存已删结点

分享好友

预览全文

回路搜寻.doc

上传人:花开一叶 2019/5/27 文件大小:27 KB

下载得到文件列表

回路搜寻.doc