Java编程实现深度优先遍历与连通分量代码示例

深度优先遍历

深度优先遍历类似于一个人走迷宫：

如图所示，从起点开始选择一条边走到下一个顶点，没到一个顶点便标记此顶点已到达。

当来到一个标记过的顶点时回退到上一个顶点，再选择一条没有到达过的顶点。

当回退到的路口已没有可走的通道时继续回退。

而连通分量，看概念：无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

下面看看具体实例：

package com.dataStructure.graph;
// 求无权图的联通分量
public class Components {
	private Graph graph;
	// 存放输入的数组
	private Boolean[] visited;
	// 存放节点被访问状态
	private int componentCount;
	// 连通分量的数量
	private int[] mark;
	// 存储节点所属联通分量的标记
	// 构造函数，初始化私有属性
	public Components(Graph graph) {
		this.graph = graph;
		componentCount = 0;
		// 连通分量初始数量为 0
		visited = new Boolean[graph.V()];
		mark = new int[graph.V()];
		for (int i = 0; i < graph.V(); i++) {
			visited[i] = false;
			// 节点初始访问状态为 false
			mark[i] = -1;
			// 节点初始连通分量标记为 -1
		}
		for (int i = 0; i < graph.V(); i++) {
			// 对于未被访问的节点进行 dfs深度优先遍历
			if (!visited[i]) {
				dfs(i);
				componentCount++;
				// 对一个节点进行dfs 到底后，一个连通分量结束，数量+1
			}
		}
	}
	private void dfs(int i) {
		visited[i] = true;
		// 节点 i 已被访问
		mark[i] = componentCount;
		// 节点 i 属于当前连通分量的数量（标记）
		for (int node : graph.adjacentNode(i)) {
			// 遍历图中节点 i 的邻接节点
			if (!visited[node]) // 对未被访问的邻接节点进行 dfs
			dfs(node);
		}
	}
	public Boolean isConnected(int v, int w) {
		return mark[v] == mark[w];
		// 根据两节点所属连通分量的标记判断两节点是否相连
	}
	public int getComponentCount() {
		return componentCount;
		// 返回 graph 中连通分量的数量
	}
}
//public class Components {
//
//  private Graph G;          // 图的引用
//  private boolean[] visited; // 记录dfs的过程中节点是否被访问
//  private int ccount;     // 记录联通分量个数
//  private int[] id;      // 每个节点所对应的联通分量标记
//
//  // 图的深度优先遍历
//  private void dfs(int v) {
//
//    visited[v] = true; // 节点 v 的访问状态置为 true
//    id[v] = ccount; // 节点 v 对应的联通标记设置为 ccount
//
//    // 遍历节点 v 的邻接点 i
//    for (int i : G.adjacentNode(v)) {
//      // 如果邻接点 i 尚未被访问
//      if (!visited[i])
//        // 对邻接点 i 进行深度优先遍历
//        dfs(i);
//    }
//  }
//
//  // 构造函数, 求出无权图的联通分量
//  public Components(Graph graph) {
//
//    // 算法初始化
//    G = graph;
//
//    // visited 数组存储 图G 中 节点的被访问状态
//    visited = new boolean[G.V()];
//
//    // id 数组存储 图G 中 节点所属连通分量的标记
//    id = new int[G.V()];
//
//    // 连通分量数量初始化为 0
//    ccount = 0;
//
//    // 将 visited 数组全部置为 false； id 数组全部置为 -1
//    for (int i = 0; i < G.V(); i++) {
//      visited[i] = false;
//      id[i] = -1;
//    }
//
//    // 求图的联通分量
//    for (int i = 0; i < G.V(); i++)
//      // 访问一个未曾被访问的节点
//      if (!visited[i]) {
//        // 对其进行深度优先遍历
//        dfs(i);
//        ccount++;
//      }
//  }
//
//  // 返回图的联通分量个数
//  int count() {
//    return ccount;
//  }
//
//  // 查询点v和点w是否联通（节点v 和 w 的联通分量的标记是否相同
//  boolean isConnected(int v, int w) {
//    assert v >= 0 && v < G.V();
//    assert w >= 0 && w < G.V();
//    return id[v] == id[w];
//  }
//}

通分量数量为 3

总结

