`
sunlujing
  • 浏览: 180347 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

图的基本算法（DFS，BFS, topoSort，SCC）

算法图基本算法DFS BFSSCCTopoSort 
阅读更多
由于要面试的缘故，在看算法导论的图算法一节，决定把基本的算法都用java代码实现出来。
1. 图的表示，使用链接表的形式。
class TreeNode{
	int nodeNum ; //节点编号
	TreeNode parent = null; //遍历时的父节点
	int dis = Integer.MAX_VALUE;// 距离源节点的路径
	int discoverTime =0; //在DFS遍历时发现的时间
	int finishTime =0;//DFS遍历时结束的时间
	Color color = Color.White;//初始时的颜色标记
	List<Integer> edges = new ArrayList<Integer>();//节点的边集合
	
	public TreeNode(int i) {
		nodeNum = i;
	}
	public int getNodeNum() {
		return nodeNum;
	}
	public void setNodeNum(int nodeNum) {
		this.nodeNum = nodeNum;
	}
	public TreeNode getParent() {
		return parent;
	}
	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	public int getDis() {
		return dis;
	}
	public void setDis(int dis) {
		this.dis = dis;
	}
	public int getDiscoverTime() {
		return discoverTime;
	}
	public void setDiscoverTime(int discoverTime) {
		this.discoverTime = discoverTime;
	}
	public int getFinishTime() {
		return finishTime;
	}
	public void setFinishTime(int finishTime) {
		this.finishTime = finishTime;
	}
}
 
2. 图的构建：
TreeNode[] heads = null;
final int NODENUM ;
public GraphicModelII(int nodeNum) {
   NODENUM = nodeNum;
   heads = new TreeNode[NODENUM+1];
   
   for(int i=1;i<=nodeNum;i++){
   heads[i] = new TreeNode(i);
   }
   }
public void addEdge(int src,int des){
   heads[src].edges.add(des);
   }
 
3. 广度优先搜索
    
public void BFS(int src){
   Queue<TreeNode> searchs = new LinkedList<TreeNode>();	    
   heads[src].color = Color.Gray;
   heads[src].dis= 0;
   searchs.add(heads[src]);
   while(!searchs.isEmpty()){
   TreeNode cur = searchs.poll();
   System.out.println("Node : "+cur.nodeNum);
   for(Integer des:cur.edges){
   TreeNode now  = heads[des];
   if(now.color == Color.White){
   now.color = Color.Gray;
   now.dis = cur.dis+1;
   now.parent = cur;
   searchs.add(now);
   }
   }
   cur.color = Color.Black;
   }
   
   }
 
 
4. 深度优先搜索
 public void DFS(){
   systemTime = 0;
   for(int i=1;i <=NODENUM;i++){
   TreeNode node = heads[i];
   if(node.color==Color.White){
   DFS_Visit(node);
   }
   }
   }
   public void DFS_Visit(TreeNode node){
   node.color = Color.Gray;
   systemTime++;
   node.discoverTime = systemTime; 
   for(Integer des:node.edges){
   TreeNode now = heads[des];
   if(now.color==Color.White){
   now.parent = node;
   DFS_Visit(now);
   }
   }
   node.color = Color.Black;
   systemTime++;
   node.finishTime = systemTime;
   topoSortUtil.push(node);
   System.out.println(node.nodeNum+"start:\t"+node.discoverTime+" end:\t"+node.finishTime);
   }
  
 
 
5. topo 排序：
topo 排序的算法
使用DFS来完成，对于每一个发现的节点，压入栈中
Stack<TreeNode> topoSortUtil = new Stack<TreeNode>();
对应DFS中 黄色标记代码
 public void topoSort(){
   topoSortUtil.clear();
   DFS();
   while(!topoSortUtil.isEmpty()){
   System.out.println(topoSortUtil.pop().nodeNum);
   }
   }
 
6. 求强连通分支SCC。
第一步 使用DFS算法，把每个节点遍历完成时写入到topoSortUtil 中，栈顶的元素是最后才遍历结束的节点。
第二步，求原图G的转置， 把原图中 u -v的边 变为 v-u.
见reverTopo 函数，遍历之后的图用heads_reverse 表示
第三步  使用DFS算法，求SCC。需要注意的是，在原始的DFS中
public void DFS(){
   systemTime = 0;
   for(int i=1;i <=NODENUM;i++){
 
   TreeNode node = heads[i];
   if(node.color==Color.White){
   DFS_Visit(node);
   }
   }
   }
for 循环 的节点顺序无要求，但是在求SCC时，需要使用topoSortUtil，最晚结束遍历的元素作为第二次遍历的第一个元素，并依此类推。
   
 public void SCC(){
  
   DFS();
   List<TreeNode> scc = new ArrayList<TreeNode>();
   reverTopo();
   while(!topoSortUtil.isEmpty()){
  TreeNode cur = heads_reverse[topoSortUtil.pop().nodeNum];
  if(cur.color==Color.White){
  DFS_Visit_Scc(cur,scc);
   }
  for(TreeNode node:scc){
  System.out.print(node.nodeNum);
  }
  System.out.println();
  scc.clear();
   }
   }
   
   public void DFS_Visit_Scc(TreeNode node,List<TreeNode> scc){
   node.color = Color.Gray;
   systemTime++;
   node.discoverTime = systemTime; 
   for(Integer des:node.edges){
   TreeNode now = heads_reverse[des];
   if(now.color==Color.White){
   now.parent = node;
   DFS_Visit_Scc(now,scc);
   }
   }
   node.color = Color.Black;
   systemTime++;
   node.finishTime = systemTime;
   scc.add(node);
   }
   
   private void reverTopo(){
   for(int i=1;i <=NODENUM;i++){
   TreeNode node = heads[i];
   int src = node.nodeNum;
   for(Integer des:node.edges){
   TreeNode reverNode = heads_reverse[des];
   reverNode.edges.add(src);
   }
   }
   }
 
完整代码
package graphic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class GraphicModelII {
	TreeNode[] heads = null;
	final int NODENUM ;
	static int  systemTime = 0;
	Stack<TreeNode> topoSortUtil = new Stack<TreeNode>();
	TreeNode[] heads_reverse = null;
	
	
	public GraphicModelII(int nodeNum) {
		   NODENUM = nodeNum;
		   heads = new TreeNode[NODENUM+1];
		   heads_reverse =new TreeNode[NODENUM+1];
		   
		   for(int i=1;i<=nodeNum;i++){
			   heads[i] = new TreeNode(i);
			   heads_reverse[i] = new TreeNode(i);
		   }
	   }
	   public void addEdge(int src,int des){
		   heads[src].edges.add(des);
	   }
	   
	   
	   public void BFS(int src){
		   Queue<TreeNode> searchs = new LinkedList<TreeNode>();
		   
		   heads[src].color = Color.Gray;
		   heads[src].dis= 0;
		   searchs.add(heads[src]);
		   while(!searchs.isEmpty()){
			   TreeNode cur = searchs.poll();
			   System.out.println("Node : "+cur.nodeNum);
			   for(Integer des:cur.edges){
				   TreeNode now  = heads[des];
				   if(now.color == Color.White){
					   now.color = Color.Gray;
					   now.dis = cur.dis+1;
					   now.parent = cur;
					   searchs.add(now);
				   }
			   }
			   cur.color = Color.Black;
		   }
		   
	   }
	   
	   public void DFS(){
		   systemTime = 0;
		   for(int i=1;i <=NODENUM;i++){
			
			   TreeNode node = heads[i];
			   if(node.color==Color.White){
				   DFS_Visit(node);
			   }
		   }
	   }
	   public void DFS_Visit(TreeNode node){
		   node.color = Color.Gray;
		   systemTime++;
		   node.discoverTime = systemTime; 
		   for(Integer des:node.edges){
			   TreeNode now = heads[des];
			   if(now.color==Color.White){
				   now.parent = node;
				   DFS_Visit(now);
			   }
		   }
		   node.color = Color.Black;
		   systemTime++;
		   node.finishTime = systemTime;
		   topoSortUtil.push(node);
		   System.out.println(node.nodeNum+"start:\t"+node.discoverTime+" end:\t"+node.finishTime);
	   }
	   
	   public void topoSort(){
		   topoSortUtil.clear();
		   DFS();
		   while(!topoSortUtil.isEmpty()){
			   System.out.println(topoSortUtil.pop().nodeNum);
		   }
	   }
	   
	   public void SCC(){
		  
		   DFS();
		   List<TreeNode> scc = new ArrayList<TreeNode>();
		   reverTopo();
		   while(!topoSortUtil.isEmpty()){
			  TreeNode cur = heads_reverse[topoSortUtil.pop().nodeNum];
			  if(cur.color==Color.White){
				  DFS_Visit_Scc(cur,scc);
			   }
			  for(TreeNode node:scc){
				  System.out.print(node.nodeNum);
			  }
			  System.out.println();
			  scc.clear();
		   }
	   }
	   
	   public void DFS_Visit_Scc(TreeNode node,List<TreeNode> scc){
		   node.color = Color.Gray;
		   systemTime++;
		   node.discoverTime = systemTime; 
		   for(Integer des:node.edges){
			   TreeNode now = heads_reverse[des];
			   if(now.color==Color.White){
				   now.parent = node;
				   DFS_Visit_Scc(now,scc);
			   }
		   }
		   node.color = Color.Black;
		   systemTime++;
		   node.finishTime = systemTime;
		   scc.add(node);
	   }
	   
	   private void reverTopo(){
		   for(int i=1;i <=NODENUM;i++){
			   TreeNode node = heads[i];
			   int src = node.nodeNum;
			   for(Integer des:node.edges){
				   TreeNode reverNode = heads_reverse[des];
				   reverNode.edges.add(src);
			   }
		   }
	   }
	   
	   public static void main(String[] args) {
//		   GraphicModelII graph = new GraphicModelII(5);
//		   graph.addEdge(1, 2);
//		   graph.addEdge(1, 5);
//		   graph.addEdge(2, 1);
//		   graph.addEdge(2, 5);
//		   graph.addEdge(2, 4);
//		   graph.addEdge(2, 3);
//		   graph.addEdge(3, 2);
//		   graph.addEdge(3, 4);
//		   graph.addEdge(4, 2);
//		   graph.addEdge(4, 5);
//		   graph.addEdge(5, 4);
//		   graph.addEdge(5, 2);
//		   graph.addEdge(5, 1);
		  // graph.BFS(1);
		   //graph.DFS();
//		   GraphicModelII graph = new GraphicModelII(9);
//		   graph.addEdge(1, 2);
//		   graph.addEdge(1, 8);
//		   graph.addEdge(2, 3);
//		   graph.addEdge(2, 8);
//		   graph.addEdge(3, 6);
//		   graph.addEdge(4, 3);
//		   graph.addEdge(4, 5);
//		   graph.addEdge(5, 6);
//		   graph.addEdge(7, 8);
//		   graph.topoSort();
		   
		   //test scc
		   GraphicModelII graph = new GraphicModelII(8);
		   graph.addEdge(1, 2);
		   graph.addEdge(2, 3);
		   graph.addEdge(3, 4);
		   graph.addEdge(4, 3);
		   graph.addEdge(2, 5);
		   graph.addEdge(2, 6);
		   graph.addEdge(3, 7);
		   graph.addEdge(4, 8);
		   graph.addEdge(5, 1);
		   graph.addEdge(5, 6);
		   graph.addEdge(6, 7);
		   graph.addEdge(7, 6);
		   graph.addEdge(7,8);
		   graph.addEdge(8,8);
		   //graph.topoSort();
		   graph.SCC();
	   }
}
class TreeNode{
	int nodeNum ;
	TreeNode parent = null;
	int dis = Integer.MAX_VALUE;
	int discoverTime =0;
	int finishTime =0;
	Color color = Color.White;
	List<Integer> edges = new ArrayList<Integer>();
	
	public TreeNode(int i) {
		nodeNum = i;
	}
	public int getNodeNum() {
		return nodeNum;
	}
	public void setNodeNum(int nodeNum) {
		this.nodeNum = nodeNum;
	}
	public TreeNode getParent() {
		return parent;
	}
	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	public int getDis() {
		return dis;
	}
	public void setDis(int dis) {
		this.dis = dis;
	}
	public int getDiscoverTime() {
		return discoverTime;
	}
	public void setDiscoverTime(int discoverTime) {
		this.discoverTime = discoverTime;
	}
	public int getFinishTime() {
		return finishTime;
	}
	public void setFinishTime(int finishTime) {
		this.finishTime = finishTime;
	}
	
	
}
 
2
顶
2
踩
分享到：
| 我对非阻塞网络编程的理解
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    ALGraph DFS BFS DIJ toposort keyPath

    本文将深入探讨四个重要的图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、迪杰斯特拉算法（Dijkstra）以及拓扑排序（Topological Sort），并结合"ALGraphLastV"这个压缩包文件中的内容来解析这些概念。...

    DFS BFS 图.zip_DFS BFS_bfs_bfs dfs_dfs_dfs bfs输出图

    深度优先遍历（DFS, Depth First Search）和广度优先遍历（BFS, Breadth First Search）是图论中的两种基本搜索算法，用于遍历或查找图中的所有节点。这两种算法都起始于图中的一个特定节点，通常称为起点，然后按照...

    BFS和DFS算法可视化（js实现）

    **BFS（广度优先搜索）与DFS（深度优先搜索）是图论和树结构中常用的两种搜索算法，主要用于遍历或查找树或图。在本项目中，这两种算法通过JavaScript语言进行了可视化实现，旨在帮助学习者更好地理解和掌握这两种...

    定义采用邻接矩阵存储的图结构封装DFS、BFS算法

    定义采用邻接矩阵存储的图结构封装DFS、BFS算法

    基本图算法（bfs与dfs）1

    "基本图算法（bfs与dfs）" 图算法是计算机科学中最重要的领域之一，许多问题可以被建模为图问题。图算法是解决这些问题的基础。 在图算法中，图是一种重要的数据结构，通常用来表示实世界中的关系。图可以被定义为...

    算法之BFS与DFS

    在计算机科学中，图论和算法是至关重要的部分，而BFS（广度优先搜索）和DFS（深度优先搜索）是两种最基础且广泛使用的图遍历算法。它们在解决各种问题时起到关键作用，如寻找最短路径、判断连通性、拓扑排序等。 1....

    acm-ICPC 搜索算法DFS和BFS文件格式（ppt）经典算法“剪枝”等算法

    在计算机科学中，特别是在图论和算法领域，DFS和BFS是两种基本的图遍历方法，主要用于搜索图中的所有节点。它们在解决各种问题，如路径查找、连通性检测和最短路径计算等方面发挥着重要作用。 **深度优先搜索（DFS...

    基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频

    基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项：使用matlab2021a或者更高版本测试，运行里面的Runme.m文件，不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...

    图的 DFS 和BFS

    图的深度优先搜索（DFS, Depth First Search）和广度优先搜索（BFS, Breadth First Search）是图论中的两种重要算法，用于遍历或搜索树或图。这两种算法在计算机科学中有着广泛的应用，比如在路径查找、拓扑排序、...

    图的DFS和BFS遍历

    图的深度优先搜索（DFS, Depth First Search）和广度优先搜索（BFS, Breadth First Search）是两种常用的图遍历算法，它们在很多实际问题中都有着广泛的应用，如网络爬虫、社交网络分析、路由算法等。 **深度优先...

    图的DFS和BFS算法实现 C++

    图的深度优先搜索（DFS, Depth First Search）和广度优先搜索（BFS, Breadth First Search）是图论中的两种基本遍历算法，广泛应用于数据结构和算法领域，如求解连通性、最短路径、拓扑排序等问题。在C++中，这两种...

    数据结构图bfs，Dfs遍历算法

    总结起来，数据结构中的图遍历算法，尤其是DFS和BFS，是理解和操作图形数据的基础。它们在实际编程问题中，如网络爬虫、社交网络分析、图形渲染等领域都有广泛应用。通过深入学习和实践这些算法，可以提升解决复杂...

    C语言：图的DFS和BFS（内附代码和算法思路）.docx

    在本文档中，我们讨论了如何使用C语言实现无向图的深度优先遍历（DFS）和广度优先遍历（BFS）。首先，我们需要理解数据结构中的图，它由顶点（vertices）和边（edges）组成，无向图意味着边没有方向。图的存储通常有...

    java 写的一些排序算法，dfs，bfs

    一些常用的排序算法，dfs bfs

    DFS \BFS生成树

    我们可以提炼出以下几个关键知识点：邻接表、深度优先搜索（Depth-First Search, DFS）、广度优先搜索（Breadth-First Search, BFS）以及如何利用这两种搜索算法生成树或森林。 ### 1. 邻接表 邻接表是一种用于...

    DFS和BFS用来干什么

    DFS和BFS DFS（Depth-First-Search）深度优先搜索算法，是搜索算法的一种。是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法...

    带BFS和DFS的图的实现

    在这个主题中，我们将深入探讨如何使用邻接矩阵实现图，并介绍两种常见的图遍历算法：广度优先搜索（BFS）和深度优先搜索（DFS）。 首先，邻接矩阵是表示图的一种直观方式。在二维数组中，我们为每对节点创建一个...

    PUZZLE15_dfs_C++求解15拼图问题_bfs_

    DFS是一种用于遍历或搜索树或图的算法。在这个问题中，我们可以通过递归地尝试将每个可移动的瓷砖移动到空位，然后回溯到之前的节点来实现DFS。每次移动后，我们检查目标状态是否达成，如果达成则返回真；否则，继续...

    ACM算法设计-BFS-DFS详解_算法_dfs_ACM_zoouts_bfs_

    在计算机科学领域，特别是算法设计中，BFS（广度优先遍历）和DFS（深度优先遍历）是两种常用图或树结构的遍历方法。这两种算法在解决许多问题时发挥着至关重要的作用，例如在寻找最短路径、解决迷宫问题、网络爬虫...

Magicbox
Global site tag (gtag.js) - Google Analytics