A-A+

基于Java的BFS和DFS的简单实现

2016年05月05日 复杂网络, 数据结构 暂无评论 阅读 1,375 views 次

说在前面的话

读研期间研究的方向为社区发现,现阶段社区发现都是基于图来进行划分。所以讲复杂网络学习中的一些知识点进行笔记记录。同时,图在算法世界中的重要地位是不言而喻的,面试官问的问题中有很多的问题都可以用图的方法去解决。由此也可以看出图确实适用范围确实很广。

图的表示

  • 邻接矩阵 ,对于N个点的图,需要N×N的矩阵表示点与点之间是否有边的存在。这种表示法的缺点是浪费空间,尤其是对于N×N的矩阵是稀疏矩阵,即边的数目远远小于N×N的时候,浪费了巨大的存储空间。

邻接矩阵

  • 邻接链表,对于任何一个node A,外挂一个邻接链表,如果存在 A->X这样的边,就将X链入链表。 这种表示方法的优点是节省空间,缺点是所有链表都存在的缺点,地址空间的不连续造成缓存命中降低,性能有不如临界矩阵这样的数组。

邻接表

BFS

BFS(Breadth First Search)宽度优先搜索,顾名思义,就是将一棵树一层一层往下搜。算法首先搜索和s距离为k的所有顶点,然后再去搜索和S距离为k+l的其他顶点。BFS是一种完备策略,即只要问题有解,它就一定可以找到解。并且,广度优先搜索找到的解,还一定是路径最短的解。但是它盲目性较大,尤其是当目标节点距初始节点较远时,将产生许多无用的节点,因此其搜索效率较低。需要保存所有扩展出的状态,占用的空间大。

一般需求最优解的时候用广搜。

搜索过程是:从初始节点S0开始逐层向下扩展,在第n层节点还没有全部搜索完之前,不进入第n+1层节点的搜索。

代码框架:

BFS(){

         初始化队列

         while(队列不为空且未找到目标节点){

                  取队首节点扩展,并将扩展出的节点放入队尾;

                  必要时要记住每个节点的父节点;

          }

}

举例

BFS例子图

  1. package com.ifcoding.structure;
  2. import java.util.HashMap;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. public class BFSTest {
  6.     public static void main(String[] args) {
  7.         LinkedList<Character> lists = new LinkedList<Character>();
  8.         lists.add('w');
  9.         lists.add('r');
  10.         LinkedList<Character> listw = new LinkedList<Character>();
  11.         listw.add('s');
  12.         listw.add('i');
  13.         listw.add('x');
  14.         LinkedList<Character> listr = new LinkedList<Character>();
  15.         listr.add('s');
  16.         listr.add('v');
  17.         LinkedList<Character> listx = new LinkedList<Character>();
  18.         listx.add('w');
  19.         listx.add('i');
  20.         listx.add('u');
  21.         listx.add('y');
  22.         LinkedList<Character> listv = new LinkedList<Character>();
  23.         listv.add('r');
  24.         LinkedList<Character> listi = new LinkedList<Character>();
  25.         listi.add('u');
  26.         listi.add('x');
  27.         listi.add('w');
  28.         LinkedList<Character> listu = new LinkedList<Character>();
  29.         listu.add('i');
  30.         listu.add('x');
  31.         listu.add('y');
  32.         LinkedList<Character> listy = new LinkedList<Character>();
  33.         listy.add('u');
  34.         listy.add('x');
  35.         HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
  36.         graph.put('s', lists);
  37.         graph.put('w', listw);
  38.         graph.put('r', listr);
  39.         graph.put('x', listx);
  40.         graph.put('v', listv);
  41.         graph.put('i', listi);
  42.         graph.put('y', listy);
  43.         graph.put('u', listu);
  44.         HashMap<Character, Integer> dist = new HashMap<Character, Integer>();
  45.         char start = 's';
  46.         bfs(graph, dist, start);
  47.     }
  48.     private static void bfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Integer> dist,
  49.             char start) {
  50.         Queue<Character> queue = new LinkedList<Character>();
  51.         queue.add(start);
  52.         dist.put(start, 0);
  53.         int i = 0;
  54.         while (!queue.isEmpty()) {
  55.             char top = queue.poll();
  56.             i++;
  57.             System.out.println("The " + i + "th element:" + top + " Distance from s is " + dist.get(top));
  58.             int d = dist.get(top) + 1;
  59.             for (Character c : graph.get(top)) {
  60.                 if (!dist.containsKey(c)) {
  61.                     dist.put(c, d);
  62.                     queue.add(c);
  63.                 }
  64.             }
  65.         }
  66.     }
  67. }

