有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。
深度优先搜索：
下面图中的数字显示了深度优先搜索顶点被访问的顺序。 
为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：
(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>
它找到了一个合理的解，但这不具有一般性。因为找到的第一条路径取决于信息的物理组织形式。
如果目标在搜索空间中隐藏得不是太深，那么广度优先搜索的性能会很好。