广度优先搜索 (BFS) 算法

更新于 2025/10/16 16:21:06

广度优先搜索 (BFS) 算法

广度优先搜索 (BFS) 算法以广度方向遍历图，在图数据结构中搜索满足一组条件的节点。当任何迭代中出现死胡同时，它使用队列来记住下一个开始搜索的顶点。

广度优先搜索 (BFS) 算法从树根开始，在移动到下一深度节点之前，先探索当前深度的所有节点。

如上例所示，BFS 算法首先从 A 遍历到 B、E、F，然后到 C、G，最后到 D。它采用以下规则。

规则 1 − 访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列。
规则 2 −如果未找到相邻顶点，则从队列中移除第一个顶点。
规则 3 −重复规则 1 和规则 2，直到队列为空。

步骤	遍历	描述
1		初始化队列。
2		我们从访问S（起始节点）开始，并将其标记为已访问。
3		然后，我们看到S中一个未访问的相邻节点。在此示例中，我们有三个节点，但按字母顺序我们选择 A，将其标记为已访问并将其入队。
4		接下来，来自 S 的未访问相邻节点是 B。我们将其标记为已访问并将其入队。
5		接下来，来自S的未访问相邻节点是C。我们将其标记为已访问并将其入队。
6		现在，S 中没有未访问的相邻节点。因此，我们出队并找到 A。
7		从 A 中，我们得到 D 作为未访问的相邻节点。我们将其标记为已访问并将其入队。

在此阶段，我们没有未标记（未访问）的节点。但根据算法，我们继续出队以获取所有未访问的节点。当队列清空时，程序结束。

示例

以下是广度优先搜索 (BFS) 算法在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex {
   char label;
   bool visited;
};
//队列变量
int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;
//图变量
//顶点数组
struct Vertex* lstVertices[MAX];
//邻接矩阵
int adjMatrix[MAX][MAX];
//顶点数量
int vertexCount = 0;
//队列函数
void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}
int removeData() {
   queueItemCount--;
   return queue[front++]; 
}
bool isQueueEmpty() {
   return queueItemCount == 0;
}
//图形函数
//将顶点添加到顶点列表
void addVertex(char label) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}
//将边添加到边数组
void addEdge(int start,int end) {
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}
//显示顶点
void displayVertex(int vertexIndex) {
   printf("%c ",lstVertices[vertexIndex]->label);
}       
//获取相邻的未访问顶点
int getAdjUnvisitedVertex(int vertexIndex) {
   int i;
	
   for(i = 0; i<vertexCount; i++) {
      if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)
         return i;
   }
   return -1;
}
void breadthFirstSearch() {
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
   //显示顶点
   displayVertex(0);   
   //在队列中插入顶点索引
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()) {
      //获取队列最前面的未访问顶点
      int tempVertex = removeData();   
      //未找到相邻顶点
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }	
   }   
   //队列为空，搜索完成，重置访问标志       
   for(i = 0;i<vertexCount;i++) {
      lstVertices[i]->visited = false;
   }    
}
int main() {
   int i, j;

   for(i = 0; i<MAX; i++) { // set adjacency 
      for(j = 0; j<MAX; j++) // matrix to 0
         adjMatrix[i][j] = 0;
   }
   addVertex('S');   // 0
   addVertex('A');   // 1
   addVertex('B');   // 2
   addVertex('C');   // 3
   addVertex('D');   // 4
   addEdge(0, 1);    // S - A
   addEdge(0, 2);    // S - B
   addEdge(0, 3);    // S - C
   addEdge(1, 4);    // A - D
   addEdge(2, 4);    // B - D
   addEdge(3, 4);    // C - D
   printf("
Breadth First Search: ");
   breadthFirstSearch();
   return 0;
}

输出

Breadth First Search: S A B C D

//广度优先遍历的 C++ 代码
#include <iostream>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex {
   char label;
   bool visited;
};
//队列变量
int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;
//图变量
//顶点数组
struct Vertex* lstVertices[MAX];
//邻接矩阵
int adjMatrix[MAX][MAX];
//顶点数量
int vertexCount = 0;
//队列函数
void insert(int data) {
   queue[++rear] = data;
   queueItemCount++;
}
int removeData() {
   queueItemCount--;
   return queue[front++]; 
}
bool isQueueEmpty() {
   return queueItemCount == 0;
}
//图形函数
//将顶点添加到顶点列表
void addVertex(char label) {
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}
//将边添加到边数组
void addEdge(int start,int end) {
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}
//显示顶点
void displayVertex(int vertexIndex) {
   std::cout << lstVertices[vertexIndex]->label << " ";
}       
//获取相邻的未访问顶点
int getAdjUnvisitedVertex(int vertexIndex) {
   int i;
   for(i = 0; i<vertexCount; i++) {
      if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)
         return i;
   }
   return -1;
}
void breadthFirstSearch() {
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
  //显示顶点
   displayVertex(0);   
   //在队列中插入顶点索引
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()) {
      //获取队列最前面的未访问顶点
      int tempVertex = removeData();   
      //未找到相邻顶点
      while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
		
   }   
   //队列为空，搜索完成，重置访问标志       
   for(i = 0;i<vertexCount;i++) {
      lstVertices[i]->visited = false;
   }    
}
int main() {
   int i, j;
   for(i = 0; i<MAX; i++) { // set adjacency 
      for(j = 0; j<MAX; j++) // matrix to 0
         adjMatrix[i][j] = 0;
   }
   addVertex('S');   // 0
   addVertex('A');   // 1
   addVertex('B');   // 2
   addVertex('C');   // 3
   addVertex('D');   // 4
   addEdge(0, 1);    // S - A
   addEdge(0, 2);    // S - B
   addEdge(0, 3);    // S - C
   addEdge(1, 4);    // A - D
   addEdge(2, 4);    // B - D
   addEdge(3, 4);    // C - D
   std::cout << "Breadth First Search: ";
   breadthFirstSearch();
   return 0;
}

