深度优先算法所遵循的搜索策略是尽可能“深”地搜索一个图。在深度优先搜索中，对于最新发现的定点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v的点。这一过程一直进行到发现从源顶点可达的所有顶点位置为止。

用java实现的深度优先算法代码如下：

import java.util.List;import java.util.ArrayList;/** * 栈 */public class Stack
     
       {	private List
      
        stack = new ArrayList
       
        ();	/**	 * 进栈	 * 	 * @param 进栈元素	 */	public void push(E e) {		stack.add(e);	}	/**	 * 出栈	 * 	 * @return 栈顶元素	 */	public E pop() {		if (!isEmpty()) {			E result = stack.get(stack.size() - 1);			stack.remove(stack.size() - 1);			return result;		} else {			return null;		}	}	/**	 * 取栈顶元素	 * 	 * @return 栈顶元素	 */	public E top() {		if (!isEmpty()) {			return stack.get(stack.size() - 1);		} else {			return null;		}	}	/**	 * 查询栈是否为空	 * 	 * @return	 */	public boolean isEmpty() {		return stack.isEmpty();	}}
       
      
     

 

/** * 边 *  * @author Thief * */public class Edge {	public Edge(String vertexA, String vertexB) {		super();		this.vertexA = vertexA;		this.vertexB = vertexB;	}		/**	 * 顶点A	 */	private String vertexA;	/**	 * 顶点B	 */	private String vertexB;	/**	 * 该边是否已经被访问	 */	boolean isVisited = false;	public String getVertexA() {		return vertexA;	}	public void setVertexA(String vertexA) {		this.vertexA = vertexA;	}	public String getVertexB() {		return vertexB;	}	public void setVertexB(String vertexB) {		this.vertexB = vertexB;	}	public boolean isVisited() {		return isVisited;	}	public void setVisited(boolean isVisited) {		this.isVisited = isVisited;	}}

 

import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;/** * 图 *  * @author Thief * */public class Graph {	/**	 * 顶点	 */	private List
     
       vertexList = new ArrayList
      
       ();	/**	 * 边	 */	private Map
       
        > edgeMap = new HashMap
        
         >();	/**	 * 向图中添加顶点	 * 	 * @param vertex	 *            顶点名字	 * @throws Exception	 *             当顶点已经存在时抛出异常	 */	public void addVertex(String vertex) throws Exception {		if (vertexList.contains(vertex)) {			throw new Exception("该顶点已经存在！");		} else {			vertexList.add(vertex);		}	}	/**	 * 向图中添加边	 * 	 * @param vertexName_A	 *            顶点A的名字	 * @param vertexName_B	 *            顶点B的名字	 * @throws Exception	 *             顶点不存在或边已经存在时抛出异常	 */	public void addEdge(String vertexA, String vertexB) throws Exception {		if (!vertexList.contains(vertexA) || !vertexList.contains(vertexB)) {			throw new Exception("顶点不存在！");		}		if (containsEdge(vertexA, vertexB)) {			throw new Exception("边已经存在");		}		if (edgeMap.containsKey(vertexA)) {			List
         
           list = edgeMap.get(vertexA);			list.add(new Edge(vertexA, vertexB));		} else {			List
          
            list = new ArrayList
           
            (); list.add(new Edge(vertexA, vertexB)); edgeMap.put(vertexA, list); } if (edgeMap.containsKey(vertexB)) { List
            
              list = edgeMap.get(vertexB); list.add(new Edge(vertexB, vertexA)); } else { List
             
               list = new ArrayList
              
               (); list.add(new Edge(vertexB, vertexA)); edgeMap.put(vertexB, list); } } /** * 判断图中该边是否已经存在 * * @param vertexA * 顶点A * @param vertexB * 顶点B * @return 如果存在返回true，否则返回false */ private boolean containsEdge(String vertexA, String vertexB) { boolean isExist = false; if (edgeMap.containsKey(vertexA)) { List
               
                 list = edgeMap.get(vertexA); if (list.contains(new Edge(vertexA, vertexB))) { isExist = true; } } return isExist; } /** * 深度优先搜索 * * @param startVertex * 起点 */ public void DFS(String startVertex) { Stack
                
                  stack = new Stack
                 
                  (); stack.push(startVertex); System.out.println("搜索开始。。。"); while (!stack.isEmpty()) { String currentVertex = stack.top(); //判断与该顶点相连的边是否都已经被访问 boolean isAllVisited = true; for (Edge edge : edgeMap.get(currentVertex)) { if (!edge.isVisited) { isAllVisited = false; break; } } if (isAllVisited) { stack.pop(); if (!stack.isEmpty()) { System.out.println(currentVertex + " --> " + stack.top()); } } else { List
                  
                    listA = edgeMap.get(currentVertex); for (Edge edge : listA) { if (!edge.isVisited) { stack.push(edge.getVertexB()); System.out.println(currentVertex + " --> " + edge.getVertexB()); edge.isVisited = true; // 将边BA的访问标志置为true List
                   
                     listB = edgeMap.get(edge.getVertexB()); for (Edge item : listB) { if (item.getVertexB().equals(currentVertex)) { item.isVisited = true; } } break; } } } } System.out.println("搜索结束。。。"); }}
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

测试代码如下：

public class Test {	public static void main(String[] args) {		Graph graph = new Graph();		try {			graph.addVertex("A");			graph.addVertex("B");			graph.addVertex("C");			graph.addVertex("D");			graph.addVertex("E");			graph.addVertex("F");			graph.addVertex("G");			graph.addEdge("A", "B");			graph.addEdge("B", "C");			graph.addEdge("B", "D");			graph.addEdge("A", "E");			graph.addEdge("E", "F");			graph.addEdge("A", "G");			graph.DFS("A");		} catch (Exception e) {			System.out.println(e.getMessage());		}	}}

执行结果如下：

搜索开始。。。

A  -->  B

B  -->  C

C  -->  B

B  -->  D

D  -->  B

B  -->  A

A  -->  E

E  -->  F

F  -->  E

E  -->  A

A  -->  G

G  -->  A

搜索结束。。。