`
dacoolbaby
  • 浏览: 1267449 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

Java实现有向图找循环(深度优先-递归)

    博客分类:
  • Java
阅读更多

目前写了个有向图深度优先递归算法,求出所有环路。

作为一个实际需求的前奏。

 

循环的单位叫做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);
		}
	}

}

 

分享到:
评论

相关推荐

    深度优先搜索输出有向图中的所有环(JAVA)

    深度优先搜索(DFS, Depth-First Search)是一种用于遍历或搜索树或图的算法,尤其在处理有向图中的环问题时表现出色。在这个场景下,我们的目标是找到有向图中的所有环。Java是实现这个算法的一种常用编程语言。下面...

    图的遍历(有向图和无向图)

    本主题将详细介绍有向图和无向图的深度优先遍历(DFS)与宽度优先遍历(BFS),并探讨递归和非递归两种实现方式。 首先,我们来理解有向图和无向图的区别。有向图的边具有方向性,即从一个节点指向另一个节点,而无...

    java深度优先遍历

    - 拓扑排序:在有向无环图(DAG)中,DFS可以用于拓扑排序,确定节点的顺序。 5. **代码示例**: 在Java中,使用递归实现二叉树的DFS遍历(前序、中序、后序)如下: ```java class TreeNode { int val; ...

    216.214.JAVA基础教程_面向对象(上)-递归方法的使用(216).rar

    在Java的基础教程中,面向对象编程是核心概念之一,而递归方法的使用是编程中一个非常重要的技术,尤其对于理解复杂问题的解决有重要作用。本教程将深入探讨递归方法在Java中的应用。 递归是编程中一种自调用的方法...

    java实现强连通图

    强连通图是指有向图中任意两个顶点都相互可达的图。也就是说,如果存在一条从顶点A到顶点B的路径,同时也存在一条从顶点B回顶点A的路径,那么这两个顶点是强连通的。如果图中所有顶点都满足此条件,该图则被称为强...

    java数据结构与算法

    - 有向图中,如果从一个节点可以到达另一个节点,并且反过来也成立,则这两个节点属于同一个强连通分量。 - **最小生成树** - 从无向图中选取一个子图,该子图包含所有节点并且是最小权重的树。 - Kruskal算法和...

    数据结构JAVA

    - **有向图的强连通分量** - 有向图的强连通性定义 - 寻找强连通分量的方法 - **最小生成树** - 最小生成树的定义 - Prim 算法与 Kruskal 算法 **4.9 最短距离** - **单源最短路径** - Dijkstra 算法 - ...

    数据结构java版

    - 强连通分量是有向图中的极大强连通子图。 - **最小生成树** - 最小生成树是连接所有顶点的子图,其边的权重之和最小。 ##### 4.9 最短距离 - **单源最短路径** - Dijkstra算法用于计算图中一个顶点到其他所有...

    数据结构与算法java进阶(百度T5推荐)

    - 有向图的强连通分量:有向图中所有顶点都可达的子图。 - **4.9 最短距离** - 单源最短路径:计算从一个起点到图中其他所有顶点的最短路径。 - 任意顶点间的最短路径:计算图中任意两个顶点之间的最短路径。 -...

    java数据结构算法

    - 有向图中所有顶点两两之间都互为可达的极大子集。 - **4.8.3 最小生成树** - 从无向图中找出一个边的子集,它构成了图中所有的顶点,且总权重最小。 **4.9 最短距离** - **4.9.1 单源最短路径** - Dijkstra...

    数据结构预算

    - 有向图中的最大强连通子图。 - **最小生成树** - 一棵权重最小的生成树。 - 包括 Prim 算法和 Kruskal 算法。 **4.9 最短距离** - **单源最短路径** - 从一个源点到图中其他所有顶点的最短路径。 - ...

    java数据结构

    - **4.8.2 有向图的强连通分量** - 找到有向图中的强连通分量。 - **4.8.3 最小生成树** - 找到图中权重最小的生成树。 **4.9 最短距离** - **4.9.1 单源最短路径** - 从一个源点到所有其他顶点的最短路径。 - ...

    数据结构与算法(java版)

    图可以是有向的或无向的,加权的或无权重的。图的遍历方法包括深度优先搜索(DFS)和广度优先搜索(BFS)。Java中可以使用`java.util.ArrayList` 或 `java.util.LinkedList` 来表示邻接列表来存储图。 5. **排序**...

    JAVA_数据结构与算法(JAVA语言版)

    - 强连通分量是有向图中的最大子图,其中任意两个顶点都相互可达。 - **最小生成树** - 最小生成树是图中所有顶点构成的子图,其中边的权值之和最小。 - **最短距离** - **单源最短路径** - 寻找从指定起点到...

Global site tag (gtag.js) - Google Analytics