输出

Breadth First Search: S A B C D

//Java code for Breadth First Traversal
import java.util.LinkedList;
import java.util.Queue;
class Vertex {
    char label;
    boolean visited;
    public Vertex(char label) {
        this.label = label;
        visited = false;
    }
}
public class Graph {
    private static final int MAX = 5;
    private Vertex[] lstVertices;
    private int[][] adjMatrix;
    private int vertexCount;
    public Graph() {
        lstVertices = new Vertex[MAX];
        adjMatrix = new int[MAX][MAX];
        vertexCount = 0;
    }
    private void addVertex(char label) {
        Vertex vertex = new Vertex(label);
        lstVertices[vertexCount++] = vertex;
    }
    private void addEdge(int start, int end) {
        adjMatrix[start][end] = 1;
        adjMatrix[end][start] = 1;
    }
    private void displayVertex(int vertexIndex) {
        System.out.print(lstVertices[vertexIndex].label + " ");
    }
    private int getAdjUnvisitedVertex(int vertexIndex) {
        for (int i = 0; i < vertexCount; i++) {
            if (adjMatrix[vertexIndex][i] == 1 && !lstVertices[i].visited)
                return i;
        }
        return -1;
    }
    private void breadthFirstSearch() {
        lstVertices[0].visited = true;
        displayVertex(0);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int tempVertex = queue.poll();
            int unvisitedVertex;
            while ((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1) {
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                queue.add(unvisitedVertex);
            }
        }
        // 重置访问标志
        for (int i = 0; i < vertexCount; i++) {
            lstVertices[i].visited = false;
        }
    }
    public static void main(String[] args) {
        Graph graph = new Graph();
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++)
                graph.adjMatrix[i][j] = 0;
        }
        graph.addVertex('S');   // 0
        graph.addVertex('A');   // 1
        graph.addVertex('B');   // 2
        graph.addVertex('C');   // 3
        graph.addVertex('D');   // 4
        graph.addEdge(0, 1);    // S - A
        graph.addEdge(0, 2);    // S - B
        graph.addEdge(0, 3);    // S - C
        graph.addEdge(1, 4);    // A - D
        graph.addEdge(2, 4);    // B - D
        graph.addEdge(3, 4);    // C - D
        System.out.print("Breadth First Search: ");
        graph.breadthFirstSearch();
    }
}

输出

Breadth First Search: S A B C D

#Python program for Breadth First Search
# 定义 MAX 5
MAX = 5
class Vertex:
   def __init__(self, label):
      self.label = label
      self.visited = False
# 队列变量
queue = [0] * MAX
rear = -1
front = 0
queueItemCount = 0
# 图变量
# 顶点数组
lstVertices = [None] * MAX
# 邻接矩阵
adjMatrix = [[0] * MAX for _ in range(MAX)]
# 顶点数量
vertexCount = 0
# 队列函数
def insert(data):
   global rear, queueItemCount
   rear += 1
   queue[rear] = data
   queueItemCount += 1
def removeData():
   global front, queueItemCount
   queueItemCount -= 1
   data = queue[front]
   front += 1
   return data
def isQueueEmpty():
   return queueItemCount == 0
# 图形函数
#将顶点添加到顶点列表
def addVertex(label):
   global vertexCount
   vertex = Vertex(label)
   lstVertices[vertexCount] = vertex
   vertexCount += 1
#将边添加到边数组
def addEdge(start, end):
   adjMatrix[start][end] = 1
   adjMatrix[end][start] = 1
#显示顶点
def displayVertex(vertexIndex):
   print(lstVertices[vertexIndex].label, end=" ")
#获取相邻的未访问顶点
def getAdjUnvisitedVertex(vertexIndex):
   for i in range(vertexCount):
      if adjMatrix[vertexIndex][i] == 1 and not lstVertices[i].visited:
         return i
   return -1
def breadthFirstSearch():
    #将第一个节点标记为已访问
   lstVertices[0].visited = True
   #显示顶点
   displayVertex(0)
   #在队列中插入顶点索引
   insert(0)
   while not isQueueEmpty():
    #获取队列最前面的未访问顶点
      tempVertex = removeData()     
      #未找到相邻顶点
      unvisitedVertex = getAdjUnvisitedVertex(tempVertex)
      while unvisitedVertex != -1:
         lstVertices[unvisitedVertex].visited = True
         displayVertex(unvisitedVertex)
         insert(unvisitedVertex)
         unvisitedVertex = getAdjUnvisitedVertex(tempVertex)     
    #队列为空，搜索完成，重置访问标志
   for i in range(vertexCount):
      lstVertices[i].visited = False
# main function
if __name__ == "__main__":
   # 设置邻接关系
   for i in range(MAX):
       #matrix to 0
       for j in range(MAX):
         adjMatrix[i][j] = 0
   addVertex('S')
   addVertex('A')
   addVertex('B')
   addVertex('C')
   addVertex('D')
   addEdge(0, 1)
   addEdge(0, 2)
   addEdge(0, 3)
   addEdge(1, 4)
   addEdge(2, 4)
   addEdge(3, 4)
   print("Breadth First Search: ", end="")
   breadthFirstSearch()

输出

Breadth First Search: S A B C D

点击查看广度优先搜索 (BFS) 算法的 C 实现

BFS 算法的复杂度

时间复杂度

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

空间复杂度

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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

广度优先搜索 (BFS) 算法

广度优先搜索 (BFS) 算法

示例

输出

输出

输出

输出

BFS 算法的复杂度

时间复杂度

空间复杂度

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！