8： 图的深度优先

1： 图的深度游戏：（邻杰表表示）

?从 v节点开始： 遍历v的邻接点g， g未被访问，再遍历g的邻接点

是一个递归的过程，然后再回到v

?

就是对一个图的深度优先遍历

?

具体过程 看： 附件ppt:

?

?

??

package com.algorithm.common.graph;/** * 图深度优先 * @author lijunqing */public class DFS {        /**     * 标记节点是否访问     */    private boolean[] marked;    private int count;    public DFS(Graph g, int s) {        marked=new boolean[g.V()];        dsf(g, s);    }    /**     * dsf 从s一个邻接点开始不断深入 递归到 遍历玩g的最后一个邻接点结束     * @param g     * @param s     */    private void dsf(Graph g, int s) {        marked[s]=true;        count++;        for(int w: g.adj(s)) { // 到遍历玩g的最后一个邻接点结束            if(!marked[w]) {                dsf(g, w);            }        }    }        /**     * 看节点是否被标记     * @param v     * @return     */    public boolean marked(int v) {        return marked(v);    }        /**     * 被标记的节点数     * @return     */    public int count() {        return count;    }}

?