回路搜寻.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。%=========================================================================