3358 www.Sina.com/http://www.Sina.com /深度优先遍历算法步骤： 1、访问初始尾部节点v，标记节点v已经访问2、节点v的第一个接收节点从v开始对w进行深度优先扫描递归(即，将w视为另一个v ) (步骤123 ) 5，寻找节点v的w相邻节点的写入相邻节点，转移到步骤3的具体问题分析：
a
B
C
d
e
a
0
1
1
0
0
B
1
0
1
1
1
C
1
1
0
0
0
d
0
1
0
0
0
e
0
1
0
0
0
//说明
//1意味着可以直接连接，0意味着不能直接连接
一、深度优先搜索（DFS）
现代大叔和b和c相连，联系是“1”b和a、c、d、e相连； c与a、b相连； d与b相连，e与b相连。
a连接到b，如果找到b，b连接到c，c不能连接到另一个节点，b、b返回到d，b返回到e。 )找到哪一点不变，一条路去黑。
每次都在访问完当前节点后首先访问当前节点的第一个邻接节点，可以看出这是一个递归的过程。
/第一个节点的下标publicintgetfirstneighbor (intindex ) for ) intj=0； jvertexList.size (； j () if ) Edges[index][j]0) ) { return j； } }返回- 1； //上一个相邻节点下标到下一个相邻节点publicintgetnextneighbor(intv1，int v2 ) ) for ) int v2； jvertexList.size (； j () if ) Edges[V1][J]0) ) { return j； }
} return -1; } //深度优先遍历 /* isVisited[] 记录结点是否访问的数组 * i 第一次是0 */ public void dfs(boolean[] isVisited,int i){ //首先访问该节点，输出 System.out.print(getValueByIndex(i)+"->"); isVisited[i]=true; int w=getfirstNeighbor(i); while(w!=-1){ //说明有邻接结点 if(!isVisited[w]){ dfs(isVisited,w); } //如果该结点被访问 w=getNextNeighbor(i,w); } } //重载dfs方法 public void dfs(){ isVisited=new boolean[vertexList.size()]; //遍历所有的结点进行dfs回溯 for(int i=0;i<vertexList.size();i++){ if(!isVisited[i]){ dfs(isVisited,i); } } }二、图的广度优先遍历(BFS)
广度优先遍历基本思想类似于一个分层搜索的过程，需要使用一个队列以保持访问过的结点的顺序，方便按照这个顺序来访问这些结点的领接结点。
算法步骤：
1访问初始结点v并标记结点v已经访问
2结点v入队列
3当队列非空时，继续执行，否则算法就结束
4出队列，取得队头节点u
5查找节点u的第一个领接结点v
6若结点u的领接结点w不存在，则转移到步骤3，否则循环执行以下三个步骤
6.1若结点w尚未被访问，则访问结点w并标记已经访问
6.2结点w入队列
6.3查找结点u的继w领接结点后的下一个领接结点，转移到步骤6.
查找过程如下:
A找到B，再找B的后继结点C，A可以找到C，此时B在队列中，将B弹出，从B结点找，此时A结点已经被访问过，C也被访问过，此时D被访问到了，E也可以访问到.
也就是，B和ljdbd访问到，D和E由A结点访问到。
//广度优先遍历 public void bfs(boolean isVisited[],int i){ int u; //表示队列的头结点对应下标 int w; //邻接结点 //队列，记录访问结点的顺序 LinkedList queue=new LinkedList(); //输出访问结点信息 System.out.println(getValueByIndex(i)+"->"); //标记为已访问 isVisited[i]=true; //将一访问的结点加入队列 queue.addLast(i); while(!queue.isEmpty()){ //取出队列的头结点下标 u=(Integer)queue.removeFirst(); //得到第一个邻接结点的下标 w=getfirstNeighbor(u); while(w!=-1){ //是否访问过 if(!isVisited[w]){ System.out.println(getValueByIndex(w)+"->"); //标记为已访问 isVisited[w]=true; //入队 queue.addLast(w); } //以u为前驱点，找w后面的下一个结点 w=getNextNeighbor(u,w); } } } //遍历所有的结点，都进行广度优先搜索 public void bfs(){ isVisited=new boolean[vertexList.size()]; for(int i=0;i<vertexList.size();i++){ if(!isVisited[i]){ bfs(isVisited,i); } } }get！