广度优先搜索（BFS）

Maha ·

更新时间:2024-11-15

· 645 次阅读

广度优先搜索（BFS）的数据结构是队列queue。算法思路是用vector来记录每层结点，然后清空当前队列，再将该层队列的下一层加入队列。
算法思路：

public class BreadthFirstPaths {
	private boolean[] marked; // 到达该顶点的最短路径已知吗？
	private int[] edgeTo; // 到达该顶点的已知路径上的最后一个顶点
	private final int s; // 起点
	public BreadthFirstPaths(Graph G, int s) {
		marked = new boolean[G.V()];
		edgeTo = new int[G.V()];
		this.s = s;
		bfs(G, s);
	}
	private void bfs(Graph G, int s) {
		Queue queue = new Queue();
		marked[s] = true; // 标记起点
		queue.enqueue(s); // 将它加入队列
		while (!queue.isEmpty()) {
			int v = queue.dequeue(); // 从队列中删去下一顶点
			for (int w : G.adj(v))
				if (!marked[w]) {// 对于每个未被标记的相邻顶点
					edgeTo[w] = v; // 保存最短路径的最后一条边
					marked[w] = true; // 标记它，因为最短路径已知
					queue.enqueue(w); // 并将它添加到队列中
				}
		}
	}
	public boolean hasPathTo(int v) {
	    return marked[v];
	}
	public Iterable pathTo(int v)
// 和深度优先搜索中的实现相同（请见算法4.1）
}

参考题：LeetCode103

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector> zigzagLevelOrder(TreeNode* root) {
        vector<vector> res;
        if (!root) return res;
        vector vec;
        vector nodes;
        queue que;
        que.push(root);
        int level = 0;
        while (!que.empty()) {
        	while (!que.empty()) {
        		TreeNode* node = que.front();
        		nodes.push_back(node);
        		vec.push_back(node->val);
        		que.pop();
        	}
        	level++;
        	for (auto node : nodes) {
        		if (node->left) que.push(node->left);
        		if (node->right) que.push(node->right);
        	}
        	nodes.clear();
        	if (level%2 == 0) reverse(vec.begin(), vec.end());
        	res.push_back(vec);
        	vec.clear();
        }
        return res;
    }
};

作者：dream161110

广度优先搜索

1024 个赞