以上就是本文关于Java编程实现深度优先遍历与连通分量代码示例的全部内容，希望对大家有所帮助。如有不足之处，欢迎留言指出。关注我们，您会有更多收获。

赞 (0)

相关推荐

  • Java的后台文件夹下文件的遍历完整代码

    Java的后台文件夹下文件的遍历完整代码

    一.在java中遍历一个文件夹里边的所有文件,可以有两种方式: 1.递归遍历,通常也是开发者第一时间能想到的方法,递归遍历的优点是:实现起来相对简单,代码量相对较少,执行效率较高,缺点是:比较吃内存,对硬件要求较高 // 递归遍历 private void getDirectory(File file) { File flist[] = file.listFiles(); if (flist == null || flist.length == 0) { return 0; } for (Fil

  • java 遍历Map及Map转化为二维数组的实例

    java 遍历Map及Map转化为二维数组的实例 实例代码: import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class Test { public static void main(String[] args) { int a = 0, b = 0, c = 0; // 第一种:通过Map.keySet()遍历Map及将Map转化为二维数组 Map<String, String>

  • Java完全二叉树的创建与四种遍历方法分析

    Java完全二叉树的创建与四种遍历方法分析

    本文实例讲述了Java完全二叉树的创建与四种遍历方法.分享给大家供大家参考,具体如下: 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素

  • Java开发之HashMap的使用和遍历

    Java开发之HashMap的使用和遍历 1:使用HashMap的一个简单例子 package com.pb.collection; import java.util.HashMap; import java.util.Iterator; import java.util.Set; import java.util.Map.Entry; public class HashMapDemo { public static void main(String[] args) { HashMap<Stri

  • java实现遍历树形菜单两种实现代码分享

    文本主要向大家分享了java实现遍历树形菜单的实例代码,具体如下. OpenSessionView实现: package org.web; import java.io.IOException; import javax.servlet.Filter; import javax.servlet.FilterChain; import javax.servlet.FilterConfig; import javax.servlet.ServletException; import javax.se

  • Java中map遍历方式的选择问题详解

    1. 阐述 对于Java中Map的遍历方式,很多文章都推荐使用entrySet,认为其比keySet的效率高很多.理由是:entrySet方法一次拿到所有key和value的集合:而keySet拿到的只是key的集合,针对每个key,都要去Map中额外查找一次value,从而降低了总体效率.那么实际情况如何呢? 为了解遍历性能的真实差距,包括在遍历key+value.遍历key.遍历value等不同场景下的差异,我试着进行了一些对比测试. 2. 对比测试 一开始只进行了简单的测试,但结果却表明k

  • java 中遍历取值异常（Hashtable Enumerator）解决办法

    java 中遍历取值异常(Hashtable Enumerator)解决办法 用迭代器取值时抛出的异常:java.util.NoSuchElementException: Hashtable Enumerator 示例代码 //使用迭代器遍历 Iterator<String> it = tableProper.stringPropertyNames().iterator(); sqlMap = new HashMap<String,String>(); while(it.hasNe

  • java 使用foreach遍历集合元素的实例

    java 使用foreach遍历集合元素的实例 1 代码示例 import java.util.*; public class ForeachTest { public static void main(String[] args) { // 创建集合.添加元素的代码与前一个程序相同 Collection books = new HashSet(); books.add(new String("book1")); books.add(new String("book2&quo

  • Java编程实现深度优先遍历与连通分量代码示例

    Java编程实现深度优先遍历与连通分量代码示例

    深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达. 当来到一个标记过的顶点时回退到上一个顶点,再选择一条没有到达过的顶点. 当回退到的路口已没有可走的通道时继续回退. 而连通分量,看概念:无向图G的极大连通子图称为G的连通分量( Connected Component).任何连通图的连通分量只有一个,即是其自身,非连通的无向图有多个连通分量. 下面看看具体实例: package com.dataStructure.gra

  • Java编程利用socket多线程访问服务器文件代码示例

    这篇文章将向大家展示Java编程利用socket多线程访问服务器文件代码示例,如果您想先了解Java多线程socket编程的基础知识,可以看下这篇文章:Java多线程编程实现socket通信示例代码. 接下来进入正文,我们看看利用socket多线程访问服务器代码: ServerMain.java package com.ysk.webServer; import java.io.File; import java.io.IOException; import java.net.ServerSoc

  • Java编程实现五子棋人人对战代码示例

    Java编程实现五子棋人人对战代码示例

    利用Java,在控制台操作下,编写的五子棋,作为复习二维数组,面向对象等基础知识.w表示白棋,b表示黑棋 import java.util.Scanner; public class MainMethod { public static char[][] c = new char[10][10]; public static void main(String[] args) { MainMethod mainMethod = new MainMethod(); mainMethod.init()

  • Java编程将汉字转Unicode码代码示例

    上一次接触到编码的知识,还是上大学的时候,那时候学的是通信工程专业,有关编码的内容,不记得是在通信原理还是信息论与编码里面学到的了.却依然记得那个信息论与编码的老师,最喜欢吃的是尖椒肥肠盖饭,不知道是尖椒肥肠吃多了还是太聪明的缘故,三十多岁就开始拜顶了.那四年真是一段难忘的回忆... 话不多说,咱们进入正题.这里是一个简单的Java编程将汉字转Unicode码代码示例,下面是代码: package me.socketthread; public class ToUnicode { /** * @

  • Java编程GUI中的事件绑定代码示例

    程序绑定的概念: 绑定指的是一个方法的调用与方法所在的类(方法主体)关联起来.对java来说,绑定分为静态绑定和动态绑定:或者叫做前期绑定和后期绑定 静态绑定: 在程序执行前方法已经被绑定,此时由编译器或其它连接程序实现.例如:C. 针对java简单的可以理解为程序编译期的绑定:这里特别说明一点,java当中的方法只有final,static,private和构造方法是前期绑定 动态绑定 后期绑定:在运行时根据具体对象的类型进行绑定. 若一种语言实现了后期绑定,同时必须提供一些机制,可在运行期间

  • Java编程实现邻接矩阵表示稠密图代码示例

    Java编程实现邻接矩阵表示稠密图代码示例

    我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 邻接矩阵模型类 邻接矩阵模型类的类名为AMWGraph.java,能够通过该类构造一个邻接矩阵表示的图,且提供插入结点,插入边,取得某一结点的第一个邻接结点和下一个邻接结点. import java.u

  • Java编程IP地址和数字相互转换代码示例

    最近才知道,将ip地址转换成十进制.八进制.十六进制同样可以访问网站. IP转为数字(第二种算法.用左移.按位或实现.效率更高.): public long ipToLong(String ipAddress) { long result = 0; String[] ipAddressInArray = ipAddress.split("\\."); for (int i = 3; i >= 0; i--) { long ip = Long.parseLong(ipAddress

  • Java编程常见内存溢出异常与代码示例

    Java 堆是用来存储对象实例的, 因此如果我们不断地创建对象, 并且保证 GC Root 和创建的对象之间有可达路径以免对象被垃圾回收, 那么当创建的对象过多时, 会导致 heap 内存不足, 进而引发 OutOfMemoryError 异常. /** * @author xiongyongshun * VM Args: java -Xms10m -Xmx10m -XX:+HeapDumpOnOutOfMemoryError */ public class OutOfMemoryErrorTe

  • Java编程线程间通信与信号量代码示例

    1.信号量Semaphore 先说说Semaphore,Semaphore可以控制某个资源可被同时访问的个数,通过acquire()获取一个许可,如果没有就等待,而release()释放一个许可.一般用于控制并发线程数,及线程间互斥.另外重入锁ReentrantLock也可以实现该功能,但实现上要复杂些. 功能就类似厕所有5个坑,假如有10个人要上厕所,那么同时只能有多少个人去上厕所呢?同时只能有5个人能够占用,当5个人中的任何一个人让开后,其中等待的另外5个人中又有一个人可以占用了.另外等待的

  • java编程实现两个大数相加代码示例

    通常情况,实现大数运算是通过BigInteger和BigDecimal两种方法.这两种方法分别表示不可变的任意精度的整数和不可变的有符号的任意精度的十进制数(浮点数).主要用于高精度计算中.这两个类使得java中的大数,高精度运算变得很简单.但本文介绍的并不是通过上述两种方法实现Java中的大数运算. 主要的思想是:把两个数存在String中了,然后将每个数字取出,放到数组,由最末位开始计算,算加法,判断是否进位,进位则前位+1,若超过长度,则copy到新的数组. 代码如下: public cl

随机推荐