深度优先算法所遵循的搜索策略是尽可能“深”地搜索一个图。在深度优先搜索中，对于最新发现的定点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v的点。这一过程一直进行到发现从源顶点可达的所有顶点位置为止。
用java实现的深度优先算法代码如下：
import java.util.List;
import java.util.ArrayList;
/**
* 栈
*/
public class Stack<E> {
private List<E> stack = new ArrayList<E>();
/**
* 进栈
*
* @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<String> vertexList = new ArrayList<String>();
/**
* 边
*/
private Map<String, List<Edge>> edgeMap = new HashMap<String, List<Edge>>();
/**
* 向图中添加顶点
*
* @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<Edge> list = edgeMap.get(vertexA);
list.add(new Edge(vertexA, vertexB));
} else {
List<Edge> list = new ArrayList<Edge>();
list.add(new Edge(vertexA, vertexB));
edgeMap.put(vertexA, list);
}
if (edgeMap.containsKey(vertexB)) {
List<Edge> list = edgeMap.get(vertexB);
list.add(new Edge(vertexB, vertexA));
} else {
List<Edge> list = new ArrayList<Edge>();
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<Edge> list = edgeMap.get(vertexA);
if (list.contains(new Edge(vertexA, vertexB))) {
isExist = true;
}
}
return isExist;
}
/**
* 深度优先搜索
*
* @param startVertex
* 起点
*/
public void DFS(String startVertex) {
Stack<String> stack = new Stack<String>();
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<Edge> 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<Edge> 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
搜索结束。。。