图的深度优先遍历介绍
图遍历介绍
所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历
深度优先遍历基本思想
图的深度优先搜索(Depth First Search) 。
深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点， 可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
显然，深度优先搜索是一个递归的过程
深度优先遍历算法步骤
- 访问初始结点v，并标记结点v为已访问。
- 查找结点v的第一个邻接结点w。
- 若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
- 若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
- 查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
代码实现
首先增加几个方法和属性
//表示是否被访问过
private boolean [] isVisited;
/**
* 得到第一个邻接节点的下标 不存在返回-1
* @param index
* @return
*/
public int getFirstNeighbor(int index){
for (int j=0;j<vertexList.size();j++){
if (edges[index][j]>0){
return j;
}
}
return -1;
}
/**
* 根据前一个邻接节点的下标来获取下一个邻接节点
* @param v1
* @param v2
* @return
*/
public int getNextNeighbor(int v1,int v2){
for (int j=v2+1;j<vertexList.size();j++){
if (edges[v1][j]>0){
return j;
}
}
return -1;
}
深度优先遍历
/**
* 深度优先遍历
* @param isVisited
* @param i
*/
private 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);
}
}
/**
* 深度优先遍历
*/
public void dfs(){
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]){
dfs(isVisited,i);
}
}
}
广度优先遍历基本思想
图的广度优先搜索(Broad First Search) 。
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
广度优先遍历算法步骤
- 1、访问初始结点v并标记结点v为已访问。
- 2、 结点v入队列
- 3、 当队列非空时，继续执行，否则算法结束。
- 4、 出队列，取得队头结点u。
- 5、查找结点u的第一个邻接结点w。
- 6、若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
- 6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
- 6.2 结点w入队列
- 6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
代码实现
//对一个结点进行广度优先遍历的方法
private void bfs(boolean[] isVisited, int i) {
int u ; // 表示队列的头结点对应下标
int w ; // 邻接结点w
//队列，记录结点访问的顺序
LinkedList queue = new LinkedList();
//访问结点，输出结点信息
System.out.print(getValueByIndex(i) + "=>");
//标记为已访问
isVisited[i] = true;
//将结点加入队列
queue.addLast(i);
while( !queue.isEmpty()) {
//取出队列的头结点下标
u = (Integer)queue.removeFirst();
//得到第一个邻接结点的下标 w
w = getFirstNeighbor(u);
while(w != -1) {//找到
//是否访问过
if(!isVisited[w]) {
System.out.print(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 < getNumOfVertex(); i++) {
if(!isVisited[i]) {
bfs(isVisited, i);
}
}
}
评论区