目前写了个有向图深度优先递归算法,求出所有环路。
作为一个实际需求的前奏。
循环的单位叫做Serv
服务与服务关系,模拟数据库里面存放的二元关系,用ServRel类代替。
public class GraphFindCycle { public List servList; public void setServList(List servList){ this.servList = servList; } class ServRel{ public String useServId; public String providerServId; public double amount; } class Serv{ public String servId; public List refServ = new ArrayList(); } public List findRefServ(String servId,List servRelList){ List refServList = new ArrayList(); for(int i=0;i<servRelList.size();i++){ ServRel rel = (ServRel)servRelList.get(i); if(servId.equals(rel.useServId)){ refServList.add(rel.providerServId); } } return refServList; } class CycleServ{ public List cycleServList; } public void findCycleServ(String servId,String cyclePath,List servRelList){ String id = servId; List refServList = findRefServ(servId,servRelList); if(!(refServList.size()>0)){ return; } else if(cyclePath.indexOf(servId)>0){ System.out.println(cyclePath+","+id); return; } else{ cyclePath = cyclePath+","+id; for(int j=0;j<refServList.size();j++){ String childServId = (String)refServList.get(j); findCycleServ(childServId,cyclePath,servRelList); } } } public static void main(String[] args) { GraphFindCycle gfc = new GraphFindCycle(); List servList = new ArrayList(); servList.add("A"); servList.add("B"); servList.add("C"); servList.add("D"); servList.add("E"); servList.add("F"); List servRelList = new ArrayList(); ServRel sr = gfc.new ServRel(); sr.useServId = "A"; sr.providerServId = "B"; servRelList.add(sr); ServRel sr1 = gfc.new ServRel(); sr1.useServId = "B"; sr1.providerServId = "A"; servRelList.add(sr1); ServRel sr2 = gfc.new ServRel(); sr2.useServId = "A"; sr2.providerServId = "C"; servRelList.add(sr2); ServRel sr3 = gfc.new ServRel(); sr3.useServId = "B"; sr3.providerServId = "D"; servRelList.add(sr3); ServRel sr4 = gfc.new ServRel(); sr4.useServId = "E"; sr4.providerServId = "A"; servRelList.add(sr4); ServRel sr5 = gfc.new ServRel(); sr5.useServId = "F"; sr5.providerServId = "B"; servRelList.add(sr5); //System.out.println(servRelList.size()); for(int i=0;i<servList.size();i++){ String servId = (String)servList.get(i); gfc.findCycleServ(servId,"",servRelList); } } }
相关推荐
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
基于深度卷积-递归神经网络的手绘草图识别方法.pdf
应用cfree软件,采用递归方法,基于有向图的邻接矩阵,进行深度优先搜索遍历(包括连通性)。
c++-深度优先遍历的递归实现版本
java培训知识-递归,详细描述了,递归算法。
java语法 method 递归 马克-to-win java视频 方法 重载
数据结构DFS深度优先遍历非递归算法实现,是自己编写的,可靠。
NOIP普及讲座1-递归与分治(C++版).pdf
遍历递归的先中後序, 非递归的先中後序, 计算出深度 结点数 /* 运行结果: ------------------------ 请先序输入二叉树(如:ab三个空格表示a为根节点,b为左子树的二叉树) ab c 先序递归遍历二叉树: a b c 先序...
大师叫你不再害怕 ----递归 大师叫你不再害怕 ----递归 大师叫你不再害怕 ----递归
编译原理-递归子程序 c++源码 编译原理-递归子程序 c++源码 编译原理-递归子程序 c++源码
数据结构课时,c++写的深度优先搜索和广度优先搜索非递归算法,
哈夫曼编码实现_c语言 (最小堆) 求WPL -----递归求解
java-树状结构展示-递归查询,只查询一次数据库,提高性能,减少响应时间
20221011-1-递归与循环.py
编译原理课程设计---递归下降分析程序的实现
深度优先遍历的实现; 广度优先遍历的实现;
javascript通过递归和栈实现树深度优先遍历和广度优先遍历
使用邻接表表示法创建无向图,然后使用非递归算法进行深度优先遍历和广度优先遍历
用C++写的图的非递归深度优先搜索.一个小程序