跳到主要内容

广度优先搜索

提示
  1. 广度优先搜索定义：广度优先搜索（BFS）是一种用于遍历或搜索树或图的数据结构的算法，它从一个节点开始，然后遍历节点的所有邻居，再遍历邻居的邻居，以此类推。
  2. 算法流程：在BFS中，算法使用队列来跟踪待访问的顶点。首先访问起始顶点，然后依次访问所有相邻顶点，并将未访问的相邻顶点添加到队列中。这个过程一直持续到队列为空，表示所有可达顶点都已访问。
  3. 应用领域：BFS广泛应用于构建搜索索引、GPS导航系统、路径查找算法、检测无向图中的循环、在网络流算法中寻找最大流，以及在最小生成树算法中。

遍历意味着访问图的所有节点。广度优先遍历或广度优先搜索是一种用于搜索图或树数据结构的所有顶点的递归算法。

BFS算法​

标准的BFS实现将图的每个顶点放入以下两种类别之一：

  1. 已访问
  2. 未访问

该算法的目的是在避免循环的同时将每个顶点标记为已访问。

算法工作如下：

  1. 从将图的任何一个顶点放入队列的后面开始。
  2. 取队列的前端项并将其添加到已访问列表中。
  3. 创建该顶点的相邻节点列表。将那些不在已访问列表中的节点添加到队列的后面。
  4. 重复步骤2和3，直到队列为空。

图可能有两个不同的不连通部分，为了确保我们覆盖每个顶点，我们还可以在每个节点上运行BFS算法。

BFS示例​

让我们看一个广度优先搜索算法的示例。我们使用一个具有5个顶点的无向图。

具有5个顶点的无向图

我们从顶点0开始，BFS算法首先将其放入已访问列表中，并将其所有相邻顶点放入队列中。

访问起始顶点并将其相邻顶点添加到队列

接下来，我们访问队列的前端元素，即1，并转到其相邻节点。由于0已经被访问，我们访问2。

访问起始节点0的第一个相邻节点1

顶点2有一个未访问的相邻顶点4，所以我们将其添加到队列的后面，并访问队列的前端元素3。

访问2，它被添加到队列中以添加其相邻节点

访问

由于队列中只剩下4，因为3的唯一相邻节点0已经被访问，我们访问它。

访问队列中的最后一个剩余项以检查它是否有未访问的相邻节点

由于队列为空，我们已经完成了图的广度优先遍历。

BFS伪代码​

create a queue Q
mark v as visited and put v into Q
while Q is non-empty
    remove the head u of Q
    mark and enqueue all (unvisited) neighbours of u

Python、Java和C/C++示例​

下面是带有示例的广度优先搜索算法代码。为了便于理解算法，代码已经进行了简化，以便专注于算法而不是其他细节。

Python Java C C++

# Python中的BFS算法


import collections

# BFS算法
def bfs(graph, root):

    visited, queue = set(), collections.deque([root])
    visited.add(root)

    while queue:

        # 从队列中出队一个顶点
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        # 如果未被访问，标记为已访问并入队
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)


if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("以下是广度优先遍历: ")
    bfs(graph, 0)

// Java中的BFS算法

import java.util.*;

public class Graph {
  private int V;
  private LinkedList<Integer> adj[];

  // 创建图
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  // 向图添加边
  void addEdge(int v, int w) {
    adj[v].add(w);
  }

  // BFS算法
  void BFS(int s) {

    boolean visited[] = new boolean[V];

    LinkedList<Integer> queue = new LinkedList();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }

  public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    System.out.println("以下是广度优先遍历 " + "(从顶点2开始)");

    g.BFS(2);
  }
}

// 在 C 中实现 BFS 算法

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
  int items[SIZE];
  int front;
  int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjLists;
  int* visited;
};

// BFS 算法
void bfs(struct Graph* graph, int startVertex) {
  struct queue* q = createQueue();

  graph->visited[startVertex] = 1;
  enqueue(q, startVertex);

  while (!isEmpty(q)) {
    printQueue(q);
    int currentVertex = dequeue(q);
    printf("访问了 %d\n", currentVertex);

    struct node* temp = graph->adjLists[currentVertex];

    while (temp) {
      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) {
        graph->visited[adjVertex] = 1;
        enqueue(q, adjVertex);
      }
      temp = temp->next;
    }
  }
}

// 创建一个节点
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// 创建一个图
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));
  graph->visited = malloc(vertices * sizeof(int));

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }

  return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
  // 从 src 到 dest 添加边
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // 从 dest 到 src 添加边
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

// 创建队列
struct queue* createQueue() {
  struct queue* q = malloc(sizeof(struct queue));
  q->front = -1;
  q->rear = -1;
  return q;
}

// 检查队列是否为空
int isEmpty(struct queue* q) {
  if (q->rear == -1)
    return 1;
  else
    return 0;
}

// 向队列中添加元素
void enqueue(struct queue* q, int value) {
  if (q->rear == SIZE - 1)
    printf("\n队列已满!!");
  else {
    if (q->front == -1)
      q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
  }
}

// 从队列中移除元素
int dequeue(struct queue* q) {
  int item;
  if (isEmpty(q)) {
    printf("队列为空");
    item = -1;
  } else {
    item = q->items[q->front];
    q->front++;
    if (q->front > q->rear) {
      printf("重置队列 ");
      q->front = q->rear = -1;
    }
  }
  return item;
}

// 打印队列
void printQueue(struct queue* q) {
  int i = q->front;

  if (isEmpty(q)) {
    printf("队列为空");
  } else {
    printf("\n队列包含 \n");
    for (i = q->front; i < q->rear + 1; i++) {
      printf("%d ", q->items[i]);
    }
  }
}

int main() {
  struct Graph* graph = createGraph(6);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 1, 4);
  addEdge(graph, 1, 3);
  addEdge(graph, 2, 4);
  addEdge(graph, 3, 4);

  bfs(graph, 0);

  return 0;
}
// C++中的BFS算法

#include <iostream>
#include <list>

using namespace std;

class Graph {
  int numVertices;
  list<int>* adjLists;
  bool* visited;

   public:
  Graph(int vertices);
  void addEdge(int src, int dest);
  void BFS(int startVertex);
};

// 创建具有给定顶点的图，并维护邻接列表
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
}

// 向图添加边
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_back(dest);
  adjLists[dest].push_back(src);
}

// BFS算法
void Graph::BFS(int startVertex) {
  visited = new bool[numVertices];
  for (int i = 0; i < numVertices; i++)
    visited[i] = false;

  list<int> queue;

  visited[startVertex] = true;
  queue.push_back(startVertex);

  list<int>::iterator i;

  while (!queue.empty()) {
    int currVertex = queue.front();
    cout << "已访问 " << currVertex << " ";
    queue.pop_front();

    for (i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i) {
      int adjVertex = *i;
      if (!visited[adjVertex]) {
        visited[adjVertex] = true;
        queue.push_back(adjVertex);
      }
    }
  }
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);
  g.addEdge(3, 3);

  g.BFS(2);

  return 0;
}

BFS算法复杂性​

BFS算法的时间复杂度表示为O(V + E)，其中V是节点数，E是边数。

算法的空间复杂度为O(V)。

BFS算法应用​

  1. 用于构建搜索索引
  2. 用于GPS导航
  3. 路径查找算法
  4. 在Ford-Fulkerson算法中用于查找网络中的最大流
  5. 在无向图中检测循环
  6. 在最小生成树中使用
最后于 更新