阅读量:0
深度优先搜索的基本思想
1.深度优先搜索，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先搜索的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点为初始节点，访问它的第一个邻接节点。可以这样理解：每次都在访问完当前节点后首先访问当前节点的第一个邻接节点
2.我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接节点进行横向访问
3.显然，深度优先搜索是一个递归的过程
深度优先按搜索算法步骤
1.访问初始节点 v，并标记节点 v 为已访问
2.查找节点 v 的第一个邻接节点 w
3.若 w 存在，则继续执行 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个节点继续
4.若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当作另一个 v，然后进行步骤 1 2 3）
5.查找节点 v 的 w 邻接节点的下一个邻接节点，转到步骤 3
public class Graph { private ArrayList<String> vertexList; //存储顶点的集合 private int[][] edges; //存储图对应的邻接矩阵 private int numOfEdges; //表示边的数目 //定义一个数组 boolean[]，记录某个节点是否被访问 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); } //添加边 // A-B A-C B-C B-D B-E 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(); //测试 dfs System.out.println("深度遍历"); graph.dfs(); } //构造器 public Graph(int n) { //初始化矩阵和 vertexList edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; isVisited = new boolean[n]; } //得到第一个邻接节点的下标 w /** * * @param index * @return 如果存在，返回对应下标，否则返回 -1 */ public int getFirstNeighbor(int index) { for (int j = 0;j < vertexList.size(); j++) { if (edges[index][j] > 0) { return j; } } return -1; } //根据前一个邻接节点的下标来获取下一个邻接节点 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; } //深度优先搜索算法 private void dfs(boolean[] isVisited, int i) { //首先我们访问该节点，输出 System.out.print(getValueByIndex(i) + " -> "); //将节点设置为已经访问 isVisited[i] = true; //查找节点 i 的第一个邻接节点 w int w = getFirstNeighbor(i); while (w != -1) { //说明存在 if (!isVisited[w]) { dfs(isVisited, w); } //如果 w 节点已经被访问过 w = getNextNeighbor(i, w); } } //对 dfs 进行一个重载，遍历我们所有的节点，并进行 dfs public void dfs() { //遍历所有的节点，进行 dfs （回溯） for (int i = 0; i < getNumOfEdges(); i++) { if (!isVisited[i]) { dfs(isVisited, i); } } } //图中常用的方法 //返回节点的个数 public int getNumOfVertex() { return vertexList.size(); } //返回边的个数 public int getNumOfEdges() { return numOfEdges; } //返回节点 i(下标)对应的数据 0->"A" 1->"B" 2->"C" public String getValueByIndex(int i) { return vertexList.get(i); } //返回 v1 和 v2 的权值 public int getWeight(int v1, int v2) { return edges[v1][v2]; } //显示图对应的矩阵 public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } } //插入节点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 /** * * @param v1 代表第一个顶点对应的下标 * @param v2 代表第二个顶点对应的下标 * @param weight */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }