欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-12-15 15:54:16
深度优先遍历 深度优先遍历类似于一个人走迷宫: 如图所示,从起点开始选择一条边走到下一个顶点,没到一个顶点便标记此顶点已到达。 当来到一个标记过的顶点时回退到...

深度优先遍历

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

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];
//  }
//}

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

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

通分量数量为 3

总结

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

上一篇:

下一篇: