首页 > 代码库 > DFS & BFS
DFS & BFS
DFS 深度优先
BFS 广度优先
DFS或者BFS都是在联通区域内遍历节点的方法
用在二叉树上DFS有preOreder，inOrder，postOrder，BFS就是层次遍历。
在二叉树上的节点，只有两个选择，left 和right，即，对于每一个节点，in 有1个， out 有两个，有向图
在矩阵的节点上，有四个选择，up、down、left和right四种选择，即，即，对于每一个节点，in 有4个， out 有4个，有向图
在surrounded Regions 中可以使用DFS或者BFS来解决问题
下面以4x4 矩阵为例，说明DFS和BFS的工作过程
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <iostream> 4 #include <vector> 5 #include <queue> 6 #include <stack> 7 using namespace std; 8 9 void printArray(int *array, int size) 10 { 11 for(int i = 0; i < size; i++) 12 cout << array[i]<< "\t" ; 13 cout << endl; 14 } 15 16 void printVector(vector<char> array ) 17 { 18 for(int i = 0; i <array.size(); i++) 19 cout << array[i]<< "\t" ; 20 cout << endl; 21 } 22 23 void printVector(vector<int> array ) 24 { 25 for(int i = 0; i <array.size(); i++) 26 cout << array[i]<< "\t" ; 27 cout << endl; 28 } 29 30 class Solution { 31 queue<pair<int, int> > m_que; 32 public: 33 void dfs(vector<vector<int> > &board, int i, int j) 34 { 35 size_t row = board.size(); 36 size_t col = board[0].size(); 37 38 if(i < 0 || i > row-1 || j < 0 || j > col-1) 39 return; 40 if( board[i][j] == INT_MAX) 41 return; 42 cout << "(" << i <<"," << j << ") = " << board[i][j] << endl ; 43 board[i][j] = INT_MAX;//tag, in order to reverse back 44 dfs(board, i, j-1); 45 dfs(board, i, j+1); 46 dfs(board, i-1, j); 47 dfs(board, i+1, j); 48 } 49 50 void fill(vector<vector<int> > &board, int i, int j){ 51 size_t row = board.size(); 52 size_t col = board[0].size(); 53 54 if(i<0 || i>=row || j<0 || j>=col || board[i][j]== INT_MAX) 55 return; 56 57 pair<int, int> p ; 58 p.first = i; 59 p.second = j; 60 m_que.push(p); 61 62 cout << "(" << i <<"," << j << ") = " << board[i][j] << endl ; 63 board[i][j]= INT_MAX; 64 65 } 66 67 68 void bfs(vector<vector<int> > &board, int i, int j) 69 { 70 fill(board, i, j); 71 72 while(!m_que.empty()) 73 { 74 pair<int, int> p = m_que.front() ; 75 m_que.pop(); 76 77 i = p.first; 78 j = p.second; 79 80 fill(board, i, j-1); 81 fill(board, i, j+1); 82 fill(board, i-1, j); 83 fill(board, i+1, j); 84 } 85 86 } 87 88 void dfs(vector<vector<int> > board) 89 { 90 if (board.empty()) return; 91 92 dfs(board, 2 ,2); 93 94 } 95 void bfs(vector<vector<int> > board) 96 { 97 if (board.empty()) return; 98 99 bfs(board, 2 ,2);100 101 }102 };103 104 int main()105 {106 vector<vector<int> > board;107 vector<int> a;108 a.resize(4, 0);109 110 a[0] = 0;111 a[1] = 1;112 a[2] = 2;113 a[3] = 3;114 board.push_back(a);115 116 a[0] = 4;117 a[1] = 5;118 a[2] = 6;119 a[3] = 7;120 board.push_back(a);121 122 a[0] = 8;123 a[1] = 9;124 a[2] = 10;125 a[3] = 11;126 board.push_back(a);127 128 a[0] = 12;129 a[1] = 13;130 a[2] = 14;131 a[3] = 15;132 board.push_back(a);133 134 135 // board.clear();136 Solution sl;137 138 139 for(int i = 0; i < board.size(); i++)140 printVector(board[i]);141 142 cout <<endl;143 cout << "dfs" <<endl;144 sl.dfs(board);145 cout << "bfs" <<endl;146 sl.bfs(board);147 148 for(int i = 0; i < board.size(); i++)149 printVector(board[i]);150 151 return 0;152 }
打印结果
[root@localhost surroundedRegions]# ./a.out
矩阵
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
dfs
(2,2) = 10
(2,1) = 9
(2,0) = 8
(1,0) = 4
(1,1) = 5
(1,2) = 6
(1,3) = 7
(0,3) = 3
(0,2) = 2
(0,1) = 1
(0,0) = 0
(2,3) = 11
(3,3) = 15
(3,2) = 14
(3,1) = 13
(3,0) = 12
bfs
(2,2) = 10
(2,1) = 9
(2,3) = 11
(1,2) = 6
(3,2) = 14
(2,0) = 8
(1,1) = 5
(3,1) = 13
(1,3) = 7
(3,3) = 15
(0,2) = 2
(1,0) = 4
(3,0) = 12
(0,1) = 1
(0,3) = 3
(0,0) = 0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。