图学习笔记索引

图学习笔记索引(全部)
001自定义输入流In类实现
002背包数据类型Bag实现
003无向图数据类型实现
004基于图的深度优先搜索
005使用深度优先搜索找图中的所有连通分量
005-1基于深度优先搜索查找图中连通路径
006基于深度优先搜索判断图中是否存在环
007基于深度优先搜索判断一个无向图图是否是一个二分图
008广度优先搜索查找连通图中的最短路径
009有向图数据类型实现
010有向图的可达性
011带权重的无向边数据类型Edge实现
012加权无向图数据类型实现

本文参考《算法(第4版)》

基于深度优先搜索判断图中是否存在环

1.实现代码

从文件中读取无向图图的顶点关系。
tinyWG.txt文件中的第一行为顶点数，第二行为边数。
第三行到最后是两个相邻的顶点：
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3

package algorithms.graph;

import java.io.IOException;
/*
 * 基于深度优先搜索判断图中是否有环，假设不含自环和平行环
 * */
public class Cycle {
    private boolean[] marked;
    private boolean hasCycle;
    public Cycle(Graph G){
    	this.marked = new boolean[G.V()];
    	for(int s = 0; s < G.V(); s++){
    		  if(!marked[s])   //排除在一个连通图中的顶点重复查找
    		      dfs(G, s, s);
    	}
    }
    public void dfs(Graph G, int v, int u){
    	marked[v] = true;
    	for(int w : G.adj(v))
    		if(!marked[w])
    			dfs(G, w, v);
    		else if( w != u){  //非上一个相邻顶点已标记，即存在环
    			hasCycle = true;
    	        //break;
    		}
    } 
    public boolean hasCycle(){
    	return hasCycle;
    }
	public static void main(String[] args) throws IOException {
		In in = new In("D:\\tinyWG.txt"); 
		Graph G = new Graph(in);
		System.out.println(G);
		Cycle cycle = new Cycle(G);
        System.out.println(cycle.hasCycle());
	}

}

2.总结

基于深度优先搜索判断图中是否存在环，其思想是在dfs()方法中加入一个顶点参数，该参数传入上一次递归操作中的顶点，即上一个相邻顶点。使用深度优先搜索，不断地在相邻顶点遍历过程中，如果相邻顶点未被标记，则进行标记，继续递归的进行查找。如果相邻顶点被标记且不是上一个相邻顶点，即不是平行环，则说明无向图中存在环。