社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
前言
图的遍历与前面文章中的二叉树遍历还是存在很大区别的。所谓图的遍历指的是从图中的某一个顶点出发访问图中的其余顶点,并且需要保证每个顶点只被访问一次。由于图比二叉树复杂得多,所以前面二叉树的遍历算法在图中是行不通的。因为对于任意一个顶点来讲,都可能与其余的顶点发生连接。如果不对访问的顶点做一些处理,出发重复访问的几率是很高的。因此,一个基本思想是设置一个标记数组,主要用于标记已经被访问过的顶点。图的遍历算法主要有两种:深度优先遍历和广度优先遍历。本篇文章主要介绍的是深度优先遍历算法。
深度优先遍历的具体过程
深度优先遍历,简称DFS。具体思想是不放过任何一个死角。在图的遍历中就是从图的某个顶点v出发,访问此顶点,然后从v的未被访问过的邻接点出发深度优先遍历图,直至图中的所有和v有路径相通的顶点都被访问到(对于连通图来讲)。
为了更好说明深度优先遍历的过程,以下面的图为例:
上图的邻接表定义如下:
注意:顶点0的第一个元素是2而不是5,其顶点类似。
从以上过程来看,上图的顶点访问次序依次是:0,2,1,3,5,4。
深度优先遍历算法的实现
首先需要定义一个存储图的数据结构,在Java中可以使用邻接表来实现图存储。具体而言就是,图的顶点用一维数组存储,每个顶点的邻接顶点用一个单链表进行存储。
图的数据结构:邻接表的实现
package com.rhwayfun.algorithm.graph;
public class MyGraph {
//顶点数目
private int V;
//边的数目
private int E;
//邻接表
private Bag<Integer>[] adj;
public MyGraph(int V){
this.V = V;
this.E = 0;
//创建邻接表
adj = (Bag<Integer>[])new Bag[V];
//将所有链表初始化
for(int v = 0; v < V; v++){
adj[v] = new Bag<Integer>();
}
}
public int V(){
return V;
}
public int E(){
return E;
}
public void addEdge(int v,int w){
//将w添加到v的链表中
adj[v].add(w);
//将v添加到w的链表中
adj[w].add(v);
E++;
}
//获取顶点v的邻接表顶点列表
public Iterable<Integer> adj(int v){
return adj[v];
}
}
深度优先遍历算法的实现代码:
package com.rhwayfun.algorithm.graph;
/**
* 深度优先搜索
* <p>Title:DepthFirstSearch</p>
* <p>Description:</p>
* @author rhwayfun
* @date Dec 22, 2015 8:04:23 PM
* @version 1.0
*/
public class DepthFirstSearch {
//创建一个标记数组
private boolean[] marked;
//访问计数器
private int count;
/**
* 构造一幅图并进行深度优先遍历
* <p>Description: </p>
* @param G 读入的图
* @param s 开始遍历的顶点
*/
public DepthFirstSearch(MyGraph G,int s) {
marked = new boolean[G.V()];
dfs(G,s);
}
private void dfs(MyGraph G, int s) {
marked[s] = true;
count++;
System.out.print(s + " ");
for(int w : G.adj(s)){
//如果没有被访问过就继续遍历
if(!marked[w]) dfs(G, w);
}
}
public boolean[] getMarked() {
return marked;
}
public int getCount() {
return count;
}
}
深度优先遍历算法的非递归实现方式
使用非递归的方式与递归的思想是一致的,不同的在于需要使用一个栈保存遍历的顶点。下面是具体的实现代码:
package com.rhwayfun.algorithm.graph;
import java.util.Iterator;
import java.util.Stack;
/**
* 使用非递归方式对图进行深度优先遍历
* <p>Title:NonrecursiveDFS</p>
* <p>Description:</p>
* @author rhwayfun
* @date Dec 22, 2015 10:43:35 PM
* @version 1.0
*/
public class NonrecursiveDFS {
//创建一个标记数组标记访问过的元素
private boolean[] marked;
@SuppressWarnings("unchecked")
public NonrecursiveDFS(MyGraph G, int s){
marked = new boolean[G.V()];
//创建一个迭代器迭代每个顶点的邻接表
Iterator<Integer>[] adj = (Iterator<Integer>[])new Iterator[G.V()];
//获得每个顶点的邻接表
for(int v = 0; v < G.V(); v++){
adj[v] = G.adj(v).iterator();
}
//创建一个栈用户存放遍历的顶点
Stack<Integer> stack = new Stack<Integer>();
marked[s] = true;
System.out.print(s + " ");
stack.add(s);
while(!stack.isEmpty()){
int v = stack.peek();
//如果有邻接表的话,就继续遍历
if(adj[v].hasNext()){
int w = adj[v].next();
//判断是否已被访问过
if(!marked[w]){
//没访问过就将器标记为已访问过,下次不会再访问了
marked[w] = true;
System.out.print(w + " ");
stack.push(w);
}
}else{
//如果没有邻接表的话就将该顶点弹出栈顶
stack.pop();
}
}
}
public boolean marked(int v) {
return marked[v];
}
}
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!