[关闭]
@LIUHUAN 2019-09-03T13:12:42.000000Z 字数 4657 阅读 865

DFS

algorithm

深度优先搜索算法(DFS)

标签（空格分隔）： algorithm

  1. void traveralGraph(){
  2.     初始化标志hashmap
  3.     for node in G: // 对图中的每一个节点
  4.         如果没有被访问：hashmap[node] == false
  5.         执行DFS             DFS(G,node,hashmap)
  6. }
  8.     void DFS(G,node,hashmap){
  9.         // 递归的出口
  10.         如果节点被访问了：if hashmap[node] == true:
  11.                 返回：          return
  12.         1.访问节点：visited(node)
  13.         2.标志节点已被访问:hashmap[node] = true
  14.         3.获取node节点的旁边，邻接节点集合:adjlist = getadjList(node)
  15.             for adjNode : adjlist: 对每一个邻接点，执行
  16.                 1).如果邻接点没有被访问：hashmap[adjNode] != true
  17.                 2).以这个节点开始，进行DFS遍历 :DFS(G,adjNode,hashmap)
  18.         }
  19.     }
  1.     A --- B --- C
  2.           |
  3.           D
  4.           |
  5.           E
  2. |   |     |   |     | C |    |   |   | D |     |   |    | E |  | |
  3. |   | --> | B | ->  | B | -> | B |   | B |     | B |    | B |  |B|
  4. | A |     | A |     | A |    | A |   | A |     | A |    | A |  |A|
  5. —————                        
  6. DFS(A) -> 
  7.           DFS(B) -> for n in (D,C)
  8.                     DFS(C) 
  9.                     DFS(D)   DFS(C)返回
  10.                                     DFS(D)    
  11.                                               DFS(D)返回
  12.                                                         DFS(E)
  13.                                                                 DFS(E)返回
  14.                                                                 DFS(B)返回
  15.                                                                 DFS(A)返回
  1. public class DFSMethod {
  2. public static void main(String[] args){
  3.     G = new Graph();
  4.     hashmap = new hashmap();
  5.     for node in G:
  6.         if hashmap[node] == false:
  7.             DFS(G,node,hashmap);// 表示从0 节点开始遍历
  9. }
  10. public static void BFS(G,node,hashmap) {
  11.     //1.已经认为是在队列当中，说明已经要被访问了，所以这么标志
  12.     visitedMap.put(node, true);  
  14.     //2.访问
  15.     visited(node);
  17.     // 3.获取相邻的节点
  18.     ArrayList<Node> adjNodeList = G.getAdjectList(q); 
  20.     // 4.开始以邻接点为七点执行DFS搜索
  21.     for(int i = 0; i < adjNodeList.size() ; ++i) {
  22.         node = adjNodelist.get(i)
  23.         /**没有被访问过，则以这个节点开始执行DFS搜索*/
  24.         if (visitedMap[node] == false) { // 没有被访问过
  25.         DFS(g,node,hashmap);
  27.     }
  28.     }//end for
  30. }
  32. public static void visited(Node s) {
  33.     // 这里只是简单的打印一下，可进行性统计、计数等操作
  34.     System.out.println(s);
  35. }
  36. }

2 图联通量的遍历

2.1 问题描述

  1. [[0,0,1,0,0,0,0,1,0,0,0,0,0],
  2.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  3.  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  4.  [0,1,0,0,1,1,0,0,1*,0, 1*,0,0],
  5.  [0,1,0,0,1,1,0,0,1*,1*,1*,0,0],
  6.  [0,0,0,0,0,0,0,0,0,0,1*,0,0],
  7.  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  8.  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
  9.  上述中有个连通分量（带*的1），大小为6
  1. /***
  2.  * x,y 坐标的相邻坐标
  3.  * (x-1,y-1)---(x-1,y)----(x,y-1)
  4.  * (x , y-1)---(x , y)----(x,y+1)
  5.  * (x+1,y-1)---(x+1,y)----(x+1,y+1)
  6.  */
  9. public static int visitedCount = 0;
  11. public static int maxAreaOfIsland(int[][] grid) {
  12.     //访问标志
  13.     HashMap<String,Boolean> visitedMap = new HashMap<String,Boolean>();
  15.     int count = 0;
  16.     for(int x =0; x < grid.length; ++x) {
  17.         for(int y = 0; y < grid[0].length; ++y) {
  18.             if(grid[x][y] == 0)// 跳过非连通节点
  19.                 continue;
  20.             String xykey = x + ":"  + y;
  22.             if(visitedMap.containsKey(xykey) == false) {
  23.                 DFS(grid,visitedMap,x,y);// 把连通的岛遍历一下，并标志下，visitedCount记录这个连通分量节点数
  24.                 count = count > visitedCount ? count : visitedCount;
  25.                 visitedCount = 0;// 下一个连通分量遍历
  26.             }
  27.         }
  28.     }
  29.     return count;
  30. }
  33. public static void DFS(int[][] grid,HashMap<String,Boolean> visitedMap,int startx,int starty) { 
  36.     NodeValue e = new NodeValue(startx, starty);
  37.     //访问标志
  38.     visitedMap.put(startx + ":" + starty, true);
  39.     visited(e);
  41.     /*获取邻接点集合*/
  42.     ArrayList<NodeValue> adjlist = getAdjList(grid,e);
  43.     // 邻接点调用DFS 
  44.     for(int i = 0 ;i < adjlist.size(); ++i) {
  45.         e = adjlist.get(i);
  46.         String ekey = e.x +":" + e.y;
  47.         if(visitedMap.containsKey(ekey) == false) {
  48.             DFS(grid,visitedMap,e.x,e.y);
  49.         }
  50.     }
  51. }
  53. private static void visited(NodeValue e) {
  54.     visitedCount ++;// 访问到的节点数增加，计数功能
  55. }
  57. /**寻找其相邻节点的函数*/
  58. public static ArrayList<NodeValue> getAdjList(int[][] grid,NodeValue e) {
  59.     ArrayList<NodeValue> adjlist = new ArrayList<NodeValue>();
  60.     int xlen = grid.length;
  62.     int ylen = grid[0].length;
  63.     if(e.x - 1 >=0 ) { // 上面(x-1,y)
  64.         if (grid[e.x -1][e.y] == 1) {
  65.             adjlist.add(new NodeValue(e.x - 1,e.y));
  66.         }
  67.     }
  69.     if(e.y - 1 >=0 ) { //左面(x,y-1)
  70.         if (grid[e.x][e.y - 1 ] == 1) {
  71.             adjlist.add(new NodeValue(e.x,e.y - 1 ));
  72.         }
  73.     }
  75.     if(e.x + 1 < xlen ) { // 下面 (x+1,y)
  76.         if (grid[e.x + 1][e.y] == 1) {
  77.             adjlist.add(new NodeValue(e.x + 1,e.y));
  78.         }
  79.     }
  81.     if(e.y + 1 < ylen ) { // 右面(x,y+1)
  82.         if (grid[e.x ][e.y + 1] == 1) {
  83.             adjlist.add(new NodeValue(e.x,e.y + 1));
  84.         }
  85.     }
  87.     return adjlist;
  88. }
  90. /**存储下x,y的坐标*/
  91. static class NodeValue{
  92.     public int x, y;
  93.     public NodeValue(int x,int y){
  94.         this.x = x;
  95.         this.y = y;
  96.     }
  97. }

3.参考内容：

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注