DFS

DFS(Depth First Search)深度优先搜索是从起始顶点开始,递归访问其所有邻近节点,比如A节点是其第一个邻近节点,而B节点又是A的一个邻近节点,则DFS访问A节 点后再访问B节点,如果B节点有未访问的邻近节点的话将继续访问其邻近节点,否则继续访问A的未访问邻近节点,当所有从A节点出去的路径都访问完之后,继 续递归访问除A以外未被访问的邻近节点。

举例

DFS例子图

  1. package com.ifcoding.structure;
  2. import java.util.HashMap;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. public class DFSTest {
  6.     private static int count = 0;
  7.     public static void main(String[] args) {
  8.         LinkedList<Character> lists = new LinkedList<Character>();
  9.         lists.add('w');
  10.         lists.add('r');
  11.         LinkedList<Character> listw = new LinkedList<Character>();
  12.         listw.add('s');
  13.         listw.add('i');
  14.         listw.add('x');
  15.         LinkedList<Character> listr = new LinkedList<Character>();
  16.         listr.add('s');
  17.         listr.add('v');
  18.         LinkedList<Character> listx = new LinkedList<Character>();
  19.         listx.add('w');
  20.         listx.add('i');
  21.         listx.add('u');
  22.         listx.add('y');
  23.         LinkedList<Character> listv = new LinkedList<Character>();
  24.         listv.add('r');
  25.         LinkedList<Character> listi = new LinkedList<Character>();
  26.         listi.add('u');
  27.         listi.add('x');
  28.         listi.add('w');
  29.         LinkedList<Character> listu = new LinkedList<Character>();
  30.         listu.add('i');
  31.         listu.add('x');
  32.         listu.add('y');
  33.         LinkedList<Character> listy = new LinkedList<Character>();
  34.         listy.add('u');
  35.         listy.add('x');
  36.         HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
  37.         graph.put('s', lists);
  38.         graph.put('w', listw);
  39.         graph.put('r', listr);
  40.         graph.put('x', listx);
  41.         graph.put('v', listv);
  42.         graph.put('i', listi);
  43.         graph.put('y', listy);
  44.         graph.put('u', listu);
  45.         HashMap<Character, Boolean> visited = new HashMap<Character, Boolean>();
  46.         dfs(graph, visited);
  47.     }
  48.     private static void dfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited) {
  49.         visit(graph,visited,'s');
  50.     }
  51.     private static void visit(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited,
  52.             char start) {
  53.         if (!visited.containsKey(start)) {
  54.             count++;
  55.             System.out.println("The time into element " + start + ":" + count);
  56.             visited.put(start, true);
  57.             for (char c : graph.get(start)) {
  58.                 if (!visited.containsKey(c)) {
  59.                     visit(graph, visited, c);
  60.                 }
  61.             }
  62.             count++;
  63.             System.out.println("The time out element " + start + ":" + count);
  64.         }
  65.     }
  66. }

总结

总的来说,BFS多用于寻找最短路径的问题,DFS多用于快速发现底部节点。

给我留言

*

Copyright © If Coding 保留所有权利.   Theme  Ality   

用户登录