基于Java的BFS和DFS的简单实现
说在前面的话
读研期间研究的方向为社区发现,现阶段社区发现都是基于图来进行划分。所以讲复杂网络学习中的一些知识点进行笔记记录。同时,图在算法世界中的重要地位是不言而喻的,面试官问的问题中有很多的问题都可以用图的方法去解决。由此也可以看出图确实适用范围确实很广。
图的表示
- 邻接矩阵 ,对于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(队列不为空且未找到目标节点){
取队首节点扩展,并将扩展出的节点放入队尾;
必要时要记住每个节点的父节点;
}
}
举例
- package com.ifcoding.structure;
- import java.util.HashMap;
- import java.util.LinkedList;
- import java.util.Queue;
- public class BFSTest {
- public static void main(String[] args) {
- LinkedList<Character> lists = new LinkedList<Character>();
- lists.add('w');
- lists.add('r');
- LinkedList<Character> listw = new LinkedList<Character>();
- listw.add('s');
- listw.add('i');
- listw.add('x');
- LinkedList<Character> listr = new LinkedList<Character>();
- listr.add('s');
- listr.add('v');
- LinkedList<Character> listx = new LinkedList<Character>();
- listx.add('w');
- listx.add('i');
- listx.add('u');
- listx.add('y');
- LinkedList<Character> listv = new LinkedList<Character>();
- listv.add('r');
- LinkedList<Character> listi = new LinkedList<Character>();
- listi.add('u');
- listi.add('x');
- listi.add('w');
- LinkedList<Character> listu = new LinkedList<Character>();
- listu.add('i');
- listu.add('x');
- listu.add('y');
- LinkedList<Character> listy = new LinkedList<Character>();
- listy.add('u');
- listy.add('x');
- HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
- graph.put('s', lists);
- graph.put('w', listw);
- graph.put('r', listr);
- graph.put('x', listx);
- graph.put('v', listv);
- graph.put('i', listi);
- graph.put('y', listy);
- graph.put('u', listu);
- HashMap<Character, Integer> dist = new HashMap<Character, Integer>();
- char start = 's';
- bfs(graph, dist, start);
- }
- private static void bfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Integer> dist,
- char start) {
- Queue<Character> queue = new LinkedList<Character>();
- queue.add(start);
- dist.put(start, 0);
- int i = 0;
- while (!queue.isEmpty()) {
- char top = queue.poll();
- i++;
- System.out.println("The " + i + "th element:" + top + " Distance from s is " + dist.get(top));
- int d = dist.get(top) + 1;
- for (Character c : graph.get(top)) {
- if (!dist.containsKey(c)) {
- dist.put(c, d);
- queue.add(c);
- }
- }
- }
- }
- }
DFS
DFS(Depth First Search)深度优先搜索是从起始顶点开始,递归访问其所有邻近节点,比如A节点是其第一个邻近节点,而B节点又是A的一个邻近节点,则DFS访问A节 点后再访问B节点,如果B节点有未访问的邻近节点的话将继续访问其邻近节点,否则继续访问A的未访问邻近节点,当所有从A节点出去的路径都访问完之后,继 续递归访问除A以外未被访问的邻近节点。
举例
- package com.ifcoding.structure;
- import java.util.HashMap;
- import java.util.LinkedList;
- import java.util.Queue;
- public class DFSTest {
- private static int count = 0;
- public static void main(String[] args) {
- LinkedList<Character> lists = new LinkedList<Character>();
- lists.add('w');
- lists.add('r');
- LinkedList<Character> listw = new LinkedList<Character>();
- listw.add('s');
- listw.add('i');
- listw.add('x');
- LinkedList<Character> listr = new LinkedList<Character>();
- listr.add('s');
- listr.add('v');
- LinkedList<Character> listx = new LinkedList<Character>();
- listx.add('w');
- listx.add('i');
- listx.add('u');
- listx.add('y');
- LinkedList<Character> listv = new LinkedList<Character>();
- listv.add('r');
- LinkedList<Character> listi = new LinkedList<Character>();
- listi.add('u');
- listi.add('x');
- listi.add('w');
- LinkedList<Character> listu = new LinkedList<Character>();
- listu.add('i');
- listu.add('x');
- listu.add('y');
- LinkedList<Character> listy = new LinkedList<Character>();
- listy.add('u');
- listy.add('x');
- HashMap<Character, LinkedList<Character>> graph = new HashMap<Character, LinkedList<Character>>();
- graph.put('s', lists);
- graph.put('w', listw);
- graph.put('r', listr);
- graph.put('x', listx);
- graph.put('v', listv);
- graph.put('i', listi);
- graph.put('y', listy);
- graph.put('u', listu);
- HashMap<Character, Boolean> visited = new HashMap<Character, Boolean>();
- dfs(graph, visited);
- }
- private static void dfs(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited) {
- visit(graph,visited,'s');
- }
- private static void visit(HashMap<Character, LinkedList<Character>> graph, HashMap<Character, Boolean> visited,
- char start) {
- if (!visited.containsKey(start)) {
- count++;
- System.out.println("The time into element " + start + ":" + count);
- visited.put(start, true);
- for (char c : graph.get(start)) {
- if (!visited.containsKey(c)) {
- visit(graph, visited, c);
- }
- }
- count++;
- System.out.println("The time out element " + start + ":" + count);
- }
- }
- }
总结
总的来说,BFS多用于寻找最短路径的问题,DFS多用于快速发现底部节点。