如果用非递归方式实现：
- DFS 需要 stack
- BFS 需要 queue
Java 版本实现 请见：https://blog.csdn.net/Gene1994/article/details/85097507
#include<iostream>
#include<fstream>
#include<queue>
#include<stack>
using namespace std;
#define MAX 10
typedef struct graph
{
int n; //顶点数
int e; //边数
int edge[MAX][MAX]; //标识边，0为没有该边，不为0则有边，且标识边的权值
}Graph;
int visit[MAX] = { 0 }; //表示该顶点有没有访问过，没有为0，有为1
void InitGraph(Graph *G)
{
for (int i = 0; i < MAX;i++)
for (int j = 0; j < MAX; j++)
(*G).edge[i][j] = 0;
}
//广度优先搜索算法
void BFS(Graph G, int num) //num为从该点开始进行搜索
{
queue<int>Queue;
cout << num <<" ";
visit[num] = 1;
Queue.push(num); //访问完该点后入队列
while (!Queue.empty()) //队列不为空时
{
num = Queue.front(); //出队
Queue.pop();
for (int i = 0; i < G.n; i++)
{
if (G.edge[num][i] != 0 && visit[i] == 0) //找到与之相连的顶点入队
{
cout << i << " ";
Queue.push(i);
visit[i] = 1;
}
}
}
cout << endl;
}
void DFS1(Graph G, int num) //深度优先搜索递归算法
{
int i;
cout << num << " ";
visit[num] = 1;
for (i = 0; i < G.n; i++)
{
if (G.edge[num][i] != 0 && visit[i] == 0)
DFS1(G, i);
}
}
void DFS2(Graph G, int num) //深度优先搜索非递归算法
{
stack<int> Stack;
visit[num] = 1;
Stack.push(num);
while (!Stack.empty())
{
num = Stack.top();
Stack.pop();
cout << num << " ";
for (int i = G.n - 1; i >= 0; i--)
{
if (G.edge[num][i] != 0 && visit[i] == 0)
{
Stack.push(i);
visit[i] = 1;
}
}
}
cout << endl;
}
int main()
{
int a, b, v, i;
Graph G;
ifstream cin("data.txt");
cin >> G.n >> G.e; //n,e为顶点个数，边个数
InitGraph(&G); //对G进行初始化，整个MAX范围初始化
for (i = 0; i < G.e; i++) //建图
{
cin >> a >> b >> v; //a,b为顶点，v为权值
G.edge[a][b] = v;
G.edge[b][a] = v;
}
BFS(G, 0); //0为开始搜索的顶点序号
for (i = 0; i < MAX; i++)
visit[i] = 0;
DFS1(G, 0);
cout << endl;
for (i = 0; i < MAX; i++)
visit[i] = 0;
DFS2(G, 0);
system("pause");
return 0;
3.一列排好序的数列，其中有两个数字被调换了。请用o(n)的复杂度发现这两个数字。
// 用于存储当前找到的发生交换的数
int first = -1, second;
// 从前往后依次寻找逆序并相邻的数字对
for (int i = 0; i < n; i++) {
// 存在逆序
if (i > 0 && val[i] < val[i - 1]) {
// 如果当前一对都没有找到
if (first == -1) {
// 不放先假设只有一对
first = i - 1; second = i;
}
else {
// 存在两对，只需要修改second
second = i;
}
}
}
// Swap(val[first], val[second])
4.和上题类似的场景，但是是发生在BST中的两个节点被调换。在中序遍历过程中，在处理current节点时可以做类似于上述 找first 和 找second的事情
public class Solution {
TreeNode firstNode;
TreeNode secondNode;
TreeNode lastNode;
public void recoverTree(TreeNode root) {
inorderTraversal(root);
int tmp = firstNode.val;
firstNode.val = secondNode.val;
secondNode.val = tmp;
}
private void inorderTraversal(TreeNode root) {
if(root == null)
return;
inorderTraversal(root.left);
if(lastNode != null && firstNode == null && lastNode.val >= root.val)
firstNode = lastNode;
if(lastNode != null && firstNode != null && lastNode.val >= root.val)
secondNode = root;
lastNode = root; // lastNode，用于帮助发现firstNode
inorderTraversal(root.right);
}
}
- 矩阵中的孤岛个数
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
递归时做的事情：将这个岛屿周围的、尚未计算过的节点，设置为visited。
最终，dfs外面访问过几次，就是几个孤岛
public int numIslands(char[][] grid) {
if(grid == null || grid.length ==0 || grid[0].length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
int numbers = 0;
for(int i =0; i< m; i++){
for (int j =0;j<n;j++){
if(grid[i][j] == '1'){
dfs(grid, i, j);
numbers++;
}
}
}
return numbers;
}
public void dfs(char[][] grid, int i, int j){
if(i<0 || i >= grid.length || j<0 || j>= grid[0].length){
return;
}
if(grid[i][j] == '1'){
grid[i][j] = '0';
dfs(grid, i-1, j);
dfs(grid, i+1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}
}
- 对称树的判定
(1) 解法1：用层次遍历的方法
public boolean isSymmetric(TreeNode root) {
// Write your code here
if(root == null) return true;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int size = q.size();
List<Integer> level = new ArrayList<>();
for(int i = 0; i<size; i++){
TreeNode cur = q.poll();
level.add(cur.val);
if(cur.left == null && cur.right!=null){
q.offer(new TreeNode(-1));
}
else if(cur.left != null){
q.offer(cur.left);
}
if(cur.right == null && cur.left!=null){
q.offer(new TreeNode(-1));
}
else if(cur.right != null){
q.offer(cur.right);
}
}
if(!valid(level)) return false;
}
return true;
}
public boolean valid(List<Integer> l){
int left = 0;
int right = l.size()-1;
while(left <= right){
if(l.get(left) != l.get(right)) return false;
left++;
right--;
}
return true;
}
(2) 解法2：用中序遍历法：左根右 VS 右根左的结果
List<Integer> path1 = new ArrayList<>();
List<Integer> path2 = new ArrayList<>();
public boolean isSymmetric(TreeNode root) {
// Write your code here
if (root == null) {
return true;
}
rightInorder(root);
leftInorder(root);
if (path1.size() != path2.size()) {
return false;
}
for (int i = 0; i < path1.size(); i++) {
if (path1.get(i) != path2.get(i)) {
return false;
}
}
return true;
}
private void leftInorder(TreeNode root) {
if (root == null) {
return;
}
leftInorder(root.left);
path1.add(root.val);
leftInorder(root.right);
}
private void rightInorder(TreeNode root) {
if (root == null) {
return;
}
rightInorder(root.right);
path2.add(root.val);
rightInorder(root.left);
}
- 朋友圈个数：给定一个矩阵数组 代表了两个朋友间认识或者不认识。求独立的朋友圈个数
说明：dfs中visited的设定，应该是每次进入dfs函数时 设置的，这样可以保证每个人只走一次dfs函数
public int findCircleNum(int[][] M) {
if(M==null ||M.length == 0 || M[0].length == 0){
return 0;
}
int n = M.length;
int[] visited = new int[n]; // =0代表未访问
int circle = 0;
for(int i =0; i<n; i++){
if(visited[i] ==0){
circle++;
dfs(M, visited, i);
}
}
return circle;
}
public void dfs(int[][] M, int[] visited , int x){
if(visited[x] == 1){
return;
}
visited[x] =1;
for(int i =0;i<M.length; i++){
if(i == x)
continue;
if(M[x][i] == 1){
dfs(M, visited, i);
}
}
}
- 被围绕的区域：给一个二维的矩阵，包含 'X' 和 'O', 找到所有被 'X' 围绕的区域，并用 'X' 填充满。
用BFS算法，从边缘的O开始找它的O邻居，放入待分析队列，继续进行下去
class Solution {
public void solve(char[][] board) {
if(board == null || board.length ==0 || board[0].length ==0 )
return ;
int n = board.length;
int m = board[0].length;
for(int i = 0; i < n ;i++){
bfs(board, i,0);
bfs(board, i,m-1);
}
for(int j =0; j< m; j++){
bfs(board, 0, j);
bfs(board, n-1, j);
}
for(int i=0; i< n;i++){
for(int j=0; j<m;j++){
if(board[i][j] == 'W')
board[i][j] = 'O';
else{
board[i][j] = 'X';
}
}
}
}
public void bfs(char[][] board, int x, int y){
if(board[x][y]!='O')
return;
int[] addx = {0,0,1, -1};
int[] addy = {1,-1,0, 0};
Queue<Integer> x_q = new LinkedList<Integer>();
Queue<Integer> y_q = new LinkedList<Integer>();
x_q.offer(x); // 放入这个队列的是：和边缘O相连，待分析其邻居的O节点
y_q.offer(y);
board[x][y]='W';
while(!x_q.isEmpty()){
int cur_x = x_q.poll();
int cur_y = y_q.poll();
for(int i=0; i< 4; i++){
int x1 = addx[i] + cur_x;
int y1 = addy[i] + cur_y;
if(x1>=0&& x1<board.length && y1>=0 && y1<board[0].length && board[x1][y1]=='O'){
board[x1][y1]='W';
x_q.offer(x1);
y_q.offer(y1);
}
}
}
}
}
