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;
    }
}