深度优先与广度优先_深度优先 广度优先

有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。 
深度优先搜索：
下面图中的数字显示了深度优先搜索顶点被访问的顺序。

为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：
(1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。
(2) 当不能执行规则1时，如果栈不空，就从栈中弹出一个顶点。
(3) 如果不能执行规则1和规则2，就完成了整个搜索过程。
广度优先搜索：
在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中，算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区域。它是用队列来实现的。
下面图中的数字显示了广度优先搜索顶点被访问的顺序。

实现广度优先搜索，也要遵守三个规则：
(1) 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。
(2) 如果因为已经没有未访问顶点而不能执行规则1时，那么从队列头取一个顶点，并使其成为当前顶点。
(3) 如果因为队列为空而不能执行规则2，则搜索结束。
下面是一个图类的java代码，dfs()为深度优先搜索算法，bfs()为广度优先搜索算法：

//用于实现深度优先搜索的栈类
class StackX{
private final int SIZE=20;
private int[] st;
private int top;
public StackX(){
        st=new int[SIZE];
        top=-1;
    }
public void push(int j){
        st[++top]=j;
    }
public int pop(){
return st[top--];
    }
public int peek(){
return st[top];
    }
public boolean isEmpty(){
return top==-1;
    }
}
//用于实现广度优先搜索的队列类
class Queue{
private final int SIZE=20;
private int[] queArray;
private int front;
private int rear;
public Queue(){
        queArray=new int[SIZE];
        front=0;
        rear=-1;
    }
public void insert(int j){
if(rear==SIZE-1)
            rear=-1;
        queArray[++rear]=j;
    }
public int remove(){
int temp=queArray[front++];
if(front==SIZE)
            front=0;
return temp;
    }
public boolean isEmpty(){
return ((rear+1==front)||(front+SIZE-1==rear));
    }
}
//顶点类
class Vertex{
public char label;
public boolean wasVisited;
public Vertex(char lab){
        label=lab;
        wasVisited=false;
    }
}
//图类
public class Graph {

private final int MAX_VERTS=20;
private Vertex vertexList[];
private int adjMat[][];
private int nVerts;
private StackX theStack;
private Queue theQueue;

/** Creates a new instance of Graph */
public Graph() {
        vertexList=new Vertex[MAX_VERTS];
        adjMat=new int[MAX_VERTS][MAX_VERTS];
        nVerts=0;
for (int j = 0; j < MAX_VERTS; j++) {
for (int k = 0; k < MAX_VERTS; k++) {
                adjMat[j][k]=0;
            }
        }
        theStack=new StackX();
        theQueue=new Queue();
    }
//增加一个顶点
public void addVertex(char lab){
        vertexList[nVerts++]=new Vertex(lab);
    }
//增加一条边
public void addEdge(int start,int end){
        adjMat[start][end]=1;
        adjMat[end][start]=1;
    }
public void displayVertex(int v){
        System.out.print(vertexList[v].label);
    }
//深度优先搜索
public void dfs(){
        vertexList[0].wasVisited=true;
        displayVertex(0);
        theStack.push(0);
while(!theStack.isEmpty()){
int v=getAdjUnvisitedVertex(theStack.peek());
if(v==-1)
                theStack.pop();
else{
                vertexList[v].wasVisited=true;
                displayVertex(v);
                theStack.push(v);
            }
        }
for(int j=0;j
            vertexList[j].wasVisited=false;
    }
//得到与v顶点邻接且未访问过的顶点标号
public int getAdjUnvisitedVertex(int v){
for (int j = 0; j < nVerts; j++) {
if(adjMat[v][j]==1&&vertexList[j].wasVisited==false)
return j;
        }
return -1;
    }
//广度优先搜索
public void bfs(){
        vertexList[0].wasVisited=true;
        displayVertex(0);
        theQueue.insert(0);
int v2;
while(!theQueue.isEmpty()){
int v1=theQueue.remove();
while((v2=getAdjUnvisitedVertex(v1))!=-1){
                vertexList[v2].wasVisited=true;
                displayVertex(v2);
                theQueue.insert(v2);
            }
        }
for (int j = 0; j < nVerts; j++) {
            vertexList[j].wasVisited=false;
        }
    }

}

 

===============================================================

一、深度优先搜索 
    深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
      深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。
二、    重排九宫问题游戏
在一个3乘3的九宫中有1-8的8个数及一个空格随机摆放在其中的格子里。如下面左图所示。现在要求实现这样的问题：将该九宫调整为如下图右图所示的形式。调整规则是：每次只能将与空格（上，下或左，右）相临的一个数字平移到空格中。试编程实现。
| 2 | 8  | 3 |                 | 1 | 2 | 3 |
-
| 1 |     | 4 |                 | 8 |    | 4 |
| 7 | 6  | 5 |                 | 7 | 6 | 5 |
深度优先搜索的路径示意图：

三、广度优先搜索

    在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。

广度优先搜索路径示意图：

四、航班问题（来自《The Art of Java》)
    一位顾客要预定一张从New York到Los Angeles的航班机票，下面是航班线路，请你为顾客找一种购票方案。

 

下面是用深度优先搜索求解的程序:

// Find connections using a depth-first search.
import java.util.*;
import java.io.*;
// Flight information.
class FlightInfo {
  String from;
  String to;
int distance;
boolean skip; // used in backtracking
  FlightInfo(String f, String t, int d) {
    from = f;
    to = t;
    distance = d;
    skip = false;
  }
}
class Depth {
final int MAX = 100;
// This array holds the flight information.
  FlightInfo flights[] = new FlightInfo[MAX]; 
int numFlights = 0; // number of entries in flight array
  Stack btStack = new Stack(); // backtrack stack
public static void main(String args[])
  {
    String to, from;
    Depth ob = new Depth();
    BufferedReader br = new
      BufferedReader(new InputStreamReader(System.in)); 
    ob.setup();  
try { 
      System.out.print("From? ");
      from = br.readLine(); 
      System.out.print("To? ");
      to = br.readLine(); 
      ob.isflight(from, to);
if(ob.btStack.size() != 0)
        ob.route(to);
    } catch (IOException exc) { 
      System.out.println("Error on input.");
    }
  }
// Initialize the flight database.
void setup()
  {
    addFlight("New York", "Chicago", 900);
    addFlight("Chicago", "Denver", 1000);
    addFlight("New York", "Toronto", 500);
    addFlight("New York", "Denver", 1800);
    addFlight("Toronto", "Calgary", 1700);
    addFlight("Toronto", "Los Angeles", 2500);
    addFlight("Toronto", "Chicago", 500);
    addFlight("Denver", "Urbana", 1000);
    addFlight("Denver", "Houston", 1000);
    addFlight("Houston", "Los Angeles", 1500);
    addFlight("Denver", "Los Angeles", 1000);
  }
// Put flights into the database.
void addFlight(String from, String to, int dist)
  {
if(numFlights < MAX) {
      flights[numFlights] =
new FlightInfo(from, to, dist);
      numFlights++;
    }
else System.out.println("Flight database full. ");
  }
// Show the route and total distance.
void route(String to)
  {
    Stack rev = new Stack();
int dist = 0;
    FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for(int i=0; i < num; i++) 
      rev.push(btStack.pop());
for(int i=0; i < num; i++) {
      f = (FlightInfo) rev.pop();
      System.out.print(f.from + " to ");
      dist += f.distance;
    }
    System.out.println(to);
    System.out.println("Distance is " + dist);
  }
/* If there is a flight between from and to,
     return the distance of flight;
     otherwise, return 0. */
int match(String from, String to)
  {
for(int i=numFlights-1; i > -1; i--) {
if(flights[i].from.equals(from) &&
         flights[i].to.equals(to) &&
!flights[i].skip)
      {
        flights[i].skip = true; // prevent reuse
return flights[i].distance;
      }
    }
return 0; // not found 
  }
// Given from, find any connection.
  FlightInfo find(String from)
  {
for(int i=0; i < numFlights; i++) {
if(flights[i].from.equals(from) &&
!flights[i].skip)
      {
        FlightInfo f = new FlightInfo(flights[i].from,
                             flights[i].to,
                             flights[i].distance);
        flights[i].skip = true; // prevent reuse
return f;
      }
    }
return null;
  }
// Determine if there is a route between from and to. 
void isflight(String from, String to)
  {
int dist;
    FlightInfo f;
// See if at destination.
    dist = match(from, to);
if(dist != 0) {
      btStack.push(new FlightInfo(from, to, dist));
return;
    }
// Try another connection.
    f = find(from);
if(f != null) {
      btStack.push(new FlightInfo(from, to, f.distance));
      isflight(f.to, to);
    }
else if(btStack.size() > 0) {
// Backtrack and try another connection.
      f = (FlightInfo) btStack.pop();
      isflight(f.from, f.to);
    }
  }
} 

解释：isflight()方法用递归方法进行深度优先搜索，它先调用match()方法检查航班的数据库，判断在from和to之间有没有航班可达。如果有，则获取目标信息，并将该线路压入栈中，然后返回（找到一个方案）。否则，就调用find()方法查找from与任意其它城市之间的线路，如果找到一条就返回描述该线路的FlightInfo对象，否则返回null。如果存在这样的一条线路，那么就把该线路保存在f中，并将当前航班信息压到栈的顶部，然后递归调用isflight()方法 ,此时保存在f.to中的城市成为新的出发城市.否则就进行回退,弹出栈顶的第一个节点,然后递归调用isflight()方法。该过程将一直持续到找到目标为止。

程序运行结果：

C:/java>java Depth
From? New York
To? Los Angeles
New York to Chicago to Denver to Los Angeles
Distance is 2900

C:/java>

     深度优先搜索能够找到一个解，同时，对于上面这个特定问题，深度优先搜索没有经过回退，一次就找到了一个解；但如果数据的组织方式不同，寻找解时就有可能进行多次回退。因此这个例子的输出并不具有普遍性。而且，在搜索一个很长，但是其中并没有解的分支的时候，深度优先搜索的性能将会很差，在这种情况下，深度优先搜索不仅在搜索这条路径时浪费时间，而且还在向目标的回退中浪费时间。

再看对这个例子使用广度优先搜索的程序：

程序运行结果：
C:/java>java Breadth
From? New York
To? Los Angeles
New York to Toronto to Los Angeles
Distance is 3000

// Find connections using a breadth-first search.
import java.util.*;
import java.io.*;
// Flight information.
class FlightInfo {
  String from;
  String to;
int distance;
boolean skip; // used in backtracking
  FlightInfo(String f, String t, int d) {
    from = f;
    to = t;
    distance = d;
    skip = false;
  }
}
class Breadth {
final int MAX = 100;
// This array holds the flight information.
  FlightInfo flights[] = new FlightInfo[MAX]; 
int numFlights = 0; // number of entries in flight array
  Stack btStack = new Stack(); // backtrack stack
public static void main(String args[])
  {
    String to, from;
    Breadth ob = new Breadth();
    BufferedReader br = new
      BufferedReader(new InputStreamReader(System.in)); 
    ob.setup();  
try { 
      System.out.print("From? ");
      from = br.readLine(); 
      System.out.print("To? ");
      to = br.readLine(); 
      ob.isflight(from, to);
if(ob.btStack.size() != 0)
        ob.route(to);
    } catch (IOException exc) { 
      System.out.println("Error on input.");
    }
  }
// Initialize the flight database.
void setup()
  {
    addFlight("New York", "Chicago", 900);
    addFlight("Chicago", "Denver", 1000);
    addFlight("New York", "Toronto", 500);
    addFlight("New York", "Denver", 1800);
    addFlight("Toronto", "Calgary", 1700);
    addFlight("Toronto", "Los Angeles", 2500);
    addFlight("Toronto", "Chicago", 500);
    addFlight("Denver", "Urbana", 1000);
    addFlight("Denver", "Houston", 1000);
    addFlight("Houston", "Los Angeles", 1500);
    addFlight("Denver", "Los Angeles", 1000);
  }
// Put flights into the database.
void addFlight(String from, String to, int dist)
  {  
if(numFlights < MAX) {
      flights[numFlights] =
new FlightInfo(from, to, dist);
      numFlights++;
    }
else System.out.println("Flight database full. ");
  }
// Show the route and total distance.
void route(String to)
  {
    Stack rev = new Stack();
int dist = 0;
    FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for(int i=0; i < num; i++) 
      rev.push(btStack.pop());
for(int i=0; i < num; i++) {
      f = (FlightInfo) rev.pop();
      System.out.print(f.from + " to ");
      dist += f.distance;
    }
    System.out.println(to);
    System.out.println("Distance is " + dist);
  }
/* If there is a flight between from and to,
     return the distance of flight;
     otherwise, return 0. */
int match(String from, String to)
  {
for(int i=numFlights-1; i > -1; i--) {
if(flights[i].from.equals(from) &&
         flights[i].to.equals(to) &&
!flights[i].skip)
      {
        flights[i].skip = true; // prevent reuse
return flights[i].distance;
      }
    }
return 0; // not found 
  }
// Given from, find any connection.
  FlightInfo find(String from)
  {
for(int i=0; i < numFlights; i++) {
if(flights[i].from.equals(from) &&
!flights[i].skip)
      {
        FlightInfo f = new FlightInfo(flights[i].from,
                             flights[i].to,
                             flights[i].distance);
        flights[i].skip = true; // prevent reuse
return f;
      }
    }
return null;
  }
/* Determine if there is a route between from and to
     using breadth-first search. */
void isflight(String from, String to)
  {
int dist, dist2;
    FlightInfo f;
// This stack is needed by the breadth-first search.
    Stack resetStck = new Stack();
// See if at destination.
    dist = match(from, to);
if(dist != 0) {
      btStack.push(new FlightInfo(from, to, dist));
return;
    }
/* Following is the first part of the breadth-first
       modification.  It checks all connecting flights
       from a specified node. */
while((f = find(from)) != null) {
      resetStck.push(f);
if((dist = match(f.to, to)) != 0) {
        resetStck.push(f.to);
        btStack.push(new FlightInfo(from, f.to, f.distance));
        btStack.push(new FlightInfo(f.to, to, dist));
return;
      }
    }
/* The following code resets the skip fields set by
       preceding while loop. This is also part of the
       breadth-first modifiction. */
int i = resetStck.size();
for(; i!=0; i--)
      resetSkip((FlightInfo) resetStck.pop());
// Try another connection.
    f = find(from);
if(f != null) {
      btStack.push(new FlightInfo(from, to, f.distance));
      isflight(f.to, to);
    }
else if(btStack.size() > 0) {
// Backtrack and try another connection.
      f = (FlightInfo) btStack.pop();
      isflight(f.from, f.to);
    }
  }
// Reset skip field of specified flight.
void resetSkip(FlightInfo f) {
for(int i=0; i< numFlights; i++)
if(flights[i].from.equals(f.from) &&
         flights[i].to.equals(f.to))
           flights[i].skip = false;
  }
}

C:/java>

它找到了一个合理的解，但这不具有一般性。因为找到的第一条路径取决于信息的物理组织形式。

如果目标在搜索空间中隐藏得不是太深，那么广度优先搜索的性能会很好。