`
woxiaoe
  • 浏览: 283189 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

基于java的图(四) 强连通组件

    博客分类:
  • Java
阅读更多

有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量
最关键通用部分:强连通分量一定是图的深搜树的一个子树。




算法步骤:

    1)对图G进行深度搜索生成森林(树)

    2)生成图G的转置图G’ 
    3)用1)中生成的顶点到转置图中查找相关联的节点,返回的即为一个强连通分量

 

代码:

    

/**
	 * 返回图的强连通组件
	 * @param <T>
	 * @param graph
	 * @return
	 */
	public static<T> List<List<T>> getStrongComponents(Graph<T> graph){
		List<T> vList = visitGraph(graph);
		Collections.reverse(vList);
		Graph<T> graphT = transpose(graph);
		List<List<T>> components = new ArrayList<List<T>>();
		List<T> component = null;
		graphT.allUnVisted();
		for(T v : vList){
			if(graphT.getState(v) == VertexState.UNVISITED){
				component = new ArrayList<T>();
				dfsHandler(graphT, v, false, component);
				components.add(component);
			}
			
		}
		
		return components;
	}
	/**
	 * 得到图的转置图
	 * @param <T>
	 * @param graph
	 * @return
	 */
	private static<T> Graph<T> transpose(Graph<T> graph){
		Graph<T> graphT = new EGraph<T>();
		Set<T> vSet = graph.vertexSet();//得到顶点数
		Set<T> neighbors = null;
		for(T v : vSet){//加入顶点
			graphT.addVertex(v);
		}
		for(T v : vSet){//转向
			neighbors = graph.getNeighbors(v);
			for(T neighbor : neighbors){
				graphT.addEdge(neighbor, v, graph.getWeight(v, neighbor));
			}
		}
		return graphT;
	}

 

 

 

 

分享到:
评论

相关推荐

    基于Java的拼图游戏

    【基于Java的拼图游戏】是一款专为Java初学者设计的编程学习项目,它通过实现一个拼图游戏,帮助学习者深入理解Java编程语言的基本概念、面向对象编程思想以及图形用户界面(GUI)的设计与实现。这个项目不仅锻炼了...

    基于Java的迷宫程序(带界面)

    【基于Java的迷宫程序(带界面)】是一款利用Eclipse集成开发环境开发的互动式迷宫游戏。这款程序不仅提供了基本的迷宫生成和解决功能,还配备了一个直观的图形用户界面(GUI),使得用户体验更为友好。通过GUI,...

    基于 Java 的简单图形验证码识别.zip

    总之,基于Java的图形验证码识别是一个结合了图像处理、特征工程和机器学习的综合实践项目。通过这个项目,开发者不仅可以深化对Java编程的理解,还能掌握图像处理和模式识别的关键技术,为更复杂的计算机视觉应用...

    Java OCR 图像智能字符识别技术,可识别中文

    3. 文本区域检测:通过边缘检测和连通组件分析,找出可能包含文字的区域。 4. 字符分割:将文本区域进一步分割成单个字符。 5. 特征提取:提取每个字符的形状、纹理、结构等特征。 6. 分类识别:使用预先训练的...

    java源码-基于图像处理的车牌识别源码.zip

    在本项目中,我们主要探讨的是一个基于Java语言的图像处理技术,用于实现对国内车牌号码的自动识别系统。这个源码库提供了完整的程序代码,旨在帮助开发者理解并实现车牌识别的核心算法。以下是对该技术及其相关知识...

    基于java分水岭算法

    本项目是基于Java实现的分水岭算法,它利用了Java的强大功能来处理图像数据,从而进行精确的图像分割。 分水岭算法的概念源自地理学中的分水岭原理,即山脊线将河流流域分开。在图像处理中,这个概念被抽象化,用来...

    基于java的连连看游戏.doc

    《基于JAVA的连连看游戏》是一款使用JAVA编程语言开发的休闲益智游戏,它通过简单的游戏规则和丰富的视觉效果吸引了大量的玩家。以下是基于这个文档的关键知识点的详细解释: 1. **JAVA基础语法**:开发连连看游戏...

    javacv对图片进行文字提取,定位指定文字在图片的位置坐标,提高识别速度

    这可能涉及到连通组件分析,以便将相邻的字符分开。 4. 字符识别:最后,将分割出的字符输入到 OCR 引擎进行识别。OpenCV 本身并不包含 OCR 引擎,但 JavaCV 可以与 Tesseract OCR 集成,Tesseract 是 Google 维护...

    图文识别_java图文识别_java文字识别_

    这可以通过边缘检测、连通组件分析等算法来完成。Java的JavaCV或者Tess4J库提供了这些功能。 3. **文字识别**:一旦确定了文字区域,下一步就是识别具体字符。这通常依赖于预先训练好的模型,如深度学习模型,如RNN...

    Java源码 OCR 图像智能字符识别技术,大幅提升中文识别率,完善修正版

    后处理可能包括连通组件分析,以合并分割错误的字符。而用户接口则让非技术人员也能方便地使用这个OCR工具。 总之,这个Java OCR项目展示了如何利用现代计算机视觉技术和机器学习方法来高效准确地识别图像中的中文...

    基于Java的文字识别系统的研究.zip

    《基于Java的文字识别系统的研究》 文字识别技术是计算机视觉领域的一个重要分支,它涉及到图像处理、模式识别、机器学习等多个技术领域。本研究主要探讨如何利用Java编程语言构建一个高效、准确的文字识别系统。...

    java识别验证码 仅限字母数字 附带bmp图片

    本话题聚焦于使用Java来识别只包含字母和数字的BMP格式的验证码图片,其中验证码的位置会在图片上随机变动。这涉及到图像处理、模式识别以及机器学习等技术。 首先,我们要理解验证码识别的基本流程。它通常包括...

    SGIP.rar_ sgip1.2 java_sgip_sgip1.2_联通sgip1.2

    标题中的“SGIP.rar_ sgip1.2 java_sgip_sgip1.2_联通sgip1.2”指的是一个使用Java语言编写的、基于SGIP 1.2协议的程序,主要用于处理中国联通的SGIP 1.2通信协议。SGIP(Short Message Gateway Interface Protocol...

    基于Java的软件度量源码.zip

    - **复杂性度量**:Cyclomatic复杂度,表示程序控制流的复杂程度,计算公式为M = E - N + 2P,其中E是边数,N是节点数,P是连通组件数量。 - **耦合与内聚度量**:耦合度量模块之间的依赖关系,内聚度量一个模块...

    java车牌识别

    Java车牌识别程序是一种利用计算机视觉技术来...以上就是基于Java的车牌识别程序开发所涵盖的关键技术点。这个项目中的Java车牌识别程序很可能包含了上述部分或全部功能,通过这些技术实现对车辆车牌的高效准确识别。

    基于Java技术的泰语脱机手写模式识别研究.zip

    《基于Java技术的泰语脱机手写模式识别研究》是一项深入探讨计算机视觉与机器学习在泰语手写字符识别领域的应用。这篇文章着重讨论了如何利用Java编程语言来实现一个高效的脱机手写识别系统,旨在提高泰语文字处理的...

    SGIP1.2Java实现(包括服务端客户端)

    本项目提供了一个基于Java语言的完整实现,包括服务端和客户端两部分,方便开发者进行短消息业务的开发和对接。 首先,我们要理解SGIP1.2协议的基本概念和结构。SGIP1.2是SGIP(Short Message Gateway Interface ...

    基于openvc,车牌号识别以及图像处理springboot项目-java

    字符分割是将车牌上的单个字符分离出来,可能涉及连通组件分析;字符识别则通过OCR(光学字符识别)技术将字符转换成文本,这可能需要训练特定的模型,如SVM或深度学习网络。 3. **SpringBoot**:作为后端框架,...

Global site tag (gtag.js) - Google Analytics