图的遍历

具体见我的上一篇广度优先搜索

DFS的基本策略

我们还是以上回的那个图为例：

遍历的顺序

个人觉得DFS比BFS更好理解，简单来说就是一条路走到黑，没路再回头的策略的策略。我们先来看这个例子（这回从0开始）：

打印0，找一个和0相邻的（未被打印）顶点（这里4和0之间选4）
打印4，找一个和4相邻的（未被打印）顶点（这里只有3）
打印3，找和3相邻的（未被打印）顶点（然而并没有）
回退到4，找到一个和4相邻的（未被打印）顶点（找到了2）
打印2，找一个和2相邻的（未被打印）顶点（找到了1）
打印1，找和1相邻的（未被打印）顶点（没有）
回退，找一个和2相邻的（未被打印）顶点（没有）
回退，找一个和4相邻的（未被打印）顶点（没有）
回退，找一个和1相邻的（未被打印）顶点（没有）
结束

不难发现，这和我们走迷宫的套路是一样的(一直往左手边的路走，找不到了回退)，没错，DFS一个最经典的应用便是走迷宫

代码实现

递归实现

根据上面的分析，不难发现DFS是一个递归算法，循环调用以达遍历目的，这里为了标记已经打印的点，也采用一个visited[]数组来存储是否打印的情况。代码是这样的：

void DFSUtil(int v,boolean visited[]){//把遍历部分单独抽出
//标记当前的点为已经标记
visited[v] = true;
System.out.print(v+" ");//打印
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()){
int n = i.next();
if(!visited[n])
DFSUtil(n,visited);//遍历与当前节点相邻的所有未被打印节点
	} 
}
void DFS(int v){
boolean visited[] = new boolean[this.V];
DFSUtil(v,visited);
}

下面再来看看非递归实现

非递归实现

类比BFS的队列存储，BFS可以利用栈来存储：

搜索是入栈的过程：当栈顶顶点还有相邻的顶点的时候就将该顶点入栈
打印是出栈的过程：当栈顶顶点已经没有相邻的顶点时就将该顶点出栈（也就是打印的过程）

下面是一个实例分析：（还是这个图）

（空栈）
0 （0入栈）
04（0和4相邻，4入栈）
043（3和4相邻，3入栈）
04（没有顶点和3相邻，3出栈,打印3）
042（与栈顶顶点相邻的还有2，2入栈）
0421（1和2相邻，1入栈）
042（没有顶点和1相邻，1出栈,打印1）
04（没有顶点和2相邻，2出栈,打印2）
0（没有顶点和4相邻，4出栈,打印4）
（没有顶点和0相邻，0出栈,打印0）

这样当栈为空的时候整个遍历就完全结束了，下面是代码（基本和BFS一模一样）：

void DFS(int s){
    //参观过为true
    boolean visited[] = new boolean[V];
    //第一个遍历的节点已经访问，设为true
    LinkedList<Integer> stack = new LinkedList<>();
    visited[s] = true;
    stack.push(s);//把已经访问的节点加入队列

    while (stack.size()!=0){
        s = stack.pop();//弹出栈顶元素并打印
        System.out.print(s+" ");
        Iterator<Integer> i = adj[s].listIterator();
        while (i.hasNext()){
            int n = i.next();//若该节点没有访问
            if(!visited[n]){
            visited[n] = true;//访问该节点
            stack.push(n);//加入队列
            }
        }
    }
}

就这样，图的遍历结束了。写这两篇加深了我对图的搜索的认识，后面就是最小生成树和最短路径算法了，游戏才刚刚开始。

广度优先搜索（BFS） Previous

图 Next