[MasterThe Coding Interview]Algorithms:Searching + BFS + DFS

發表於 分類於 閱讀次數：

本篇為MasterThe Coding Interview教學影片筆記文

搜尋存在各種地方，google的搜尋引擎、蝦皮的搜尋商品等，任何有規模的網站都會用到搜尋功能，以下是這次要介紹的搜尋演算法：

適用於list的資料，從頭到尾一個一個的查看，是一個O(n)的演算法，因為最後的情況是要找的東西在最後面。

1
2
3
4
5
6
7
8
9
10
11
12
var beasts = ['Centaur' , 'Godzilla' , 'Mosura' , 'Minotaur' , 'Hydra' , 'Nessie'];

beasts.indexOf('Godzilla');
beasts.findIndex(function(item){
	return item === 'Godzilla'
});

beasts.find(function(item){
	return item === 'Godzilla'
});

beasts.includes('Godzilla');

適用已經sort過的資料，透過不斷的從中間分割來找到目標，時間複雜度是O(logn)。

1
2
3
4
5
6
7
8
9
//      9
//  4      34
//1   6  12  45
//假設今天要找12，先從9分割
//因為12比9大，所以走右邊
//因為34比12小，所以走左邊
//找到12

//總結以上，透過樹高可以知道經歷步驟數，所以時間複雜度是O(logn)

從第一層開始一層一層的往下開始找，一定是找完當前這一層才會往下一層走。

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
//      9
//  4      20
//1   6  15  170
[9 , 4 , 20 , 1 , 6 , 15 , 170]

//第一種方法，僅限用在二元樹
function breadthFirstSearch(){
	let currentNode = this.root;
	let list = [];
	let queue = [];
	queue.push(currentNode);
	
	while(queue.length > 0){
		currentNode = queue.shift();
		list.push(currentNode.value);
		if(currentNode.left){
			queue.push(currentNode.left)
		}
		if(currentNode.right){
			queue.push(currentNode.right);
		}
	}
}

//用遞迴的方式
function breadthFirstSearchRecursive(queue , list){
	if(!queue.length){
		return list;
	}
	let currentNode = queue.shift();
	list.push(currentNode.value);
	if(currentNode.left){
		queue.push(currentNode.left)
	}
	if(currentNode.right){
		queue.push(currentNode.right);
	}
	return breadthFirstSearchRecursive(queue , list)
}
優點 缺點
Shortest Path More Memory
Closer Nodes

從第一個分支開始往最深處找，直到沒辦法再深才會換到下一個分支。DFS 主要有三種方式，前序遍歷 (Preorder)、中序遍歷 (Inorder)、後序遍歷 (Postorder)，跟BFS不一樣，不需要一個queue來儲存所有還未找尋的node，只需要儲存分支上的Node即可。

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
//      9
//  4      20
//1   6  15  170
InOrder - [1, 4, 6, 9, 15, 20, 170]
PreOrder - [9, 4, 1, 6, 20, 15, 170]
PostOrder - [1, 6, 4, 15, 170, 20, 9]

function DFSInorder(){
	return traverseInOrder(root , [])
}

function traverseInOrder(node , list){
	if(node.left){
		traverseInOrder(node.left , list)
	}
	list.push(node.value);
	if(node.right){
		traverseInOrder(node.right , list)
	}
	return list;
}

function DFSPreOrder(){
	return traversePreOrder(root , [])
}

function traversePreOrder(node , list){
	list.push(node.value);
	if(node.left){
		traversePreOrder(node.left , list)
	}
	if(node.right){
		traversePreOrder(node.right , list)
	}
	return list;
}

function DFSPostOrder(){
	return traversePostOrder(root , [])
}

function traversePostOrder(node , list){
	if(node.left){
		traversePostOrder(node.left , list)
	}
	if(node.right){
		traversePostOrder(node.right , list)
	}
	list.push(node.value);
	return list;
}
優點 缺點
Less Memory Can Get Slow
Does Path Exist

BFS vs DFS

  1. If you know a solution is not far from the root of the tree → BFS(適合搜尋最近的點)
  2. If the tree is very deep and solutions are rare → BFS(因為樹太深了，DFS會耗費太多時間)
  3. If the tree is very wide → DFS(因為樹太深了，BFS會耗費太多memory)
  4. If solutions are frequent but located deep in the tree → DFS
  5. Determining whether a path exists between two nodes →DFS
  6. Finding the shortest path → BFS

BFS and DFS in Graph

其實圖跟樹的方法都一樣，只是可以更明顯的看出兩者的差異，如果圖中的一個node連結很多很多node，那我們用BFS就有可能會耗費太多memory，相反的，如果圖的深度很深，用DFS的時候因為是用resursive實作，會造成太多的call stack，耗費太多memory和時間。

但是！當我們圖的路徑有權重的時候，找出最短路徑就不能使用BFS來實作，必須用另外兩種特殊的演算法來實作，Dijkstra和Bellman-Ford，兩個都是最短路徑的演算法，Bellman-Ford的效率比Dijkstra好，而且Bellman-Ford可以有負數，Dijkstra不行，但值得一提的是Bellman-Ford的worst case有可能到O(n^2)，所以當路徑的權重沒有負數的時候，我們仍然會使用Dijkstra。

補充：Finding The Shortest Path, With A Little Help From Dijkstra