当前位置:   article > 正文

图的深度优先遍历

图的深度优先遍历

一 图遍历介绍

所谓图的遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略。

1 深度优先遍历 

2 广度优先遍历

二 深度优先遍历基本思想

图的深度优先搜索(Depth First Search) ,简称DFS。

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。

四 实战

1 要求

对下图进行深度优先搜索, 从A 开始遍历。

2 思路分析

3 代码

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.LinkedList;
  4. /**
  5. * @className: Graph
  6. * @description: 图
  7. * @date: 2021/3/28
  8. * @author: cakin
  9. */
  10. public class Graph {
  11. // 存储顶点集合
  12. private ArrayList<String> vertexList;
  13. // 存储图对应的邻结矩阵
  14. private int[][] edges;
  15. // 表示边的数目
  16. private int numOfEdges;
  17. // 表示某个结点是否被访问
  18. private boolean[] isVisited;
  19. /**
  20. * 功能描述:图的擦拭
  21. *
  22. * @param args 命令行
  23. * @author cakin
  24. * @date 2021/3/28
  25. */
  26. public static void main(String[] args) {
  27. // 顶点
  28. String Vertexs[] = {"A", "B", "C", "D", "E"};
  29. //String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
  30. // 结点的个数
  31. int n = Vertexs.length;
  32. // 创建图对象
  33. Graph graph = new Graph(n);
  34. // 循环的添加顶点
  35. for (String vertex : Vertexs) {
  36. graph.insertVertex(vertex);
  37. }
  38. // 添加边
  39. graph.insertEdge(0, 1, 1); // A-B
  40. graph.insertEdge(0, 2, 1); // A-C
  41. graph.insertEdge(1, 2, 1); // B-C
  42. graph.insertEdge(1, 3, 1); // B-D
  43. graph.insertEdge(1, 4, 1); // B-E
  44. // 显示邻结矩阵
  45. graph.showGraph();
  46. // dfs测试
  47. System.out.println("dfs:");
  48. graph.dfs(); // A->B->C->D->E
  49. }
  50. // 构造器
  51. public Graph(int n) {
  52. // 初始化矩阵
  53. edges = new int[n][n];
  54. // 初始化 vertexList
  55. vertexList = new ArrayList<>(n);
  56. // 边的数量
  57. numOfEdges = 0;
  58. }
  59. /**
  60. * 功能描述:得到某个顶点的第一个邻接结点的下标 w
  61. *
  62. * @param index 顶点索引
  63. * @return 如果存在就返回对应的下标,否则返回-1
  64. */
  65. public int getFirstNeighbor(int index) {
  66. for (int j = 0; j < vertexList.size(); j++) {
  67. if (edges[index][j] > 0) {
  68. return j;
  69. }
  70. }
  71. return -1;
  72. }
  73. /**
  74. * 功能描述:根据前一个邻接结点的下标来获取下一个邻接结点
  75. *
  76. * @param v1 第1个顶点
  77. * @param v2 第2个顶点,也就是邻节点
  78. * @return int 邻节点的下一个邻节点
  79. * @author cakin
  80. * @date 2021/3/29
  81. */
  82. public int getNextNeighbor(int v1, int v2) {
  83. for (int j = v2 + 1; j < vertexList.size(); j++) {
  84. if (edges[v1][j] > 0) {
  85. return j;
  86. }
  87. }
  88. return -1;
  89. }
  90. /**
  91. * 功能描述:深度优先遍历算法
  92. *
  93. * @author cakin
  94. * @date 2021/3/29
  95. * @param isVisited 节点是否被访问数组
  96. * @param i 被访问节点的下标
  97. * @return
  98. * @description:
  99. */
  100. private void dfs(boolean[] isVisited, int i) {
  101. // 输出被访问节点
  102. System.out.print(getValueByIndex(i) + "->");
  103. // 将该结点设置为已经访问
  104. isVisited[i] = true;
  105. // 查找结点i的第一个邻接结点w
  106. int w = getFirstNeighbor(i);
  107. while (w != -1) { // 找到该邻节点
  108. if (!isVisited[w]) {
  109. // 递归进行深度优先遍历算法
  110. dfs(isVisited, w);
  111. }
  112. // 如果w结点已经被访问过,找下一个邻节点
  113. w = getNextNeighbor(i, w);
  114. }
  115. }
  116. /**
  117. * 功能描述:对 dfs 进行一个重载, 遍历所有的结点,并进行 dfs
  118. *
  119. * @author cakin
  120. * @date 2021/3/29
  121. */
  122. public void dfs() {
  123. isVisited = new boolean[vertexList.size()];
  124. // 遍历所有的结点,进行 dfs
  125. for (int i = 0; i < getNumOfVertex(); i++) {
  126. if (!isVisited[i]) {
  127. dfs(isVisited, i);
  128. }
  129. }
  130. }
  131. /**
  132. * 功能描述:返回结点的个数
  133. *
  134. * @author cakin
  135. * @date 2021/3/28
  136. */
  137. public int getNumOfVertex() {
  138. return vertexList.size();
  139. }
  140. /**
  141. * 功能描述:显示图对应的矩阵
  142. *
  143. * @author cakin
  144. * @date 2021/3/28
  145. */
  146. public void showGraph() {
  147. for (int[] link : edges) {
  148. System.err.println(Arrays.toString(link));
  149. }
  150. }
  151. /**
  152. * 功能描述:得到边的数目
  153. *
  154. * @return 得到边的数目
  155. * @author cakin
  156. * @date 2021/3/28
  157. */
  158. public int getNumOfEdges() {
  159. return numOfEdges;
  160. }
  161. /**
  162. * 功能描述:返回结点i(下标)对应的数据
  163. *
  164. * @param i 节点下标
  165. * @return 节点对应的数据
  166. * @author cakin
  167. * @date 2021/3/28
  168. * @description: 举例如下:
  169. * 0->"A" 1->"B" 2->"C"
  170. */
  171. public String getValueByIndex(int i) {
  172. return vertexList.get(i);
  173. }
  174. /**
  175. * 功能描述:返回v1和v2的权值
  176. *
  177. * @param v1 第1个顶点的下标
  178. * @param v2 第2个顶点的下标
  179. * @return int 两个顶点间的权值
  180. * @author cakin
  181. * @date 2021/3/28
  182. */
  183. public int getWeight(int v1, int v2) {
  184. return edges[v1][v2];
  185. }
  186. /**
  187. * 功能描述:插入结点
  188. *
  189. * @param vertex 节点的数据
  190. * @author cakin
  191. * @date 2021/3/28
  192. */
  193. public void insertVertex(String vertex) {
  194. vertexList.add(vertex);
  195. }
  196. /**
  197. * 功能描述:添加边
  198. *
  199. * @param v1 第1个顶点对应的下标
  200. * @param v2 第2个顶点对应的下标
  201. * @param weight 表示第1个顶点和第2个顶点的权重
  202. */
  203. public void insertEdge(int v1, int v2, int weight) {
  204. edges[v1][v2] = weight;
  205. edges[v2][v1] = weight;
  206. numOfEdges++;
  207. }
  208. }

4 测试

  1. [0, 1, 1, 0, 0]
  2. [1, 0, 1, 1, 1]
  3. [1, 1, 0, 0, 0]
  4. [0, 1, 0, 0, 0]
  5. [0, 1, 0, 0, 0]
  6. dfs:
  7. A->B->C->D->E->

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/804753
推荐阅读
相关标签
  

闽ICP备14008679号