Algorithms | BFS & DFS

Posted on | | Visitors

这一篇笔记来谈谈有关图的算法

先来看看图的分类：
一般来说，图分为有向图和无向图两种，在此基础上每条边可能还会有 weight
在图中，每个点称为 vertex，每条边称为 edge，图用 G = (V, E) 来表示
V 是所有 vertex 的集合，E 是每条边 (v, w) 的集合

graph

上图里左边表示 Undirected Graph，右边表示 Directed Graph

如何把图用代码的形式表示出来呢？
有两种方法：Adjacency Matrix 和 Adjacency List

Adjacency Matrix:
其中 Adjacency Matrix 代表用一个 2D array 来存储图
row 和 colunm 都表示图中的点，如果两个点之间有边，则把该 cell 标记为 1
如果这两个点之间没有边，则把该 cell 标记为 0
如上图左边，Array[A][B] = 1, Array[A][E] = 0
值得关注的是，在 Undirected Graph 中，2D array 的表示形式是中心对称的
因为点 A 和 B 有一条边，则点 B 和 A 当然也有一条边
相应的 Array[A][B] = 1, Array[B][A] = 1

Adjacency List:
下面再来看看 Adjacency List，它是 Array－based LinkedList
Array 长度为图中点的个数，每一个 array cell 里是一个 linkedlist
这个 linkedlist 链接着相邻的点
比如，对于左边的 Undirected Graph 来说
Array[B] –> A –> C –> D 这就是一个 linkedlist

Adjacency Matrix VS Adjacency List

这两种表示方式在时间，空间上的花费也不同，下面就来分析一下
对于 Adjacency Matrix 来说，它的优点是能在 O(1) 时间内判断两个点之间是否有边
直接看 Array[v][w] 是否等于 1
但 Adjacency Matrix 太浪费空间，他要花费 n^2 的内存
然而我们只使用了其中很小一部分，array 中存储着 1 的 cell 才是我们关心的
空间花费太大

对于 Adjacency List 来说，它的好处是只使用了 O(n + m) 的内存
其中 n 是 vertex 的个数，m 是 edge 的个数
在实际生活中，我们用 Adjacency List 的情况更多一点

BFS

Breadth First Search 是一种很常见的 traversal graph 的算法
顾名思义，它是以 breadth 为 frist 的
给定一个起始点 s，访问它的所有相邻的点
直到所有与它距离为 1 的点都访问完了，再访问与它距离为 2 的点，依此类推

下面给出了 BFS 的 Java 代码
它用了 Adjacency List 来表示图
main() 方法里的测试代码是文章开头图片里的右边的 Directed Graph
点 A, B, C, D, E 分别表示成 0, 1, 2, 3, 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.io.*;
import java.util.*;
 
// this class represents a directed graph using linked list
class Graph{
    private int n; // number of vertices
    private LinkedList<Integer> adj[];
	
    // constructor
    public Graph(int n){
	this.n = n;
	adj = new LinkedList[n];
	for (int i = 0; i < n; ++i){
	    adj[i] = new LinkedList(); 
	}
    }
	
    void addEdge(int v, int w){
	adj[v].add(w);
    }
	
    // prints BFS traversal from a given vertex
    void BFS(int s){
	// mark all the vertices as not visited 
	// by default, all values are false
	boolean visited[] = new boolean[n];
		
	LinkedList<Integer> l = new LinkedList<Integer>();
		
	// mark the current node as visited and add it
	visited[s] = true;
	l.add(s);
		
	while (l.size() != 0){
	    s= l.poll();
	    System.out.print(s + " ");
			
	    Iterator<Integer> i = adj[s].listIterator();
	    while(i.hasNext()){
		int j = i.next();
		if (!visited[j]) {
		    visited[j] = true;
		    l.add(j);
		}
	    }
        }
    }
	
    public static void main(String[] args){
	Graph g = new Graph(5);
		
	g.addEdge(0, 1);
	g.addEdge(1, 2);
	g.addEdge(1, 3);
	g.addEdge(2, 4);
	g.addEdge(3, 2);
	g.addEdge(4, 3);
		
	System.out.println("Following is the BFS traversal from vetex 1(vertex B):");
	g.BFS(1);
    }
}

运行结果为

Following is the BFS traversal from vetex 1(vertex B):
1 2 3 4

值得注意的是，我们从点 B 出发，结果为 1，2，3，4
即 B –> C –> D –> E，并没有点 A
因为这是一个有向图，从 B 到 A 并没有 edge

DFS

Depth First Search，顾名思义即以 Depth 为 first
给定一个点 v，visit 离它距离为 1 的点
再 visit 离它距离为 2 的点，再 ……
直到没有点可以 visit 后，再 backtrack，看看在之前的支路上又没有漏掉的点

下面给出了 DFS 的 Java 代码实现
main() 方法里用的仍然是之前的 directed graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
import java.io.*;
public class GraphDFS {
    private int V;  // number of vertices
    // array of lists for adjacency list representation
    private LinkedList<Integer> adj[];
	
    // constructor
    public GraphDFS(int v){
	V = v;
	adj = new LinkedList[v];
	for (int i = 0; i < v; i++){
	    adj[i] = new LinkedList();
	}
    }
	
    // function to add edge
    void addEdge(int v, int w){
	adj[v].add(w);
    }
	
    // function used by DFS
    void DFSUtil(int v, boolean visited[]){
	// mark the current node as visited and print it
	visited[v] = true;
	System.out.print(v + " ");
		
	// Recur for all the vertices adjacent to this vertex
	Iterator<Integer> i = adj[v].listIterator();
	while (i.hasNext()){
	    int n = i.next();
	    if (!visited[n]){
	        DFSUtil(n, visited);
	    }
	}
    }
	
    void DFS(int v){
	boolean visited[] = new boolean[V];
	DFSUtil(v, visited);
    }
	
    public static void main(String[] args){
	GraphDFS g = new GraphDFS(5);
		
	g.addEdge(0, 1);
	g.addEdge(1, 2);
	g.addEdge(1, 3);
	g.addEdge(2, 4);
	g.addEdge(3, 2);
	g.addEdge(4, 3);
		
	System.out.println("Following is the DFS traversal from vetex 1(vertex B):");
	g.DFS(1);
    }
}

运行结果为

Following is the DFS traversal from vetex 1(vertex B):
1 2 4 3

注意，从点 B 出发并不能 visit 到 A
因为从点 B 到点 A 并没有一条 edge

如果我们想 visit 点 A，也是有办法的
可以一个一个点的调用 DFSUtil() 方法，这样所有的点都会遍历到
不管这些店是否与其它点有 edge
我们只需修改 DFS() 方法就可以

1
2
3
4
5
6
7
8
9
void DFS(int v){
    boolean visited[] = new boolean[V];
		
    // Call the recursive helper function to print DFS traversal
    // starting from all vertices one by one
    for(int i = 0; i < V; i++){
	if (!visited[i]) DFSUtil(i, visited);
    }
}

此时运行结果为

Following is the DFS traversal from vetex 1(vertex B):
0 1 2 4 3

谢谢你请我吃糖果：）