图的深度优先遍历详解
说明
- 深度优先遍历,即先向纵深处挖掘遍历,等这条路走不通再回溯
- 设置要开始遍历的第一个顶点,然后寻找该顶点的第一个邻接顶点,如果第一个邻接顶点存在,则从第一个邻接顶点又重新开始深度优先,寻找它的第一个邻接顶点,直到他们的第一个邻接顶点不存在或者第一个邻接顶点已经被访问,那么寻找它的下一个邻接顶点,直到寻找完所有的顶点
- 很明显需要使用递归
- 当没有通路的最后一个邻接顶点相连的所有顶点全部遍历完时,则回溯判断上一个顶点的下一个邻接顶点,直到遍历完然后再回溯
- 直到遍历完所有的顶点
- 说明:当 当前顶点的第一个邻接顶点已经被访问过时,才遍历它的下一个邻接顶点
- 源码见下
源码及分析
深度优先核心代码
//深度优先算法实现
/**
* @param isVisited 判断当前顶点是否已经遍历过
* @param v 从遍历的当前顶点下标
*/
public void dfs(boolean[] isVisited, int v) {
//先输出当前顶点信息
System.out.print(getValueByIndex(v) + "-->");
//将当前节点设置为已经访问过
isVisited[v] = true;
//获取当前节点的第一个节点
int w = getFirstNeighbor(v);
//如果当前顶点存在,则递归遍历
while (w != -1) {
//依旧需要判断当前顶点是否访问过
if (!isVisited[w]) {
dfs(isVisited, w);
}
//如果w节点已经被访问过
w = getNextNeighbor(v, w);
}
}
//对dfs进行重载,遍历所有的顶点
public void dfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
}
深度优先遍历代码实现
package algorithm.datastructor.graph;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @author AIMX_INFO
* @version 1.0
*/
public class Graph {
//使用邻接矩阵表示图
//使用集合存储图的顶点
private ArrayList<String> vertexList;
//使用二维数组即矩阵描述顶点之间的关系
private int[][] edges;
//边的个数
private int numOfEdges;
//定义变量判断是否访问过
private boolean[] isVisited;
//测试
public static void main(String[] args) {
int n = 5;
String[] vertexs = {"A", "B", "C", "D", "E"};
//创建图
Graph graph = new Graph(n);
//添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//连接顶点
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
//显示图
graph.showGraph();
System.out.println("深度优先遍历");
graph.dfs();
}
//n为顶点的个数
public Graph(int n) {
edges = new int[n][n];
vertexList = new ArrayList<>(n);
numOfEdges = 0;
isVisited = new boolean[n];
}
//插入顶点
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
/**
* 添加边
*
* @param v1 顶点在集合中存储的下标
* @param v2 顶点在集合中的下标
* @param weight 两个顶点之间的权值,0或者1,表示是否相连
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//返回节点的个数
public int getNumOfVertex() {
return vertexList.size();
}
//返回边的个数
public int getNumOfEdges() {
return numOfEdges;
}
//返回下标 i 对应的数
public String getValueByIndex(int i) {
return vertexList.get(i);
}
//返回v1和v2的权值
public int getWeigh(int v1, int v2) {
return edges[v1][v2];
}
//显示矩阵
public void showGraph() {
for (int[] link : edges) {
System.out.println(Arrays.toString(link));
}
}
//获取与当前顶点连接的第一个邻接顶点
public int getFirstNeighbor(int v) {
for (int i = 0; i < vertexList.size(); i++) {
if (edges[v][i] > 0) {
return i;
}
}
return -1;
}
//根据前一个邻接顶点获取下一个邻接节点的下标
/**
* @param v1 当前顶点
* @param v2 当前顶点的第一个顶点
* @return 返回下一个邻接顶点
*/
public int getNextNeighbor(int v1, int v2) {
for (int i = v2 + 1; i < vertexList.size(); i++) {
if (edges[v1][i] > 0) {
return i;
}
}
return -1;
}
//深度优先算法实现
/**
* @param isVisited 判断当前顶点是否已经遍历过
* @param v 从遍历的当前顶点下标
*/
public void dfs(boolean[] isVisited, int v) {
//先输出当前顶点信息
System.out.print(getValueByIndex(v) + "-->");
//将当前节点设置为已经访问过
isVisited[v] = true;
//获取当前节点的第一个节点
int w = getFirstNeighbor(v);
//如果当前顶点存在,则递归遍历
while (w != -1) {
//依旧需要判断当前顶点是否访问过
if (!isVisited[w]) {
dfs(isVisited, w);
}
//如果w节点已经被访问过
w = getNextNeighbor(v, w);
}
}
//对dfs进行重载,遍历所有的顶点
public void dfs() {
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
}